diff --git a/lld/wasm/CMakeLists.txt b/lld/wasm/CMakeLists.txt --- a/lld/wasm/CMakeLists.txt +++ b/lld/wasm/CMakeLists.txt @@ -12,6 +12,7 @@ OutputSections.cpp OutputSegment.cpp Relocations.cpp + SplitApplyDataRelocsStrategy.cpp SymbolTable.cpp Symbols.cpp SyntheticSections.cpp diff --git a/lld/wasm/Config.h b/lld/wasm/Config.h --- a/lld/wasm/Config.h +++ b/lld/wasm/Config.h @@ -67,6 +67,9 @@ bool ltoDebugPassManager; UnresolvedPolicy unresolvedSymbols; + // https://github.com/v8/v8/blob/master/src/wasm/wasm-limits.h#L47 + uint64_t maxFunctionSize = 7'654'321; + llvm::StringRef entry; llvm::StringRef mapFile; llvm::StringRef outputFile; diff --git a/lld/wasm/Driver.cpp b/lld/wasm/Driver.cpp --- a/lld/wasm/Driver.cpp +++ b/lld/wasm/Driver.cpp @@ -763,6 +763,12 @@ "__wasm_apply_data_relocs", WASM_SYMBOL_VISIBILITY_DEFAULT | WASM_SYMBOL_EXPORTED, make(nullSignature, "__wasm_apply_data_relocs")); + + WasmSym::applyDataRelocsTail = symtab->addSyntheticFunction( + "__wasm_apply_data_relocs_tail", + WASM_SYMBOL_VISIBILITY_DEFAULT | WASM_SYMBOL_EXPORTED, + make(nullSignature, + "__wasm_apply_data_relocs_tail")); } } diff --git a/lld/wasm/FunctionSplitter.h b/lld/wasm/FunctionSplitter.h new file mode 100644 --- /dev/null +++ b/lld/wasm/FunctionSplitter.h @@ -0,0 +1,25 @@ +#ifndef LLD_WASM_FUNCTION_SPLITTER_H +#define LLD_WASM_FUNCTION_SPLITTER_H + +#include "SplitStrategy.h" + +#include +#include +#include + +namespace lld::wasm { + +class FunctionSplitter { +public: + FunctionSplitter(std::unique_ptr strategy) + : split_strategy_(std::move(strategy)) {} + + SplitStrategy::SplittedFunctions split() { return split_strategy_->split(); } + +private: + std::unique_ptr split_strategy_; +}; + +} // namespace lld::wasm + +#endif diff --git a/lld/wasm/SplitApplyDataRelocsStrategy.h b/lld/wasm/SplitApplyDataRelocsStrategy.h new file mode 100644 --- /dev/null +++ b/lld/wasm/SplitApplyDataRelocsStrategy.h @@ -0,0 +1,30 @@ +#ifndef LLD_WASM_SPLIT_APPLY_DATA_RELOCS_STRATEGY_H +#define LLD_WASM_SPLIT_APPLY_DATA_RELOCS_STRATEGY_H + +#include "SplitStrategy.h" + +namespace lld::wasm { + +class SplitApplyDataRelocsStrategy final : public SplitStrategy { +public: + SplitApplyDataRelocsStrategy(const std::string &functionBody); + virtual ~SplitApplyDataRelocsStrategy() = default; + + // Splits the function up into 2 functions. Cuts off the instructions + // that exceed the function size limit and put them into the second function. + // The first function calls the second one at the end. + // The last instruction that is gonna be left in the first function + // is WASM_OPCODE_I32_STORE/WASM_OPCODE_I64_STORE (+ align & offset) + SplittedFunctions split() override; + +private: + size_t findPositionToCutInstructionsFrom(unsigned instruction_opcode) const; + void addApplyDataRelocsTailCall(std::string &functionBody, size_t pos) const; + void addCutOffInstructions(std::string &functionBody, size_t pos) const; + + const std::string &function_to_split_; +}; + +} // namespace lld::wasm + +#endif diff --git a/lld/wasm/SplitApplyDataRelocsStrategy.cpp b/lld/wasm/SplitApplyDataRelocsStrategy.cpp new file mode 100644 --- /dev/null +++ b/lld/wasm/SplitApplyDataRelocsStrategy.cpp @@ -0,0 +1,69 @@ +#include "SplitApplyDataRelocsStrategy.h" +#include "Config.h" +#include "Symbols.h" +#include "WriterUtils.h" +#include "llvm/BinaryFormat/Wasm.h" +#include "llvm/Support/raw_ostream.h" + +namespace lld::wasm { + +SplitApplyDataRelocsStrategy::SplitApplyDataRelocsStrategy( + const std::string &functionBody) + : function_to_split_(functionBody) {} + +SplitApplyDataRelocsStrategy::SplittedFunctions +SplitApplyDataRelocsStrategy::split() { + if (function_to_split_.size() < config->maxFunctionSize) { + throw "The function is intented to only split functions that exceed" + "the function size limit"; + } + + using namespace llvm::wasm; + + SplittedFunctions functions; + const bool is64 = config->is64.value_or(false); + const unsigned store_opcode = + is64 ? WASM_OPCODE_I64_STORE : WASM_OPCODE_I32_STORE; + + const size_t pos = findPositionToCutInstructionsFrom(store_opcode); + addApplyDataRelocsTailCall(functions.first, pos); + addCutOffInstructions(functions.second, pos); + + return functions; +} + +size_t SplitApplyDataRelocsStrategy::findPositionToCutInstructionsFrom( + unsigned instruction_opcode) const { + // Skip some instructions to leave the place for CALL instruction and others + constexpr size_t skip_instruction_count = 10; + const size_t pos = function_to_split_.rfind( + instruction_opcode, function_to_split_.size() - config->maxFunctionSize - + skip_instruction_count); + if (pos == std::string::npos) + throw "No instruction opcode found"; + + // includes the following instructions: store + align + offset + constexpr size_t offset = 3; + + return pos + offset; +} + +void SplitApplyDataRelocsStrategy::addApplyDataRelocsTailCall( + std::string &functionBody, size_t pos) const { + llvm::raw_string_ostream first_os(functionBody); + functionBody = function_to_split_.substr(0, pos); + + writeU8(first_os, llvm::wasm::WASM_OPCODE_CALL, "CALL"); + writeUleb128(first_os, WasmSym::applyDataRelocsTail->getFunctionIndex(), + "function index"); + writeU8(first_os, llvm::wasm::WASM_OPCODE_END, "END"); +} + +void SplitApplyDataRelocsStrategy::addCutOffInstructions( + std::string &functionBody, size_t pos) const { + llvm::raw_string_ostream second_os(functionBody); + writeUleb128(second_os, 0, "num locals"); + functionBody.append(function_to_split_.substr(pos)); +} + +} // namespace lld::wasm diff --git a/lld/wasm/SplitStrategy.h b/lld/wasm/SplitStrategy.h new file mode 100644 --- /dev/null +++ b/lld/wasm/SplitStrategy.h @@ -0,0 +1,19 @@ +#ifndef LLD_WASM_SPLIT_STRATEGY_H +#define LLD_WASM_SPLIT_STRATEGY_H + +#include +#include + +namespace lld::wasm { + +class SplitStrategy { +public: + using SplittedFunctions = std::pair; + + virtual ~SplitStrategy() = default; + virtual SplittedFunctions split() = 0; +}; + +} // namespace lld::wasm + +#endif diff --git a/lld/wasm/Symbols.h b/lld/wasm/Symbols.h --- a/lld/wasm/Symbols.h +++ b/lld/wasm/Symbols.h @@ -573,6 +573,15 @@ // Function that applies relocations to data segment post-instantiation. static DefinedFunction *applyDataRelocs; + // __wasm_apply_data_relocs_tail + // __wasm_apply_data_relocs can grow drastically exceeding the function + // size limit. In that case, we split it up into 2 functions, so that + // the extra number of instructions go to applyDataRelocsTail. + // This function is called only from applyDataRelocs and only if + // the latter exceeds the function size limit. The rest of the time this + // function is empty. + static DefinedFunction *applyDataRelocsTail; + // __wasm_apply_global_relocs // Function that applies relocations to wasm globals post-instantiation. // Unlike __wasm_apply_data_relocs this needs to run on every thread. diff --git a/lld/wasm/Symbols.cpp b/lld/wasm/Symbols.cpp --- a/lld/wasm/Symbols.cpp +++ b/lld/wasm/Symbols.cpp @@ -76,6 +76,7 @@ DefinedFunction *WasmSym::callDtors; DefinedFunction *WasmSym::initMemory; DefinedFunction *WasmSym::applyDataRelocs; +DefinedFunction *WasmSym::applyDataRelocsTail; DefinedFunction *WasmSym::applyGlobalRelocs; DefinedFunction *WasmSym::applyGlobalTLSRelocs; DefinedFunction *WasmSym::initTLS; diff --git a/lld/wasm/Writer.cpp b/lld/wasm/Writer.cpp --- a/lld/wasm/Writer.cpp +++ b/lld/wasm/Writer.cpp @@ -8,12 +8,14 @@ #include "Writer.h" #include "Config.h" +#include "FunctionSplitter.h" #include "InputChunks.h" #include "InputElement.h" #include "MapFile.h" #include "OutputSections.h" #include "OutputSegment.h" #include "Relocations.h" +#include "SplitApplyDataRelocsStrategy.h" #include "SymbolTable.h" #include "SyntheticSections.h" #include "WriterUtils.h" @@ -68,6 +70,8 @@ void createCommandExportWrappers(); void createCommandExportWrapper(uint32_t functionIndex, DefinedFunction *f); + std::string createEmptyFunctionBody() const; + void assignIndexes(); void populateSymtab(); void populateProducers(); @@ -1338,7 +1342,26 @@ writeU8(os, WASM_OPCODE_END, "END"); } - createFunction(WasmSym::applyDataRelocs, bodyContent); + if (bodyContent.size() < config->maxFunctionSize) { + createFunction(WasmSym::applyDataRelocs, bodyContent); + createFunction(WasmSym::applyDataRelocsTail, createEmptyFunctionBody()); + } else { + FunctionSplitter splitter( + std::make_unique(bodyContent)); + auto &&[firstFunctionBody, secondFunctionBody] = splitter.split(); + createFunction(WasmSym::applyDataRelocs, firstFunctionBody); + createFunction(WasmSym::applyDataRelocsTail, secondFunctionBody); + } +} + +std::string Writer::createEmptyFunctionBody() const { + std::string bodyContent; + raw_string_ostream os(bodyContent); + + writeUleb128(os, 0, "num locals"); + writeU8(os, WASM_OPCODE_END, "END"); + + return bodyContent; } // Similar to createApplyDataRelocationsFunction but generates relocation code