Index: test/wasm/Inputs/start.ll =================================================================== --- test/wasm/Inputs/start.ll +++ test/wasm/Inputs/start.ll @@ -1,4 +1,5 @@ target triple = "wasm32-unknown-unknown" +target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128" define void @_start() local_unnamed_addr { entry: Index: test/wasm/lto/lto-start.ll =================================================================== --- /dev/null +++ test/wasm/lto/lto-start.ll @@ -0,0 +1,19 @@ +; 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 +} Index: wasm/CMakeLists.txt =================================================================== --- wasm/CMakeLists.txt +++ wasm/CMakeLists.txt @@ -6,6 +6,7 @@ Driver.cpp InputChunks.cpp InputFiles.cpp + LTO.cpp MarkLive.cpp OutputSections.cpp SymbolTable.cpp @@ -18,6 +19,8 @@ BinaryFormat Core Demangle + LTO + MC Object Option Support Index: wasm/Config.h =================================================================== --- wasm/Config.h +++ wasm/Config.h @@ -13,6 +13,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/ADT/StringSet.h" #include "llvm/BinaryFormat/Wasm.h" +#include "llvm/Support/CachePruning.h" namespace lld { namespace wasm { @@ -28,19 +29,26 @@ 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 SearchPaths; + llvm::CachePruningPolicy ThinLTOCachePolicy; }; // The only instance of Configuration struct. Index: wasm/Driver.cpp =================================================================== --- wasm/Driver.cpp +++ wasm/Driver.cpp @@ -26,6 +26,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Path.h" #include "llvm/Support/Process.h" +#include "llvm/Support/TargetSelect.h" #define DEBUG_TYPE "lld" @@ -48,6 +49,17 @@ #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 ArgsArr); @@ -72,6 +84,7 @@ Config = make(); Symtab = make(); + initLLVM(); LinkerDriver().link(Args); // Exit immediately if we don't need to return to the caller. @@ -169,7 +182,8 @@ 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)) @@ -178,8 +192,13 @@ Files.push_back(make(MBRef)); return; } + case file_magic::bitcode: + Files.push_back(make(MBRef)); + break; + default: + Files.push_back(make(MBRef)); + } - Files.push_back(make(MBRef)); } // Add a given library by searching it from input search paths. @@ -257,8 +276,20 @@ } } +// 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 ArgsArr) { WasmOptTable Parser; + Config->ProgName = ArgsArr[0]; opt::InputArgList Args = Parser.parse(ArgsArr.slice(1)); // Handle --help @@ -290,6 +321,7 @@ 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); @@ -300,6 +332,7 @@ !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); @@ -368,12 +401,11 @@ // 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 ` options. for (auto *Arg : Args.filtered(OPT_undefined)) - Symtab->addUndefinedFunction(Arg->getValue(), 0, nullptr, nullptr); + handleUndefined(Arg->getValue()); } createFiles(Args); @@ -389,6 +421,12 @@ 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(); Index: wasm/InputFiles.h =================================================================== --- wasm/InputFiles.h +++ wasm/InputFiles.h @@ -14,6 +14,7 @@ #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" @@ -28,6 +29,12 @@ using llvm::wasm::WasmRelocation; using llvm::wasm::WasmSignature; +namespace llvm { +namespace lto { +class InputFile; +} +} + namespace lld { namespace wasm { @@ -42,6 +49,7 @@ enum Kind { ObjectKind, ArchiveKind, + BitcodeKind, }; virtual ~InputFile() {} @@ -57,10 +65,15 @@ // An archive file name if this file is created from an archive. StringRef ParentName; + ArrayRef 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 Symbols; + private: const Kind FileKind; }; @@ -113,7 +126,6 @@ std::vector CustomSections; llvm::DenseMap CustomSectionsByIndex; - ArrayRef 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; @@ -126,12 +138,18 @@ bool isExcludedByComdat(InputChunk *Chunk) const; - // List of all symbols referenced or defined by this file. - std::vector Symbols; - std::unique_ptr 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 Obj; +}; + // Opens a given file. llvm::Optional readFile(StringRef Path); Index: wasm/InputFiles.cpp =================================================================== --- wasm/InputFiles.cpp +++ wasm/InputFiles.cpp @@ -369,6 +369,34 @@ Symtab->addFile(Obj); } +static Symbol *createBitcodeSymbol(const lto::InputFile::Symbol &ObjSym, + BitcodeFile &F) { + StringRef NameRef = Saver.save(ObjSym.getName()); + + if (ObjSym.isUndefined()) { + if (ObjSym.isExecutable()) + return Symtab->addUndefinedFunction(NameRef, 0, &F, nullptr); + return Symtab->addUndefinedData(NameRef, 0, &F); + } + + if (ObjSym.isExecutable()) + return Symtab->addDefinedFunction(NameRef, 0, &F, nullptr); + return Symtab->addDefinedData(NameRef, 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) { + fatal(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) Index: wasm/LTO.h =================================================================== --- /dev/null +++ wasm/LTO.h @@ -0,0 +1,58 @@ +//===- 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 +#include + +namespace llvm { +namespace lto { +class LTO; +} +} + +namespace lld { +namespace wasm { + +class BitcodeFile; +class InputFile; + +class BitcodeCompiler { +public: + BitcodeCompiler(); + ~BitcodeCompiler(); + + void add(BitcodeFile &F); + std::vector compile(); + +private: + std::unique_ptr LTOObj; + std::vector> Buff; + std::vector> Files; +}; +} // namespace wasm +} // namespace lld + + +#endif Index: wasm/LTO.cpp =================================================================== --- /dev/null +++ wasm/LTO.cpp @@ -0,0 +1,168 @@ +//===- 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/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 +#include +#include +#include +#include +#include + +using namespace llvm; +using namespace llvm::object; + +using namespace lld; +using namespace lld::wasm; + +// This is for use when debugging LTO. +static void saveBuffer(StringRef Buffer, const Twine &Path) { + std::error_code EC; + raw_fd_ostream OS(Path.str(), EC, sys::fs::OpenFlags::F_None); + if (EC) + error("cannot create " + Path + ": " + EC.message()); + OS << Buffer; +} + +static void checkError(Error E) { + handleAllErrors(std::move(E), + [&](ErrorInfoBase &EIB) { error(EIB.message()); }); +} + +static void diagnosticHandler(const DiagnosticInfo &DI) { + SmallString<128> S; + raw_svector_ostream OS(S); + DiagnosticPrinterRawOStream DP(OS); + DI.print(DP); + warn(S); +} + +static std::unique_ptr 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(std::move(C), Backend, + Config->LTOPartitions); +} + +BitcodeCompiler::BitcodeCompiler() : LTOObj(createLTO()) {} + +BitcodeCompiler::~BitcodeCompiler() = default; + +static void undefine(Symbol *S) { + if (isa(S)) + replaceSymbol(S, S->getName(), 0); + else if (isa(S)) + replaceSymbol(S, S->getName(), 0); + else + llvm_unreachable("unexpected symbol kind"); +} + +void BitcodeCompiler::add(BitcodeFile &F) { + lto::InputFile &Obj = *F.Obj; + unsigned SymNum = 0; + ArrayRef Syms = F.getSymbols(); + std::vector 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 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 MB) { + Files[Task] = std::move(MB); + })); + + checkError(LTOObj->run( + [&](size_t Task) { + return llvm::make_unique( + llvm::make_unique(Buff[Task])); + }, + Cache)); + + if (!Config->ThinLTOCacheDir.empty()) + pruneCache(Config->ThinLTOCacheDir, Config->ThinLTOCachePolicy); + + std::vector 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; +} Index: wasm/Options.td =================================================================== --- wasm/Options.td +++ wasm/Options.td @@ -136,3 +136,22 @@ def alias_max_memory_m: Flag<["-"], "m">, Alias; def alias_relocatable_r: Flag<["-"], "r">, Alias; def alias_undefined_u: JoinedOrSeparate<["-"], "u">, Alias; + +// 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">; Index: wasm/SymbolTable.h =================================================================== --- wasm/SymbolTable.h +++ wasm/SymbolTable.h @@ -11,6 +11,7 @@ #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" @@ -39,8 +40,10 @@ class SymbolTable { public: void addFile(InputFile *File); + void addCombinedLTOObject(); std::vector ObjectFiles; + std::vector BitcodeFiles; std::vector SyntheticFunctions; std::vector SyntheticGlobals; @@ -49,6 +52,7 @@ ArrayRef getSymbols() const { return SymVector; } Symbol *find(StringRef Name); + Symbol *addBitcode(StringRef Name, InputFile *File); Symbol *addDefinedFunction(StringRef Name, uint32_t Flags, InputFile *File, InputFunction *Function); Symbol *addDefinedData(StringRef Name, uint32_t Flags, InputFile *File, @@ -80,6 +84,9 @@ std::vector SymVector; llvm::DenseSet Comdats; + + // For LTO. + std::unique_ptr LTO; }; extern SymbolTable *Symtab; Index: wasm/SymbolTable.cpp =================================================================== --- wasm/SymbolTable.cpp +++ wasm/SymbolTable.cpp @@ -29,10 +29,36 @@ log("Processing: " + toString(File)); File->parse(); - if (auto *F = dyn_cast(File)) + // LLVM bitcode file + if (auto *F = dyn_cast(File)) + BitcodeFiles.push_back(F); + else if (auto *F = dyn_cast(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(MemoryBufferRef(Filename, "lto.tmp")); + Obj->parse(); + ObjectFiles.push_back(Obj); + } +} + void SymbolTable::reportRemainingUndefines() { SetVector Undefs; for (Symbol *Sym : SymVector) { @@ -64,6 +90,7 @@ if (Sym) return {Sym, false}; Sym = reinterpret_cast(make()); + Sym->IsUsedInRegularObj = false; SymVector.emplace_back(Sym); return {Sym, true}; } @@ -170,6 +197,11 @@ return true; } +Symbol *SymbolTable::addBitcode(StringRef Name, InputFile *File) { + DEBUG(dbgs() << "addBitcode: " << Name << "\n"); + return nullptr; +} + Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags, InputFile *File, InputFunction *Function) { @@ -178,12 +210,16 @@ bool WasInserted; std::tie(S, WasInserted) = insert(Name); + if (!File || File->kind() == InputFile::ObjectKind) + S->IsUsedInRegularObj = true; + if (WasInserted || S->isLazy()) { replaceSymbol(S, Name, Flags, File, Function); return S; } - checkFunctionType(S, File, &Function->Signature); + if (Function) + checkFunctionType(S, File, &Function->Signature); if (shouldReplace(S, File, Flags)) replaceSymbol(S, Name, Flags, File, Function); @@ -199,6 +235,9 @@ bool WasInserted; std::tie(S, WasInserted) = insert(Name); + if (!File || File->kind() == InputFile::ObjectKind) + S->IsUsedInRegularObj = true; + if (WasInserted || S->isLazy()) { replaceSymbol(S, Name, Flags, File, Segment, Address, Size); return S; @@ -218,6 +257,9 @@ bool WasInserted; std::tie(S, WasInserted) = insert(Name); + if (!File || File->kind() == InputFile::ObjectKind) + S->IsUsedInRegularObj = true; + if (WasInserted || S->isLazy()) { replaceSymbol(S, Name, Flags, File, Global); return S; Index: wasm/Symbols.h =================================================================== --- wasm/Symbols.h +++ wasm/Symbols.h @@ -91,10 +91,13 @@ 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; @@ -332,7 +335,12 @@ "SymbolUnion not aligned enough"); assert(static_cast(static_cast(nullptr)) == nullptr && "Not a Symbol"); - return new (S) T(std::forward(Arg)...); + + Symbol SymCopy = *S; + + T* S2 = new (S) T(std::forward(Arg)...); + S2->IsUsedInRegularObj = SymCopy.IsUsedInRegularObj; + return S2; } } // namespace wasm