diff options
-rw-r--r-- | src/ir/CMakeLists.txt | 1 | ||||
-rw-r--r-- | src/ir/module-splitting.cpp | 479 | ||||
-rw-r--r-- | src/ir/module-splitting.h | 72 | ||||
-rw-r--r-- | src/ir/names.h | 4 | ||||
-rw-r--r-- | src/wasm-builder.h | 3 | ||||
-rw-r--r-- | src/wasm.h | 8 | ||||
-rw-r--r-- | src/wasm/wasm.cpp | 8 | ||||
-rw-r--r-- | test/example/module-splitting.cpp | 289 | ||||
-rw-r--r-- | test/example/module-splitting.txt | 641 |
9 files changed, 1496 insertions, 9 deletions
diff --git a/src/ir/CMakeLists.txt b/src/ir/CMakeLists.txt index 5555ef98b..e2bad94bd 100644 --- a/src/ir/CMakeLists.txt +++ b/src/ir/CMakeLists.txt @@ -5,6 +5,7 @@ set(ir_SOURCES LocalGraph.cpp ReFinalize.cpp stack-utils.cpp + module-splitting.cpp ${ir_HEADERS} ) add_library(ir OBJECT ${ir_SOURCES}) diff --git a/src/ir/module-splitting.cpp b/src/ir/module-splitting.cpp new file mode 100644 index 000000000..3b3676815 --- /dev/null +++ b/src/ir/module-splitting.cpp @@ -0,0 +1,479 @@ +/* + * Copyright 2020 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// The process of module splitting involves these steps: +// +// 1. Create the new secondary module. +// +// 2. Export globals, events, tables, and memories from the primary module and +// import them in the secondary module. +// +// 3. Move the deferred functions from the primary to the secondary module. +// +// 4. For any secondary function exported from the primary module, export in +// its place a trampoline function that makes an indirect call to its +// placeholder function (and eventually to the original secondary +// function), allocating a new table slot for the placeholder if necessary. +// +// 5. Rewrite direct calls from primary functions to secondary functions to be +// indirect calls to their placeholder functions (and eventually to their +// original secondary functions), allocating new table slots for the +// placeholders if necessary. +// +// 6. For each primary function directly called from a secondary function, +// export the primary function if it is not already exported and import it +// into the secondary module. +// +// 7. Replace all references to secondary functions in the primary module's +// table segments with references to imported placeholder functions. +// +// 8. Create new active table segments in the secondary module that will +// replace all the placeholder function references in the table with +// references to their corresponding secondary functions upon +// instantiation. +// +// Functions can be used or referenced three ways in a WebAssembly module: they +// can be exported, called, or placed in a table. The above procedure introduces +// a layer of indirection to each of those mechanisms that removes all +// references to secondary functions from the primary module but restores the +// original program's semantics once the secondary module is instantiated. As +// more mechanisms that reference functions are added in the future, such as +// ref.func instructions, they will have to be modified to use a similar layer +// of indirection. +// +// The code as currently written makes a few assumptions about the module that +// is being split: +// +// 1. It assumes that mutable-globals is allowed. This could be worked around +// by introducing wrapper functions for globals and rewriting secondary +// code that accesses them, but now that mutable-globals is shipped on all +// browsers, hopefully that extra complexity won't be necessary. +// +// 2. It assumes that all table segment offsets are constants. This simplifies +// the generation of segments to actively patch in the secondary functions +// without overwriting any other table slots. This assumption could be +// relaxed by 1) having secondary segments re-write primary function slots +// as well, 2) allowing addition in segment offsets, or 3) synthesizing a +// start function to modify the table instead of using segments. +// +// 3. It assumes that each function appears in the table at most once. This +// isn't necessarily true in general or even for LLVM output after function +// deduplication. Relaxing this assumption would just require slightly more +// complex code, so it is a good candidate for a follow up PR. + +#include "ir/module-splitting.h" +#include "ir/manipulation.h" +#include "ir/module-utils.h" +#include "ir/names.h" +#include "pass.h" +#include "wasm-builder.h" +#include "wasm.h" + +namespace wasm { + +namespace ModuleSplitting { + +namespace { + +template<class F> void forEachElement(Table& table, F f) { + for (auto& segment : table.segments) { + assert(segment.offset->is<Const>() && + "TODO: handle non-constant segment offsets"); + Index baseOffset = segment.offset->cast<Const>()->value.geti32(); + for (size_t i = 0; i < segment.data.size(); ++i) { + f(Index(baseOffset + i), segment.data[i]); + } + } +} + +struct TableSlotManager { + Module& module; + Table& table; + Table::Segment* activeSegment = nullptr; + Index activeBase = 0; + std::map<Name, Index> funcIndices; + + TableSlotManager(Module& module); + + // Returns the table index for `func`, allocating a new index if necessary. + Index getIndex(Name func); + void addIndex(Name func, Index index); +}; + +void TableSlotManager::addIndex(Name func, Index index) { + auto it = funcIndices.insert(std::make_pair(func, index)); + assert(it.second && "Function already has multiple indices"); +} + +TableSlotManager::TableSlotManager(Module& module) + : module(module), table(module.table) { + + // Finds the segment with the highest occupied table slot so that new items + // can be inserted contiguously at the end of it without accidentally + // overwriting any other items. TODO: be more clever about filling gaps in the + // table, if that is ever useful. + Index maxIndex = 0; + for (auto& segment : table.segments) { + assert(segment.offset->is<Const>() && + "TODO: handle non-constant segment offsets"); + Index segmentBase = segment.offset->cast<Const>()->value.geti32(); + if (segmentBase + segment.data.size() >= maxIndex) { + maxIndex = segmentBase + segment.data.size(); + activeSegment = &segment; + activeBase = segmentBase; + } + } + + // Initialize funcIndices with the functions already in the table. + forEachElement(table, [&](Index index, Name func) { addIndex(func, index); }); +} + +Index TableSlotManager::getIndex(Name func) { + auto indexIt = funcIndices.find(func); + if (indexIt != funcIndices.end()) { + return indexIt->second; + } + + // If there are no segments yet, allocate one. + if (activeSegment == nullptr) { + table.exists = true; + assert(table.segments.size() == 0); + table.segments.emplace_back(Builder(module).makeConst(int32_t(0))); + activeSegment = &table.segments.front(); + } + + Index newIndex = activeBase + activeSegment->data.size(); + activeSegment->data.push_back(func); + addIndex(func, newIndex); + if (table.initial <= newIndex) { + table.initial = newIndex + 1; + } + if (table.max <= newIndex) { + table.max = newIndex + 1; + } + return newIndex; +} + +struct ModuleSplitter { + const Config& config; + std::unique_ptr<Module> secondaryPtr; + + Module& primary; + Module& secondary; + + const std::pair<std::set<Name>, std::set<Name>> classifiedFuncs; + const std::set<Name>& primaryFuncs; + const std::set<Name>& secondaryFuncs; + + TableSlotManager tableManager; + + static std::unique_ptr<Module> initSecondary(const Module& primary); + static std::pair<std::set<Name>, std::set<Name>> + classifyFunctions(const Module& primary, const Config& config); + + void moveSecondaryFunctions(); + void thunkExportedSecondaryFunctions(); + void indirectCallsToSecondaryFunctions(); + void exportImportCalledPrimaryFunctions(); + void setupTablePatching(); + void shareImportableItems(); + + ModuleSplitter(Module& primary, const Config& config) + : config(config), secondaryPtr(ModuleSplitter::initSecondary(primary)), + primary(primary), secondary(*secondaryPtr), + classifiedFuncs(ModuleSplitter::classifyFunctions(primary, config)), + primaryFuncs(classifiedFuncs.first), + secondaryFuncs(classifiedFuncs.second), tableManager(primary) { + moveSecondaryFunctions(); + thunkExportedSecondaryFunctions(); + indirectCallsToSecondaryFunctions(); + exportImportCalledPrimaryFunctions(); + setupTablePatching(); + shareImportableItems(); + } +}; + +std::unique_ptr<Module> ModuleSplitter::initSecondary(const Module& primary) { + // Create the secondary module and copy trivial properties. + auto secondary = std::make_unique<Module>(); + secondary->features = primary.features; + secondary->hasFeaturesSection = primary.hasFeaturesSection; + return secondary; +} + +std::pair<std::set<Name>, std::set<Name>> +ModuleSplitter::classifyFunctions(const Module& primary, const Config& config) { + std::set<Name> primaryFuncs, secondaryFuncs; + for (auto& func : primary.functions) { + if (func->imported() || config.primaryFuncs.count(func->name)) { + primaryFuncs.insert(func->name); + } else { + assert(func->name != primary.start && "The start function must be kept"); + secondaryFuncs.insert(func->name); + } + } + return std::make_pair(primaryFuncs, secondaryFuncs); +} + +void ModuleSplitter::moveSecondaryFunctions() { + // Move the specified functions from the primary to the secondary module. + for (auto funcName : secondaryFuncs) { + auto* func = primary.getFunction(funcName); + ModuleUtils::copyFunction(func, secondary); + primary.removeFunction(funcName); + } +} + +void ModuleSplitter::thunkExportedSecondaryFunctions() { + // Update exports of secondary functions in the primary module to export + // wrapper functions that indirectly call the secondary functions. We are + // adding secondary function names to the primary table here, but they will be + // replaced with placeholder functions later along with any references to + // secondary functions that were already in the table. + Builder builder(primary); + for (auto& ex : primary.exports) { + if (ex->kind != ExternalKind::Function || + !secondaryFuncs.count(ex->value)) { + continue; + } + Name secondaryFunc = ex->value; + Index tableIndex = tableManager.getIndex(secondaryFunc); + auto func = std::make_unique<Function>(); + func->name = secondaryFunc; + func->sig = secondary.getFunction(secondaryFunc)->sig; + std::vector<Expression*> args; + for (size_t i = 0, size = func->sig.params.size(); i < size; ++i) { + args.push_back(builder.makeLocalGet(i, func->sig.params[i])); + } + func->body = builder.makeCallIndirect( + builder.makeConst(int32_t(tableIndex)), args, func->sig); + primary.addFunction(std::move(func)); + } +} + +void ModuleSplitter::indirectCallsToSecondaryFunctions() { + // Update direct calls of secondary functions to be indirect calls of their + // corresponding table indices instead. + struct CallIndirector : public WalkerPass<PostWalker<CallIndirector>> { + ModuleSplitter& parent; + Builder builder; + CallIndirector(ModuleSplitter& parent) + : parent(parent), builder(parent.primary) {} + void visitCall(Call* curr) { + if (!parent.secondaryFuncs.count(curr->target)) { + return; + } + replaceCurrent(builder.makeCallIndirect( + builder.makeConst(int32_t(parent.tableManager.getIndex(curr->target))), + curr->operands, + parent.secondary.getFunction(curr->target)->sig, + curr->isReturn)); + } + void visitRefFunc(RefFunc* curr) { + assert(false && "TODO: handle ref.func as well"); + } + }; + PassRunner runner(&primary); + CallIndirector(*this).run(&runner, &primary); +} + +void ModuleSplitter::exportImportCalledPrimaryFunctions() { + // Find primary functions called in the secondary module. + ModuleUtils::ParallelFunctionAnalysis<std::vector<Name>> callCollector( + secondary, [&](Function* func, std::vector<Name>& calledPrimaryFuncs) { + struct CallCollector : PostWalker<CallCollector> { + const std::set<Name>& primaryFuncs; + std::vector<Name>& calledPrimaryFuncs; + CallCollector(const std::set<Name>& primaryFuncs, + std::vector<Name>& calledPrimaryFuncs) + : primaryFuncs(primaryFuncs), calledPrimaryFuncs(calledPrimaryFuncs) { + } + void visitCall(Call* curr) { + if (primaryFuncs.count(curr->target)) { + calledPrimaryFuncs.push_back(curr->target); + } + } + void visitRefFunc(RefFunc* curr) { + assert(false && "TODO: handle ref.func as well"); + } + }; + CallCollector(primaryFuncs, calledPrimaryFuncs).walkFunction(func); + }); + std::set<Name> calledPrimaryFuncs; + for (auto& entry : callCollector.map) { + auto& calledFuncs = entry.second; + calledPrimaryFuncs.insert(calledFuncs.begin(), calledFuncs.end()); + } + + // Find exported primary functions and map to their export names + std::map<Name, Name> exportedPrimaryFuncs; + for (auto& ex : primary.exports) { + if (ex->kind == ExternalKind::Function) { + exportedPrimaryFuncs.insert(std::make_pair(ex->value, ex->name)); + } + } + + // Ensure each called primary function is exported and imported + for (auto primaryFunc : calledPrimaryFuncs) { + Name exportName; + auto exportIt = exportedPrimaryFuncs.find(primaryFunc); + if (exportIt != exportedPrimaryFuncs.end()) { + exportName = exportIt->second; + } else { + exportName = Names::getValidExportName( + primary, config.newExportPrefix + primaryFunc.c_str()); + primary.addExport( + new Export{exportName, primaryFunc, ExternalKind::Function}); + } + auto func = std::make_unique<Function>(); + func->module = config.importNamespace; + func->base = exportName; + func->name = primaryFunc; + func->sig = primary.getFunction(primaryFunc)->sig; + secondary.addFunction(std::move(func)); + } +} + +void ModuleSplitter::setupTablePatching() { + std::map<Index, Name> replacedElems; + // Replace table references to secondary functions with an imported + // placeholder that encodes the table index in its name: + // `importNamespace`.`index`. + forEachElement(primary.table, [&](Index index, Name& elem) { + if (secondaryFuncs.count(elem)) { + replacedElems[index] = elem; + auto* secondaryFunc = secondary.getFunction(elem); + auto placeholder = std::make_unique<Function>(); + placeholder->module = config.placeholderNamespace; + placeholder->base = std::to_string(index); + placeholder->name = Names::getValidFunctionName( + primary, + std::string("placeholder_") + std::string(placeholder->base.c_str())); + placeholder->hasExplicitName = false; + placeholder->sig = secondaryFunc->sig; + elem = placeholder->name; + primary.addFunction(std::move(placeholder)); + } + }); + + // Create active table segments in the secondary module to patch in the + // original functions when it is instantiated. + Index currBase = 0; + std::vector<Name> currData; + auto finishSegment = [&]() { + auto* offset = Builder(secondary).makeConst(int32_t(currBase)); + secondary.table.segments.emplace_back(offset, currData); + }; + if (replacedElems.size()) { + currBase = replacedElems.begin()->first; + } + for (auto curr = replacedElems.begin(); curr != replacedElems.end(); ++curr) { + if (curr->first != currBase + currData.size()) { + finishSegment(); + currBase = curr->first; + currData.clear(); + } + currData.push_back(curr->second); + } + if (currData.size()) { + finishSegment(); + } +} + +void ModuleSplitter::shareImportableItems() { + // Map internal names to (one of) their corresponding export names. Don't + // consider functions because they have already been imported and exported as + // necessary. + std::unordered_map<Name, Name> exports; + for (auto& ex : primary.exports) { + if (ex->kind != ExternalKind::Function) { + exports[ex->value] = ex->name; + } + } + + auto makeImportExport = [&](Importable& primaryItem, + Importable& secondaryItem, + const std::string& genericExportName, + ExternalKind kind) { + secondaryItem.name = primaryItem.name; + secondaryItem.hasExplicitName = primaryItem.hasExplicitName; + secondaryItem.module = config.importNamespace; + auto exportIt = exports.find(primaryItem.name); + if (exportIt != exports.end()) { + secondaryItem.base = exportIt->second; + } else { + Name exportName = Names::getValidExportName( + primary, config.newExportPrefix + genericExportName); + primary.addExport(new Export{exportName, primaryItem.name, kind}); + secondaryItem.base = exportName; + } + }; + + // TODO: Be more selective by only sharing global items that are actually used + // in the secondary module, just like we do for functions. + + if (primary.memory.exists) { + secondary.memory.exists = true; + secondary.memory.initial = primary.memory.initial; + secondary.memory.max = primary.memory.max; + secondary.memory.shared = primary.memory.shared; + secondary.memory.indexType = primary.memory.indexType; + makeImportExport( + primary.memory, secondary.memory, "memory", ExternalKind::Memory); + } + + if (primary.table.exists) { + secondary.table.exists = true; + secondary.table.initial = primary.table.initial; + secondary.table.max = primary.table.max; + makeImportExport( + primary.table, secondary.table, "table", ExternalKind::Table); + } + + for (auto& global : primary.globals) { + if (global->mutable_) { + assert(primary.features.hasMutableGlobals() && + "TODO: add wrapper functions for disallowed mutable globals"); + } + auto secondaryGlobal = std::make_unique<Global>(); + secondaryGlobal->type = global->type; + secondaryGlobal->mutable_ = global->mutable_; + secondaryGlobal->init = + global->init == nullptr + ? nullptr + : ExpressionManipulator::copy(global->init, secondary); + makeImportExport(*global, *secondaryGlobal, "global", ExternalKind::Global); + secondary.addGlobal(std::move(secondaryGlobal)); + } + + for (auto& event : primary.events) { + auto secondaryEvent = std::make_unique<Event>(); + secondaryEvent->attribute = event->attribute; + secondaryEvent->sig = event->sig; + makeImportExport(*event, *secondaryEvent, "event", ExternalKind::Event); + secondary.addEvent(std::move(secondaryEvent)); + } +} + +} // anonymous namespace + +std::unique_ptr<Module> splitFunctions(Module& primary, const Config& config) { + return std::move(ModuleSplitter(primary, config).secondaryPtr); +} + +} // namespace ModuleSplitting + +} // namespace wasm diff --git a/src/ir/module-splitting.h b/src/ir/module-splitting.h new file mode 100644 index 000000000..765a1f853 --- /dev/null +++ b/src/ir/module-splitting.h @@ -0,0 +1,72 @@ +/* + * Copyright 2020 WebAssembly Community Group participants + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +// module-splitting.h: Provides an interface for decomposing WebAssembly modules +// into multiple modules that can be loaded independently. This works by moving +// functions to a new secondary module and rewriting the primary module to call +// them indirectly. Until the secondary module is instantiated, those indirect +// calls will go to placeholder functions newly imported into the primary +// module. The import names of the placeholder functions are the table indexes +// they are placed at. The secondary module imports all of its dependencies from +// the primary module. +// +// This code currently makes a few assumptions about the modules that will be +// split and will fail assertions if those assumptions are not true. +// +// 1) It assumes that mutable-globals are allowed. +// +// 2) It assumes that all table segment offsets are constants. +// +// 3) It assumes that each function appears in the table at most once. +// +// These requirements will be relaxed as necessary in the future, but for now +// this code should be considered experimental and used with care. + +#ifndef wasm_ir_module_splitting_h +#define wasm_ir_module_splitting_h + +#include "wasm.h" + +namespace wasm { + +namespace ModuleSplitting { + +struct Config { + // The set of functions to keep in the primary module. All others are split + // out into the new secondary module. Must include the start function if it + // exists. May or may not include imported functions, which are always kept in + // the primary module regardless. + std::set<Name> primaryFuncs; + // The namespace from which to import primary functions into the secondary + // module. + Name importNamespace = "primary"; + // The namespace from which to import placeholder functions into the primary + // module. + Name placeholderNamespace = "placeholder"; + // The prefix to attach to the name of any newly created exports. This can be + // used to differentiate between "real" exports of the module and exports that + // should only be consumed by the secondary module. + std::string newExportPrefix = ""; +}; + +// Returns the new secondary module and modifies the `primary` module in place. +std::unique_ptr<Module> splitFunctions(Module& primary, const Config& config); + +} // namespace ModuleSplitting + +} // namespace wasm + +#endif // wasm_ir_module_splitting_h diff --git a/src/ir/names.h b/src/ir/names.h index a725c515a..99dd3cab7 100644 --- a/src/ir/names.h +++ b/src/ir/names.h @@ -64,6 +64,10 @@ getValidName(Module& module, Name root, std::function<bool(Name)> check) { } } +inline Name getValidExportName(Module& module, Name root) { + return getValidName( + module, root, [&](Name test) { return !module.getExportOrNull(test); }); +} inline Name getValidGlobalName(Module& module, Name root) { return getValidName( module, root, [&](Name test) { return !module.getGlobalOrNull(test); }); diff --git a/src/wasm-builder.h b/src/wasm-builder.h index 77e2692f6..75e73a834 100644 --- a/src/wasm-builder.h +++ b/src/wasm-builder.h @@ -221,8 +221,9 @@ public: call->finalize(); return call; } + template<typename T> CallIndirect* makeCallIndirect(Expression* target, - const std::vector<Expression*>& args, + const T& args, Signature sig, bool isReturn = false) { auto* call = wasm.allocator.alloc<CallIndirect>(); diff --git a/src/wasm.h b/src/wasm.h index 2f655fa7f..1204eee0f 100644 --- a/src/wasm.h +++ b/src/wasm.h @@ -1734,10 +1734,10 @@ public: Global* addGlobal(Global* curr); Event* addEvent(Event* curr); - Export* addExport(std::unique_ptr<Export> curr); - Function* addFunction(std::unique_ptr<Function> curr); - Global* addGlobal(std::unique_ptr<Global> curr); - Event* addEvent(std::unique_ptr<Event> curr); + Export* addExport(std::unique_ptr<Export>&& curr); + Function* addFunction(std::unique_ptr<Function>&& curr); + Global* addGlobal(std::unique_ptr<Global>&& curr); + Event* addEvent(std::unique_ptr<Event>&& curr); void addStart(const Name& s); diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp index bb578819b..5b4a276dd 100644 --- a/src/wasm/wasm.cpp +++ b/src/wasm/wasm.cpp @@ -1242,20 +1242,20 @@ Event* Module::addEvent(Event* curr) { return addModuleElement(events, eventsMap, curr, "addEvent"); } -Export* Module::addExport(std::unique_ptr<Export> curr) { +Export* Module::addExport(std::unique_ptr<Export>&& curr) { return addModuleElement(exports, exportsMap, std::move(curr), "addExport"); } -Function* Module::addFunction(std::unique_ptr<Function> curr) { +Function* Module::addFunction(std::unique_ptr<Function>&& curr) { return addModuleElement( functions, functionsMap, std::move(curr), "addFunction"); } -Global* Module::addGlobal(std::unique_ptr<Global> curr) { +Global* Module::addGlobal(std::unique_ptr<Global>&& curr) { return addModuleElement(globals, globalsMap, std::move(curr), "addGlobal"); } -Event* Module::addEvent(std::unique_ptr<Event> curr) { +Event* Module::addEvent(std::unique_ptr<Event>&& curr) { return addModuleElement(events, eventsMap, std::move(curr), "addEvent"); } diff --git a/test/example/module-splitting.cpp b/test/example/module-splitting.cpp new file mode 100644 index 000000000..50fb0f4c5 --- /dev/null +++ b/test/example/module-splitting.cpp @@ -0,0 +1,289 @@ +#include <cassert> +#include <iostream> + +#include "ir/module-splitting.h" +#include "ir/stack-utils.h" +#include "wasm-features.h" +#include "wasm-printing.h" +#include "wasm-s-parser.h" +#include "wasm-validator.h" +#include "wasm.h" + +using namespace wasm; + +std::unique_ptr<Module> parse(char* module) { + auto wasm = std::make_unique<Module>(); + wasm->features = FeatureSet::All; + try { + SExpressionParser parser(module); + Element& root = *parser.root; + SExpressionWasmBuilder builder(*wasm, *root[0], IRProfile::Normal); + } catch (ParseException& p) { + p.dump(std::cerr); + Fatal() << "error in parsing wasm text"; + } + return wasm; +} + +void do_test(const std::set<Name>& keptFuncs, std::string&& module) { + WasmValidator validator; + bool valid; + + auto primary = parse(&module.front()); + valid = validator.validate(*primary); + assert(valid && "before invalid!"); + + std::cout << "Before:\n"; + WasmPrinter::printModule(primary.get()); + + std::cout << "Keeping: "; + if (keptFuncs.size()) { + auto it = keptFuncs.begin(); + std::cout << *it++; + while (it != keptFuncs.end()) { + std::cout << ", " << *it++; + } + } else { + std::cout << "<none>"; + } + std::cout << "\n"; + + ModuleSplitting::Config config; + config.primaryFuncs = keptFuncs; + config.newExportPrefix = "%"; + auto secondary = splitFunctions(*primary, config); + + std::cout << "After:\n"; + WasmPrinter::printModule(primary.get()); + std::cout << "Secondary:\n"; + WasmPrinter::printModule(secondary.get()); + std::cout << "\n\n"; + + valid = validator.validate(*primary); + assert(valid && "after invalid!"); + valid = validator.validate(*secondary); + assert(valid && "secondary invalid!"); +} + +int main() { + // Trivial module + do_test({}, "(module)"); + + // Global stuff + do_test({}, R"( + (module + (memory $mem (shared 3 42)) + (table $tab 3 42 funcref) + (global $glob (mut i32) (i32.const 7)) + (event $e (attr 0) (param i32)) + ))"); + + // Imported global stuff + do_test({}, R"( + (module + (import "env" "mem" (memory $mem (shared 3 42))) + (import "env" "tab" (table $tab 3 42 funcref)) + (import "env" "glob" (global $glob (mut i32))) + (import "env" "e" (event $e (attr 0) (param i32))) + ))"); + + // Exported global stuff + do_test({}, R"( + (module + (memory $mem (shared 3 42)) + (table $tab 3 42 funcref) + (global $glob (mut i32) (i32.const 7)) + (event $e (attr 0) (param i32)) + (export "mem" (memory $mem)) + (export "tab" (table $tab)) + (export "glob" (global $glob)) + (export "e" (event $e)) + ))"); + + // Non-deferred function + do_test({"foo"}, R"( + (module + (func $foo (param i32) (result i32) + (local.get 0) + ) + ))"); + + // Non-deferred exported function + do_test({"foo"}, R"( + (module + (export "foo" (func $foo)) + (func $foo (param i32) (result i32) + (local.get 0) + ) + ))"); + + // Non-deferred function in table + do_test({"foo"}, R"( + (module + (table $table 1 funcref) + (elem (i32.const 0) $foo) + (func $foo (param i32) (result i32) + (local.get 0) + ) + ))"); + + // Non-deferred imported function + do_test({"foo"}, R"( + (module + (import "env" "foo" (func $foo (param i32) (result i32))) + ))"); + + // Non-deferred exported imported function in table at a weird offset + do_test({"foo"}, R"( + (module + (import "env" "foo" (func $foo (param i32) (result i32))) + (table $table 1000 funcref) + (elem (i32.const 42) $foo) + (export "foo" (func $foo)) + ))"); + + // Deferred function + do_test({}, R"( + (module + (func $foo (param i32) (result i32) + (local.get 0) + ) + ))"); + + // Deferred exported function + do_test({}, R"( + (module + (export "foo" (func $foo)) + (func $foo (param i32) (result i32) + (local.get 0) + ) + ))"); + + // Deferred function in table + do_test({}, R"( + (module + (table $table 1 funcref) + (elem (i32.const 0) $foo) + (func $foo (param i32) (result i32) + (local.get 0) + ) + ))"); + + // Deferred exported function in table at a weird offset + do_test({}, R"( + (module + (table $table 1000 funcref) + (elem (i32.const 42) $foo) + (export "foo" (func $foo)) + (func $foo (param i32) (result i32) + (local.get 0) + ) + ))"); + + // Non-deferred function calling non-deferred function + do_test({"foo", "bar"}, R"( + (module + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) + ))"); + + // Deferred function calling non-deferred function + do_test({"bar"}, R"( + (module + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) + ))"); + + // Non-deferred function calling deferred function + do_test({"foo"}, R"( + (module + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) + ))"); + + // Deferred function calling deferred function + do_test({}, R"( + (module + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) + ))"); + + // Deferred function calling non-deferred function with clashing export name + do_test({"foo"}, R"( + (module + (export "%foo" (func $bar)) + (func $foo + (nop) + ) + (func $bar + (call $foo) + ) + ))"); + + // Mixed table 1 + do_test({"bar", "quux"}, R"( + (module + (table $table 4 funcref) + (elem (i32.const 0) $foo $bar $baz $quux) + (func $foo + (nop) + ) + (func $bar + (nop) + ) + (func $baz + (nop) + ) + (func $quux + (nop) + ) + ))"); + + // Mixed table 2 + do_test({"baz"}, R"( + (module + (table $table 4 funcref) + (elem (i32.const 0) $foo $bar $baz $quux) + (func $foo + (nop) + ) + (func $bar + (nop) + ) + (func $baz + (nop) + ) + (func $quux + (nop) + ) + ))"); + + // Mutual recursion with table growth + do_test({"foo"}, R"( + (module + (table $table 1 1 funcref) + (elem (i32.const 0) $foo) + (func $foo (param i32) (result i32) + (call $bar (i32.const 0)) + ) + (func $bar (param i32) (result i32) + (call $foo (i32.const 1)) + ) + ))"); +} diff --git a/test/example/module-splitting.txt b/test/example/module-splitting.txt new file mode 100644 index 000000000..4d79688f7 --- /dev/null +++ b/test/example/module-splitting.txt @@ -0,0 +1,641 @@ +Before: +(module +) +Keeping: <none> +After: +(module +) +Secondary: +(module +) + + +Before: +(module + (type $i32_=>_none (func (param i32))) + (memory $mem (shared 3 42)) + (table $tab 3 42 funcref) + (global $glob (mut i32) (i32.const 7)) + (event $e (attr 0) (param i32)) +) +Keeping: <none> +After: +(module + (type $i32_=>_none (func (param i32))) + (memory $mem (shared 3 42)) + (table $tab 3 42 funcref) + (global $glob (mut i32) (i32.const 7)) + (event $e (attr 0) (param i32)) + (export "%memory" (memory $mem)) + (export "%table" (table $tab)) + (export "%global" (global $glob)) + (export "%event" (event $e)) +) +Secondary: +(module + (type $i32_=>_none (func (param i32))) + (import "primary" "%memory" (memory $mem (shared 3 42))) + (import "primary" "%table" (table $tab 3 42 funcref)) + (import "primary" "%global" (global $glob (mut i32))) + (import "primary" "%event" (event $e (attr 0) (param i32))) +) + + +Before: +(module + (type $i32_=>_none (func (param i32))) + (import "env" "mem" (memory $mem (shared 3 42))) + (import "env" "tab" (table $tab 3 42 funcref)) + (import "env" "glob" (global $glob (mut i32))) + (import "env" "e" (event $e (attr 0) (param i32))) +) +Keeping: <none> +After: +(module + (type $i32_=>_none (func (param i32))) + (import "env" "mem" (memory $mem (shared 3 42))) + (import "env" "tab" (table $tab 3 42 funcref)) + (import "env" "glob" (global $glob (mut i32))) + (import "env" "e" (event $e (attr 0) (param i32))) + (export "%memory" (memory $mem)) + (export "%table" (table $tab)) + (export "%global" (global $glob)) + (export "%event" (event $e)) +) +Secondary: +(module + (type $i32_=>_none (func (param i32))) + (import "primary" "%memory" (memory $mem (shared 3 42))) + (import "primary" "%table" (table $tab 3 42 funcref)) + (import "primary" "%global" (global $glob (mut i32))) + (import "primary" "%event" (event $e (attr 0) (param i32))) +) + + +Before: +(module + (type $i32_=>_none (func (param i32))) + (memory $mem (shared 3 42)) + (table $tab 3 42 funcref) + (global $glob (mut i32) (i32.const 7)) + (event $e (attr 0) (param i32)) + (export "mem" (memory $mem)) + (export "tab" (table $tab)) + (export "glob" (global $glob)) + (export "e" (event $e)) +) +Keeping: <none> +After: +(module + (type $i32_=>_none (func (param i32))) + (memory $mem (shared 3 42)) + (table $tab 3 42 funcref) + (global $glob (mut i32) (i32.const 7)) + (event $e (attr 0) (param i32)) + (export "mem" (memory $mem)) + (export "tab" (table $tab)) + (export "glob" (global $glob)) + (export "e" (event $e)) +) +Secondary: +(module + (type $i32_=>_none (func (param i32))) + (import "primary" "mem" (memory $mem (shared 3 42))) + (import "primary" "tab" (table $tab 3 42 funcref)) + (import "primary" "glob" (global $glob (mut i32))) + (import "primary" "e" (event $e (attr 0) (param i32))) +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Keeping: foo +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Secondary: +(module +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (export "foo" (func $foo)) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Keeping: foo +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (export "foo" (func $foo)) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Secondary: +(module +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (table $table 1 funcref) + (elem (i32.const 0) $foo) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Keeping: foo +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (table $table 1 funcref) + (elem (i32.const 0) $foo) + (export "%table" (table $table)) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Secondary: +(module + (import "primary" "%table" (table $table 1 funcref)) +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "env" "foo" (func $foo (param i32) (result i32))) +) +Keeping: foo +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "env" "foo" (func $foo (param i32) (result i32))) +) +Secondary: +(module +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "env" "foo" (func $foo (param i32) (result i32))) + (table $table 1000 funcref) + (elem (i32.const 42) $foo) + (export "foo" (func $foo)) +) +Keeping: foo +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "env" "foo" (func $foo (param i32) (result i32))) + (table $table 1000 funcref) + (elem (i32.const 42) $foo) + (export "foo" (func $foo)) + (export "%table" (table $table)) +) +Secondary: +(module + (import "primary" "%table" (table $table 1000 funcref)) +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Keeping: <none> +After: +(module +) +Secondary: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (export "foo" (func $foo)) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Keeping: <none> +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "placeholder" "0" (func $placeholder_0 (param i32) (result i32))) + (table $0 1 funcref) + (elem (i32.const 0) $placeholder_0) + (export "foo" (func $foo)) + (export "%table" (table $0)) + (func $foo (param $0 i32) (result i32) + (call_indirect (type $i32_=>_i32) + (local.get $0) + (i32.const 0) + ) + ) +) +Secondary: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "primary" "%table" (table $0 1 funcref)) + (elem (i32.const 0) $foo) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (table $table 1 funcref) + (elem (i32.const 0) $foo) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Keeping: <none> +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "placeholder" "0" (func $placeholder_0 (param i32) (result i32))) + (table $table 1 funcref) + (elem (i32.const 0) $placeholder_0) + (export "%table" (table $table)) +) +Secondary: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "primary" "%table" (table $table 1 funcref)) + (elem (i32.const 0) $foo) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (table $table 1000 funcref) + (elem (i32.const 42) $foo) + (export "foo" (func $foo)) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) +Keeping: <none> +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "placeholder" "42" (func $placeholder_42 (param i32) (result i32))) + (table $table 1000 funcref) + (elem (i32.const 42) $placeholder_42) + (export "foo" (func $foo)) + (export "%table" (table $table)) + (func $foo (param $0 i32) (result i32) + (call_indirect (type $i32_=>_i32) + (local.get $0) + (i32.const 42) + ) + ) +) +Secondary: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "primary" "%table" (table $table 1000 funcref)) + (elem (i32.const 42) $foo) + (func $foo (param $0 i32) (result i32) + (local.get $0) + ) +) + + +Before: +(module + (type $none_=>_none (func)) + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) +) +Keeping: bar, foo +After: +(module + (type $none_=>_none (func)) + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) +) +Secondary: +(module +) + + +Before: +(module + (type $none_=>_none (func)) + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) +) +Keeping: bar +After: +(module + (type $none_=>_none (func)) + (export "%bar" (func $bar)) + (func $bar + (nop) + ) +) +Secondary: +(module + (type $none_=>_none (func)) + (import "primary" "%bar" (func $bar)) + (func $foo + (call $bar) + ) +) + + +Before: +(module + (type $none_=>_none (func)) + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) +) +Keeping: foo +After: +(module + (type $none_=>_none (func)) + (import "placeholder" "0" (func $placeholder_0)) + (table $0 1 funcref) + (elem (i32.const 0) $placeholder_0) + (export "%table" (table $0)) + (func $foo + (call_indirect (type $none_=>_none) + (i32.const 0) + ) + ) +) +Secondary: +(module + (type $none_=>_none (func)) + (import "primary" "%table" (table $0 1 funcref)) + (elem (i32.const 0) $bar) + (func $bar + (nop) + ) +) + + +Before: +(module + (type $none_=>_none (func)) + (func $foo + (call $bar) + ) + (func $bar + (nop) + ) +) +Keeping: <none> +After: +(module +) +Secondary: +(module + (type $none_=>_none (func)) + (func $bar + (nop) + ) + (func $foo + (call $bar) + ) +) + + +Before: +(module + (type $none_=>_none (func)) + (export "%foo" (func $bar)) + (func $foo + (nop) + ) + (func $bar + (call $foo) + ) +) +Keeping: foo +After: +(module + (type $none_=>_none (func)) + (import "placeholder" "0" (func $placeholder_0)) + (table $0 1 funcref) + (elem (i32.const 0) $placeholder_0) + (export "%foo" (func $bar)) + (export "%foo_0" (func $foo)) + (export "%table" (table $0)) + (func $foo + (nop) + ) + (func $bar + (call_indirect (type $none_=>_none) + (i32.const 0) + ) + ) +) +Secondary: +(module + (type $none_=>_none (func)) + (import "primary" "%table" (table $0 1 funcref)) + (elem (i32.const 0) $bar) + (import "primary" "%foo_0" (func $foo)) + (func $bar + (call $foo) + ) +) + + +Before: +(module + (type $none_=>_none (func)) + (table $table 4 funcref) + (elem (i32.const 0) $foo $bar $baz $quux) + (func $foo + (nop) + ) + (func $bar + (nop) + ) + (func $baz + (nop) + ) + (func $quux + (nop) + ) +) +Keeping: bar, quux +After: +(module + (type $none_=>_none (func)) + (import "placeholder" "0" (func $placeholder_0)) + (import "placeholder" "2" (func $placeholder_2)) + (table $table 4 funcref) + (elem (i32.const 0) $placeholder_0 $bar $placeholder_2 $quux) + (export "%table" (table $table)) + (func $bar + (nop) + ) + (func $quux + (nop) + ) +) +Secondary: +(module + (type $none_=>_none (func)) + (import "primary" "%table" (table $table 4 funcref)) + (elem (i32.const 0) $foo) + (elem (i32.const 2) $baz) + (func $baz + (nop) + ) + (func $foo + (nop) + ) +) + + +Before: +(module + (type $none_=>_none (func)) + (table $table 4 funcref) + (elem (i32.const 0) $foo $bar $baz $quux) + (func $foo + (nop) + ) + (func $bar + (nop) + ) + (func $baz + (nop) + ) + (func $quux + (nop) + ) +) +Keeping: baz +After: +(module + (type $none_=>_none (func)) + (import "placeholder" "0" (func $placeholder_0)) + (import "placeholder" "1" (func $placeholder_1)) + (import "placeholder" "3" (func $placeholder_3)) + (table $table 4 funcref) + (elem (i32.const 0) $placeholder_0 $placeholder_1 $baz $placeholder_3) + (export "%table" (table $table)) + (func $baz + (nop) + ) +) +Secondary: +(module + (type $none_=>_none (func)) + (import "primary" "%table" (table $table 4 funcref)) + (elem (i32.const 0) $foo $bar) + (elem (i32.const 3) $quux) + (func $bar + (nop) + ) + (func $foo + (nop) + ) + (func $quux + (nop) + ) +) + + +Before: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (table $table 1 1 funcref) + (elem (i32.const 0) $foo) + (func $foo (param $0 i32) (result i32) + (call $bar + (i32.const 0) + ) + ) + (func $bar (param $0 i32) (result i32) + (call $foo + (i32.const 1) + ) + ) +) +Keeping: foo +After: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "placeholder" "1" (func $placeholder_1 (param i32) (result i32))) + (table $table 2 2 funcref) + (elem (i32.const 0) $foo $placeholder_1) + (export "%foo" (func $foo)) + (export "%table" (table $table)) + (func $foo (param $0 i32) (result i32) + (call_indirect (type $i32_=>_i32) + (i32.const 0) + (i32.const 1) + ) + ) +) +Secondary: +(module + (type $i32_=>_i32 (func (param i32) (result i32))) + (import "primary" "%table" (table $table 2 2 funcref)) + (elem (i32.const 1) $bar) + (import "primary" "%foo" (func $foo (param i32) (result i32))) + (func $bar (param $0 i32) (result i32) + (call $foo + (i32.const 1) + ) + ) +) + + |