diff options
| -rw-r--r-- | src/ir/ExpressionAnalyzer.cpp | 18 | ||||
| -rw-r--r-- | src/ir/hashed.h | 26 | ||||
| -rw-r--r-- | src/ir/utils.h | 10 | ||||
| -rw-r--r-- | src/passes/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/passes/MergeSimilarFunctions.cpp | 627 | ||||
| -rw-r--r-- | src/passes/pass.cpp | 10 | ||||
| -rw-r--r-- | src/passes/passes.h | 1 | ||||
| -rw-r--r-- | test/lit/help/wasm-opt.test | 3 | ||||
| -rw-r--r-- | test/lit/help/wasm2js.test | 3 | ||||
| -rw-r--r-- | test/lit/passes/merge-similar-functions.wast | 447 | ||||
| -rw-r--r-- | test/lit/passes/merge-similar-functions_all-features.wast | 90 |
11 files changed, 1225 insertions, 11 deletions
diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp index a4b1efde1..acd446acc 100644 --- a/src/ir/ExpressionAnalyzer.cpp +++ b/src/ir/ExpressionAnalyzer.cpp @@ -262,7 +262,10 @@ struct Hasher { std::map<Name, Index> internalNames; ExpressionStack stack; - Hasher(Expression* curr, bool visitChildren) : visitChildren(visitChildren) { + Hasher(Expression* curr, + bool visitChildren, + ExpressionAnalyzer::ExprHasher custom) + : visitChildren(visitChildren) { stack.push_back(curr); // DELEGATE_CALLER_TARGET is a fake target used to denote delegating to // the caller. Add it here to prevent the unknown name error. @@ -287,7 +290,11 @@ struct Hasher { // call_imports type, etc. The simplest thing is just to hash the // type for all of them. rehash(digest, curr->type.getID()); - // Hash the contents of the expression. + // If the custom hasher handled this expr, then we have nothing to do. + if (custom(curr, digest)) { + continue; + } + // Hash the contents of the expression normally. hashExpression(curr); } } @@ -365,12 +372,13 @@ struct Hasher { } // anonymous namespace -size_t ExpressionAnalyzer::hash(Expression* curr) { - return Hasher(curr, true).digest; +size_t ExpressionAnalyzer::flexibleHash(Expression* curr, + ExpressionAnalyzer::ExprHasher custom) { + return Hasher(curr, true, custom).digest; } size_t ExpressionAnalyzer::shallowHash(Expression* curr) { - return Hasher(curr, false).digest; + return Hasher(curr, false, ExpressionAnalyzer::nothingHasher).digest; } } // namespace wasm diff --git a/src/ir/hashed.h b/src/ir/hashed.h index 99488dcfb..b1fd659bc 100644 --- a/src/ir/hashed.h +++ b/src/ir/hashed.h @@ -20,6 +20,7 @@ #include "ir/utils.h" #include "support/hash.h" #include "wasm.h" +#include <functional> namespace wasm { @@ -30,9 +31,14 @@ struct FunctionHasher : public WalkerPass<PostWalker<FunctionHasher>> { struct Map : public std::map<Function*, size_t> {}; - FunctionHasher(Map* output) : output(output) {} + FunctionHasher(Map* output, ExpressionAnalyzer::ExprHasher customHasher) + : output(output), customHasher(customHasher) {} + FunctionHasher(Map* output) + : output(output), customHasher(ExpressionAnalyzer::nothingHasher) {} - FunctionHasher* create() override { return new FunctionHasher(output); } + FunctionHasher* create() override { + return new FunctionHasher(output, customHasher); + } static Map createMap(Module* module) { Map hashes; @@ -44,19 +50,29 @@ struct FunctionHasher : public WalkerPass<PostWalker<FunctionHasher>> { return hashes; } - void doWalkFunction(Function* func) { output->at(func) = hashFunction(func); } + void doWalkFunction(Function* func) { + output->at(func) = flexibleHashFunction(func, customHasher); + } - static size_t hashFunction(Function* func) { + static size_t + flexibleHashFunction(Function* func, + ExpressionAnalyzer::ExprHasher customHasher) { auto digest = hash(func->type); for (auto type : func->vars) { rehash(digest, type.getID()); } - hash_combine(digest, ExpressionAnalyzer::hash(func->body)); + hash_combine(digest, + ExpressionAnalyzer::flexibleHash(func->body, customHasher)); return digest; } + static size_t hashFunction(Function* func) { + return flexibleHashFunction(func, ExpressionAnalyzer::nothingHasher); + } + private: Map* output; + ExpressionAnalyzer::ExprHasher customHasher; }; } // namespace wasm diff --git a/src/ir/utils.h b/src/ir/utils.h index 69d5f8e63..7abc87b5e 100644 --- a/src/ir/utils.h +++ b/src/ir/utils.h @@ -82,9 +82,17 @@ struct ExpressionAnalyzer { return flexibleEqual(left, right, comparer); } + // Returns true if the expression is handled by the hasher. + using ExprHasher = std::function<bool(Expression*, size_t&)>; + static bool nothingHasher(Expression*, size_t&) { return false; } + + static size_t flexibleHash(Expression* curr, ExprHasher hasher); + // hash an expression, ignoring superficial details like specific internal // names - static size_t hash(Expression* curr); + static size_t hash(Expression* curr) { + return flexibleHash(curr, nothingHasher); + } // hash an expression, ignoring child nodes. static size_t shallowHash(Expression* curr); diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index 7e5960d4b..29c8cd526 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -53,6 +53,7 @@ set(passes_SOURCES Memory64Lowering.cpp MemoryPacking.cpp MergeBlocks.cpp + MergeSimilarFunctions.cpp MergeLocals.cpp Metrics.cpp MinifyImportsAndExports.cpp diff --git a/src/passes/MergeSimilarFunctions.cpp b/src/passes/MergeSimilarFunctions.cpp new file mode 100644 index 000000000..d6e616c10 --- /dev/null +++ b/src/passes/MergeSimilarFunctions.cpp @@ -0,0 +1,627 @@ +/* + + * Copyright 2021 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. + */ + +// +// Merge similar functions that only differs constant values (like immediate +// operand of const and call insts) by parameterization. +// Performing this pass at post-link time can merge more functions across +// objects. Inspired by Swift compiler's optimization which is derived from +// LLVM's one: +// https://github.com/apple/swift/blob/main/lib/LLVMPasses/LLVMMergeFunctions.cpp +// https://github.com/llvm/llvm-project/blob/main/llvm/docs/MergeFunctions.rst +// +// The basic idea is: +// +// 1. Group possible mergeable functions by hashing instruction kind +// 2. Create a group of mergeable functions (EquivalentClass) that can be merged +// by parameterization. The classes are collected by comparing functions on +// a pairwise basis. +// 3. Derive the parameters to be parameterized (ParamInfo) from each +// EquivalentClass. A ParamInfo contains positions of parameter use and a +// set of constant values (ConstDiff) for each functions in an +// EquivalentClass. (A parameter can be used in multiple times in a function, +// so ParamInfo contains an array of use position) +// 4. Create a shared function from a function picked from EquivalentClass and +// an array of ParamInfo. +// 5. Create thunks for each functions in an EquivalentClass. +// +// e.g. +// +// Before: +// (func $big-const-42 (result i32) +// [[many instr 1]] +// (i32.const 42) +// [[many instr 2]] +// ) +// (func $big-const-43 (result i32) +// [[many instr 1]] +// (i32.const 43) +// [[many instr 2]] +// ) +// After: +// (func $byn$mgfn-shared$big-const-42 (result i32) +// [[many instr 1]] +// (local.get $0) +// [[many instr 2]] +// ) +// (func $big-const-42 (result i32) +// (call $byn$mgfn-shared$big-const-42 +// (i32.const 42) +// ) +// ) +// (func $big-const-43 (result i32) +// (call $byn$mgfn-shared$big-const-42 +// (i32.const 43) +// ) +// ) +// +// In the above example, there is an EquivalentClass `[$big-const-42, +// $big-const-43]`, and a ParamInfo `{ values: [i32(42), i32(43)], uses: +// [location of (i32.const 42)] }` is derived. Then, clone `$big-const-42` +// replacing uses of params with local.get, and create thunks for $big-const-42 +// and $big-const-43. + +#include "ir/hashed.h" +#include "ir/manipulation.h" +#include "ir/module-utils.h" +#include "ir/names.h" +#include "ir/utils.h" +#include "opt-utils.h" +#include "pass.h" +#include "support/hash.h" +#include "support/utilities.h" +#include "wasm.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <iostream> +#include <map> +#include <memory> +#include <ostream> +#include <variant> +#include <vector> + +namespace wasm { + +// A set of constant values of an instruction different between each functions +// in an EquivalentClass +using ConstDiff = std::variant<Literals, std::vector<Name>>; + +// Describes a parameter which we create to parameterize the merged function. +struct ParamInfo { + // Actual values of the parameter ordered by the EquivalentClass's + // `functions`. + ConstDiff values; + // All uses of the parameter in the primary function. + std::vector<Expression**> uses; + + ParamInfo(ConstDiff values, std::vector<Expression**> uses) + : values(std::move(values)), uses(uses) {} + + // Returns the type of the parameter value. + Type getValueType(Module* module) const { + if (const auto literals = std::get_if<Literals>(&values)) { + return (*literals)[0].type; + } else if (auto callees = std::get_if<std::vector<Name>>(&values)) { + auto* callee = module->getFunction((*callees)[0]); + return Type(callee->getSig(), NonNullable); + } else { + WASM_UNREACHABLE("unexpected const value type"); + } + } + + // Lower the constant value at a given index to an expression + Expression* + lowerToExpression(Builder& builder, Module* module, size_t index) const { + if (const auto literals = std::get_if<Literals>(&values)) { + return builder.makeConst((*literals)[index]); + } else if (auto callees = std::get_if<std::vector<Name>>(&values)) { + auto fnName = (*callees)[index]; + auto heapType = module->getFunction(fnName)->type; + return builder.makeRefFunc(fnName, heapType); + } else { + WASM_UNREACHABLE("unexpected const value type"); + } + } +}; + +// Describes the set of functions which are considered as "equivalent" (i.e. +// only differing by some constants). +struct EquivalentClass { + // Primary function in the `functions`, which will be the base for the merged + // function. + Function* primaryFunction; + // List of functions belonging to this equivalence class. + std::vector<Function*> functions; + + EquivalentClass(Function* primaryFunction, std::vector<Function*> functions) + : primaryFunction(primaryFunction), functions(functions) {} + + bool isEligibleToMerge() { return this->functions.size() >= 2; } + + // Merge the functions in this class. + void merge(Module* module, const std::vector<ParamInfo>& params); + + bool hasMergeBenefit(Module* module, const std::vector<ParamInfo>& params); + + Function* createShared(Module* module, const std::vector<ParamInfo>& params); + + Function* replaceWithThunk(Builder& builder, + Function* target, + Function* shared, + const std::vector<ParamInfo>& params, + const std::vector<Expression*>& extraArgs); + + bool deriveParams(Module* module, + std::vector<ParamInfo>& params, + bool isIndirectionEnabled); +}; + +struct MergeSimilarFunctions : public Pass { + bool invalidatesDWARF() override { return true; } + + void run(PassRunner* runner, Module* module) override { + std::vector<EquivalentClass> classes; + collectEquivalentClasses(classes, module); + std::sort( + classes.begin(), classes.end(), [](const auto& left, const auto& right) { + return left.primaryFunction->name < right.primaryFunction->name; + }); + for (auto& clazz : classes) { + if (!clazz.isEligibleToMerge()) { + continue; + } + + std::vector<ParamInfo> params; + if (!clazz.deriveParams( + module, params, isCallIndirectionEnabled(module))) { + continue; + } + + if (!clazz.hasMergeBenefit(module, params)) { + continue; + } + + clazz.merge(module, params); + } + } + + // Parameterize direct calls if the module supports func ref values. + bool isCallIndirectionEnabled(Module* module) const { + return module->features.hasReferenceTypes() && + module->features.hasTypedFunctionReferences(); + } + bool areInEquvalentClass(Function* lhs, Function* rhs, Module* module); + void collectEquivalentClasses(std::vector<EquivalentClass>& classes, + Module* module); +}; + +// Determine if two functions are equivalent ignoring constants. +bool MergeSimilarFunctions::areInEquvalentClass(Function* lhs, + Function* rhs, + Module* module) { + if (lhs->imported() || rhs->imported()) { + return false; + } + if (lhs->type != rhs->type) { + return false; + } + if (lhs->getNumVars() != rhs->getNumVars()) { + return false; + } + + ExpressionAnalyzer::ExprComparer comparer = [&](Expression* lhsExpr, + Expression* rhsExpr) { + if (lhsExpr->_id != rhsExpr->_id) { + return false; + } + if (lhsExpr->type != rhsExpr->type) { + return false; + } + if (lhsExpr->is<Call>()) { + if (!this->isCallIndirectionEnabled(module)) { + return false; + } + auto lhsCast = lhsExpr->dynCast<Call>(); + auto rhsCast = rhsExpr->dynCast<Call>(); + if (lhsCast->operands.size() != rhsCast->operands.size()) { + return false; + } + if (lhsCast->type != rhsCast->type) { + return false; + } + auto* lhsCallee = module->getFunction(lhsCast->target); + auto* rhsCallee = module->getFunction(rhsCast->target); + if (lhsCallee->getSig() != rhsCallee->getSig()) { + return false; + } + + // Arguments operands should be also equivalent ignoring constants. + for (Index i = 0; i < lhsCast->operands.size(); i++) { + if (!ExpressionAnalyzer::flexibleEqual( + lhsCast->operands[i], rhsCast->operands[i], comparer)) { + return false; + } + } + return true; + } + + if (lhsExpr->is<Const>()) { + auto lhsCast = lhsExpr->dynCast<Const>(); + auto rhsCast = rhsExpr->dynCast<Const>(); + // Types should be the same at least. + if (lhsCast->value.type != rhsCast->value.type) { + return false; + } + return true; + } + + return false; + }; + if (!ExpressionAnalyzer::flexibleEqual(lhs->body, rhs->body, comparer)) { + return false; + } + + return true; +} + +// Collect all equivalent classes to be merged. +void MergeSimilarFunctions::collectEquivalentClasses( + std::vector<EquivalentClass>& classes, Module* module) { + auto hashes = FunctionHasher::createMap(module); + PassRunner runner(module); + + std::function<bool(Expression*, size_t&)> ignoringConsts = + [&](Expression* expr, size_t& digest) { + // Ignore const's immediate operands. + if (expr->is<Const>()) { + return true; + } + // Ignore callee operands. + if (auto* call = expr->dynCast<Call>()) { + for (auto operand : call->operands) { + rehash(digest, + ExpressionAnalyzer::flexibleHash(operand, ignoringConsts)); + } + rehash(digest, call->isReturn); + return true; + } + return false; + }; + FunctionHasher(&hashes, ignoringConsts).run(&runner, module); + + // Find hash-equal groups. + std::map<size_t, std::vector<Function*>> hashGroups; + ModuleUtils::iterDefinedFunctions( + *module, [&](Function* func) { hashGroups[hashes[func]].push_back(func); }); + + for (auto& [_, hashGroup] : hashGroups) { + if (hashGroup.size() < 2) { + continue; + } + + // Collect exactly equivalent functions ignoring constants. + std::vector<EquivalentClass> classesInGroup = { + EquivalentClass(hashGroup[0], {hashGroup[0]})}; + + for (Index i = 1; i < hashGroup.size(); i++) { + auto* func = hashGroup[i]; + bool found = false; + for (auto& newClass : classesInGroup) { + if (areInEquvalentClass(newClass.primaryFunction, func, module)) { + newClass.functions.push_back(func); + found = true; + break; + } + } + + if (!found) { + // Same hash but different instruction pattern. + classesInGroup.push_back(EquivalentClass(func, {func})); + } + } + std::copy(classesInGroup.begin(), + classesInGroup.end(), + std::back_inserter(classes)); + } +} + +// Find the set of parameters which are required to merge the functions in the +// class Returns false if unable to derive parameters. +bool EquivalentClass::deriveParams(Module* module, + std::vector<ParamInfo>& params, + bool isCallIndirectionEnabled) { + // Allows iteration over children of the root expression recursively. + struct DeepValueIterator { + // The DFS work list. + SmallVector<Expression**, 10> tasks; + + DeepValueIterator(Expression** root) { tasks.push_back(root); } + + void operator++() { + ChildIterator it(*tasks.back()); + tasks.pop_back(); + for (Expression*& child : it) { + tasks.push_back(&child); + } + } + + Expression*& operator*() { + assert(!empty()); + return *tasks.back(); + } + bool empty() { return tasks.empty(); } + }; + + if (primaryFunction->imported()) { + return false; + } + DeepValueIterator primaryIt(&primaryFunction->body); + std::vector<DeepValueIterator> siblingIterators; + // Skip the first function, as it is the primary function to compare the + // primary function with the other functions based on the primary instr type. + assert(functions.size() >= 2); + for (auto func = functions.begin() + 1; func != functions.end(); ++func) { + siblingIterators.emplace_back(&(*func)->body); + } + + for (; !primaryIt.empty(); ++primaryIt) { + Expression*& primary = *primaryIt; + ConstDiff diff; + Literals values; + std::vector<Name> names; + + bool isAllSame = true; + if (auto* primaryConst = primary->dynCast<Const>()) { + values.push_back(primaryConst->value); + for (auto& it : siblingIterators) { + Expression*& sibling = *it; + ++it; + if (auto* siblingConst = sibling->dynCast<Const>()) { + isAllSame &= primaryConst->value == siblingConst->value; + values.push_back(siblingConst->value); + } else { + WASM_UNREACHABLE( + "all sibling functions should have the same instruction type"); + } + } + diff = values; + } else if (isCallIndirectionEnabled && primary->is<Call>()) { + auto* primaryCall = primary->dynCast<Call>(); + names.push_back(primaryCall->target); + for (auto& it : siblingIterators) { + Expression*& sibling = *it; + ++it; + if (auto* siblingCall = sibling->dynCast<Call>()) { + isAllSame &= primaryCall->target == siblingCall->target; + names.push_back(siblingCall->target); + } else { + WASM_UNREACHABLE( + "all sibling functions should have the same instruction type"); + } + } + diff = names; + } else { + // Skip non-constant expressions, which are ensured to be the exactly + // same. + for (auto& it : siblingIterators) { + // Sibling functions in a class should have the same instruction type. + assert((*it)->_id == primary->_id); + ++it; + } + continue; + } + // If all values are the same, skip to parameterize it. + if (isAllSame) { + continue; + } + // If the derived param is already in the params, reuse it. + // e.g. + // + // ``` + // (func $use-42-twice (result i32) + // (i32.add (i32.const 42) (i32.const 42)) + // ) + // (func $use-43-twice (result i32) + // (i32.add (i32.const 43) (i32.const 43)) + // ) + // ``` + // + // will be merged reusing the parameter [42, 43] + // + // ``` + // (func $use-42-twice (result i32) + // (call $byn$mgfn-shared$use-42-twice (i32.const 42)) + // ) + // (func $use-43-twice (result i32) + // (call $byn$mgfn-shared$use-42-twice (i32.const 43)) + // ) + // (func $byn$mgfn-shared$use-42-twice (param $0 i32) (result i32) + // (i32.add (local.get $0) (local.get $0)) + // ) + // ``` + // + bool paramReused = false; + for (auto& param : params) { + if (param.values == diff) { + param.uses.push_back(&primary); + paramReused = true; + break; + } + } + if (!paramReused) { + params.push_back(ParamInfo(diff, {&primary})); + } + } + return true; +} + +void EquivalentClass::merge(Module* module, + const std::vector<ParamInfo>& params) { + Function* sharedFn = createShared(module, params); + for (size_t i = 0; i < functions.size(); ++i) { + Builder builder(*module); + auto* func = functions[i]; + std::vector<Expression*> extraArgs; + for (auto& param : params) { + extraArgs.push_back(param.lowerToExpression(builder, module, i)); + } + replaceWithThunk(builder, func, sharedFn, params, extraArgs); + } + return; +} + +// Determine if it's beneficial to merge the functions in the class +// Merging functions by creating a shared function and thunks is not always +// beneficial. If the functions are very small, added glue code may be larger +// than the reduced size. +bool EquivalentClass::hasMergeBenefit(Module* module, + const std::vector<ParamInfo>& params) { + size_t funcCount = functions.size(); + Index exprSize = Measurer::measure(primaryFunction->body); + size_t thunkCount = funcCount; + // -1 for cloned primary func + size_t removedInstrs = (funcCount - 1) * exprSize; + // Each thunks will add local.get and call instructions to forward the params + // and pass extra parameterized values. + size_t addedInstrsPerThunk = + thunkCount * ( + // call + 1 + + // local.get + primaryFunction->getParams().size() + params.size()); + + constexpr size_t INSTR_WEIGHT = 1; + constexpr size_t CODE_SEC_LOCALS_WEIGHT = 1; + constexpr size_t CODE_SEC_ENTRY_WEIGHT = 2; + constexpr size_t FUNC_SEC_ENTRY_WEIGHT = 2; + + // Glue instrs for thunks and a merged function entry will be added by the + // merge. + size_t negativeScore = + addedInstrsPerThunk * INSTR_WEIGHT + + thunkCount * ( + // Locals entries in merged function in code section. + (params.size() * CODE_SEC_LOCALS_WEIGHT) + + // Code size field in merged function entry. + CODE_SEC_ENTRY_WEIGHT) + + // Thunk function entries in function section. + (thunkCount * FUNC_SEC_ENTRY_WEIGHT); + size_t positiveScore = INSTR_WEIGHT * removedInstrs; + return negativeScore < positiveScore; +} + +Function* EquivalentClass::createShared(Module* module, + const std::vector<ParamInfo>& params) { + Name fnName = Names::getValidFunctionName( + *module, std::string("byn$mgfn-shared$") + primaryFunction->name.str); + Builder builder(*module); + std::vector<Type> sigParams; + Index extraParamBase = primaryFunction->getNumParams(); + Index newVarBase = primaryFunction->getNumParams() + params.size(); + + for (const auto& param : primaryFunction->getParams()) { + sigParams.push_back(param); + } + for (const auto& param : params) { + sigParams.push_back(param.getValueType(module)); + } + + Signature sig(Type(sigParams), primaryFunction->getResults()); + // Cloning the primary function while replacing the parameterized values + ExpressionManipulator::CustomCopier copier = + [&](Expression* expr) -> Expression* { + if (!expr) { + return nullptr; + } + // Replace the use of the parameter with extra locals + for (Index paramIdx = 0; paramIdx < params.size(); paramIdx++) { + for (auto& use : params[paramIdx].uses) { + if (*use != expr) { + continue; + } + auto* paramExpr = builder.makeLocalGet( + extraParamBase + paramIdx, params[paramIdx].getValueType(module)); + if (expr->is<Const>()) { + return paramExpr; + } else if (auto* call = expr->cast<Call>()) { + ExpressionList operands(module->allocator); + // Clone the children of the call + for (auto* operand : call->operands) { + operands.push_back( + ExpressionManipulator::flexibleCopy(operand, *module, copier)); + } + return builder.makeCallRef(paramExpr, operands, call->type); + } + } + } + // Re-number local indices of variables (not params) to offset for the extra + // params + if (auto* localGet = expr->dynCast<LocalGet>()) { + if (primaryFunction->isVar(localGet->index)) { + localGet->index = + newVarBase + (localGet->index - primaryFunction->getNumParams()); + localGet->finalize(); + return localGet; + } + } + if (auto* localSet = expr->dynCast<LocalSet>()) { + if (primaryFunction->isVar(localSet->index)) { + auto operand = + ExpressionManipulator::flexibleCopy(localSet->value, *module, copier); + localSet->index = + newVarBase + (localSet->index - primaryFunction->getNumParams()); + localSet->value = operand; + localSet->finalize(); + return localSet; + } + } + return nullptr; + }; + Expression* body = + ExpressionManipulator::flexibleCopy(primaryFunction->body, *module, copier); + auto vars = primaryFunction->vars; + std::unique_ptr<Function> f = + builder.makeFunction(fnName, sig, std::move(vars), body); + return module->addFunction(std::move(f)); +} + +Function* +EquivalentClass::replaceWithThunk(Builder& builder, + Function* target, + Function* shared, + const std::vector<ParamInfo>& params, + const std::vector<Expression*>& extraArgs) { + std::vector<Expression*> callOperands; + Type targetParams = target->getParams(); + for (Index i = 0; i < targetParams.size(); i++) { + callOperands.push_back(builder.makeLocalGet(i, targetParams[i])); + } + + for (const auto& value : extraArgs) { + callOperands.push_back(value); + } + + auto ret = builder.makeCall(shared->name, callOperands, target->getResults()); + target->vars.clear(); + target->body = ret; + return target; +} + +Pass* createMergeSimilarFunctionsPass() { return new MergeSimilarFunctions(); } + +} // namespace wasm diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index 9158f22dd..3ac4485e3 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -227,6 +227,9 @@ void PassRegistry::registerPasses() { createMemoryPackingPass); registerPass( "merge-blocks", "merges blocks to their parents", createMergeBlocksPass); + registerPass("merge-similar-functions", + "merges similar functions when benefical", + createMergeSimilarFunctionsPass); registerPass( "merge-locals", "merges locals when beneficial", createMergeLocalsPass); registerPass("metrics", "reports metrics", createMetricsPass); @@ -565,9 +568,16 @@ void PassRunner::addDefaultGlobalOptimizationPostPasses() { if (options.optimizeLevel >= 2 || options.shrinkLevel >= 2) { addIfNoDWARFIssues("inlining-optimizing"); } + // Optimizations show more functions as duplicate, so run this here in Post. addIfNoDWARFIssues("duplicate-function-elimination"); addIfNoDWARFIssues("duplicate-import-elimination"); + + // perform after the number of functions is reduced by inlining-optimizing + if (options.shrinkLevel >= 2) { + addIfNoDWARFIssues("merge-similar-functions"); + } + if (options.optimizeLevel >= 2 || options.shrinkLevel >= 2) { addIfNoDWARFIssues("simplify-globals-optimizing"); } else { diff --git a/src/passes/passes.h b/src/passes/passes.h index 501edccc7..a703e872f 100644 --- a/src/passes/passes.h +++ b/src/passes/passes.h @@ -71,6 +71,7 @@ Pass* createLoopInvariantCodeMotionPass(); Pass* createMemory64LoweringPass(); Pass* createMemoryPackingPass(); Pass* createMergeBlocksPass(); +Pass* createMergeSimilarFunctionsPass(); Pass* createMergeLocalsPass(); Pass* createMinifiedPrinterPass(); Pass* createMinifyImportsPass(); diff --git a/test/lit/help/wasm-opt.test b/test/lit/help/wasm-opt.test index 8a752c8be..183106e4d 100644 --- a/test/lit/help/wasm-opt.test +++ b/test/lit/help/wasm-opt.test @@ -225,6 +225,9 @@ ;; CHECK-NEXT: ;; CHECK-NEXT: --merge-locals merges locals when beneficial ;; CHECK-NEXT: +;; CHECK-NEXT: --merge-similar-functions merges similar functions when +;; CHECK-NEXT: benefical +;; CHECK-NEXT: ;; CHECK-NEXT: --metrics reports metrics ;; CHECK-NEXT: ;; CHECK-NEXT: --minify-imports minifies import names (only diff --git a/test/lit/help/wasm2js.test b/test/lit/help/wasm2js.test index f24f348a7..0b03efa27 100644 --- a/test/lit/help/wasm2js.test +++ b/test/lit/help/wasm2js.test @@ -187,6 +187,9 @@ ;; CHECK-NEXT: ;; CHECK-NEXT: --merge-locals merges locals when beneficial ;; CHECK-NEXT: +;; CHECK-NEXT: --merge-similar-functions merges similar functions when +;; CHECK-NEXT: benefical +;; CHECK-NEXT: ;; CHECK-NEXT: --metrics reports metrics ;; CHECK-NEXT: ;; CHECK-NEXT: --minify-imports minifies import names (only diff --git a/test/lit/passes/merge-similar-functions.wast b/test/lit/passes/merge-similar-functions.wast new file mode 100644 index 000000000..8fb2c5d13 --- /dev/null +++ b/test/lit/passes/merge-similar-functions.wast @@ -0,0 +1,447 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited. +;; RUN: foreach %s %t wasm-opt --enable-reference-types --enable-typed-function-references --merge-similar-functions -S -o - | filecheck %s + +(module + ;; CHECK: (func $big-const-42 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$big-const-42 + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $big-const-42 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (i32.const 42) + ) + + ;; same as $big-const-42, but the set of $big-const-* derives {42, 42, 43} params + ;; CHECK: (func $big-const-42-1 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$big-const-42 + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $big-const-42-1 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (i32.const 42) + ) + ;; CHECK: (func $big-const-43 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$big-const-42 + ;; CHECK-NEXT: (i32.const 43) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $big-const-43 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (i32.const 43) + ) + + ;; CHECK: (func $small-const-44 (result i32) + ;; CHECK-NEXT: (i32.const 44) + ;; CHECK-NEXT: ) + (func $small-const-44 (result i32) + (i32.const 44) + ) + ;; CHECK: (func $small-const-45 (result i32) + ;; CHECK-NEXT: (i32.const 45) + ;; CHECK-NEXT: ) + (func $small-const-45 (result i32) + (i32.const 45) + ) + + ;; CHECK: (func $byn$mgfn-shared$big-const-42 (param $0 i32) (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: ) +) + +;; offset locals for extra params +(module + ;; CHECK: (func $take-param-and-local-0 (param $0 i32) (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$take-param-and-local-0 + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $take-param-and-local-0 (param $0 i32) (result i32) + (local $1 i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (i32.add (i32.add (i32.const 42) (local.get $0)) (local.get $1)) + ) + ;; CHECK: (func $take-param-and-local-1 (param $0 i32) (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$take-param-and-local-0 + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: (i32.const 43) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $take-param-and-local-1 (param $0 i32) (result i32) + (local $1 i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (i32.add (i32.add (i32.const 43) (local.get $0)) (local.get $1)) + ) + + ;; CHECK: (func $byn$mgfn-shared$take-param-and-local-0 (param $0 i32) (param $1 i32) (result i32) + ;; CHECK-NEXT: (local $2 i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) +) + +;; different callees +(module + ;; CHECK: (func $callee-0 (result i32) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + (func $callee-0 (result i32) (i32.const 0)) + ;; CHECK: (func $callee-1 (result i32) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + (func $callee-1 (result i32) (i32.const 1)) + ;; CHECK: (func $callee-2 (result i32) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + (func $callee-2 (result i32) (i32.const 2)) + + ;; CHECK: (func $callee-take-arg-0 (param $0 i32) (result i32) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + (func $callee-take-arg-0 (param i32) (result i32) (i32.const 0)) + ;; CHECK: (func $callee-take-arg-1 (param $0 i32) (result i32) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + (func $callee-take-arg-1 (param i32) (result i32) (i32.const 1)) + ;; CHECK: (func $callee-take-arg-2 (param $0 i32) (result i32) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + (func $callee-take-arg-2 (param i32) (result i32) (i32.const 2)) + + ;; CHECK: (func $yes-call-callee-0 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$yes-call-callee-0 + ;; CHECK-NEXT: (ref.func $callee-0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $yes-call-callee-0 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $callee-0) + ) + ;; CHECK: (func $yes-call-callee-1 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$yes-call-callee-0 + ;; CHECK-NEXT: (ref.func $callee-1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $yes-call-callee-1 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $callee-1) + ) + ;; CHECK: (func $yes-call-callee-2 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$yes-call-callee-0 + ;; CHECK-NEXT: (ref.func $callee-2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $yes-call-callee-2 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $callee-2) + ) + + + ;; CHECK: (func $yes-call-callee-take-arg-0 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$yes-call-callee-take-arg-0 + ;; CHECK-NEXT: (ref.func $callee-take-arg-0) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $yes-call-callee-take-arg-0 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $callee-take-arg-0 (i32.const 0)) + ) + ;; CHECK: (func $yes-call-callee-take-arg-1 (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$yes-call-callee-take-arg-0 + ;; CHECK-NEXT: (ref.func $callee-take-arg-1) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $yes-call-callee-take-arg-1 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $callee-take-arg-1 (i32.const 1)) + ) + + + ;; NOTE: calls with different argument expressions are not mergeable + + ;; CHECK: (func $no-call-callee-take-arg-0 (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $callee-take-arg-0 + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $no-call-callee-take-arg-0 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $callee-take-arg-0 + (block (result i32) + (drop (i32.const 0)) + (i32.const 0) + ) + ) + ) + ;; CHECK: (func $no-call-callee-take-arg-1 (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $callee-take-arg-1 + ;; CHECK-NEXT: (block $block (result i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $no-call-callee-take-arg-1 (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $callee-take-arg-1 + (block (result i32) + (drop (i32.const 0)) + (drop (i32.const 0)) + (i32.const 0) + ) + ) + ) + + ;; CHECK: (func $byn$mgfn-shared$yes-call-callee-0 (param $0 (ref $none_=>_i32)) (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call_ref + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) +) + +(module + ;; CHECK: (func $use-42-twice (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$use-42-twice + ;; CHECK-NEXT: (i32.const 42) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $use-42-twice (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (i32.add + (i32.const 42) + (i32.const 42) + ) + ) + ;; CHECK: (func $use-43-twice (result i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$use-42-twice + ;; CHECK-NEXT: (i32.const 43) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $use-43-twice (result i32) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (i32.add + (i32.const 43) + (i32.const 43) + ) + ) + + ;; CHECK: (func $byn$mgfn-shared$use-42-twice (param $0 i32) (result i32) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) +) + +(module + ;; CHECK: (func $yes-offset-local-indices-1 (param $a i32) (param $b i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$yes-offset-local-indices-1 + ;; CHECK-NEXT: (local.get $a) + ;; CHECK-NEXT: (local.get $b) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $yes-offset-local-indices-1 (param $a i32) (param $b i32) + (local $x i32) + (local $y i32) + (drop (local.get $a)) + (drop (local.get $b)) + (drop (local.get $x)) + (drop (local.get $y)) + (drop (local.tee $x (local.get $x))) + (drop (local.tee $y (local.get $y))) + (drop (local.tee $a (local.get $a))) + (drop (local.tee $b (local.get $b))) + (drop (i32.const 1)) + ) + ;; CHECK: (func $yes-offset-local-indices-2 (param $a i32) (param $b i32) + ;; CHECK-NEXT: (call $byn$mgfn-shared$yes-offset-local-indices-1 + ;; CHECK-NEXT: (local.get $a) + ;; CHECK-NEXT: (local.get $b) + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $yes-offset-local-indices-2 (param $a i32) (param $b i32) + (local $x i32) + (local $y i32) + (drop (local.get $a)) + (drop (local.get $b)) + (drop (local.get $x)) + (drop (local.get $y)) + (drop (local.tee $x (local.get $x))) + (drop (local.tee $y (local.get $y))) + (drop (local.tee $a (local.get $a))) + (drop (local.tee $b (local.get $b))) + (drop (i32.const 2)) + ) + + ;; CHECK: (func $byn$mgfn-shared$yes-offset-local-indices-1 (param $0 i32) (param $1 i32) (param $2 i32) + ;; CHECK-NEXT: (local $3 i32) + ;; CHECK-NEXT: (local $4 i32) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $4) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $3 + ;; CHECK-NEXT: (local.get $3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $4 + ;; CHECK-NEXT: (local.get $4) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $0 + ;; CHECK-NEXT: (local.get $0) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.tee $1 + ;; CHECK-NEXT: (local.get $1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (local.get $2) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) +) diff --git a/test/lit/passes/merge-similar-functions_all-features.wast b/test/lit/passes/merge-similar-functions_all-features.wast new file mode 100644 index 000000000..deda3b36b --- /dev/null +++ b/test/lit/passes/merge-similar-functions_all-features.wast @@ -0,0 +1,90 @@ +;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited. +;; RUN: foreach %s %t wasm-opt --all-features --merge-similar-functions -S -o - | filecheck %s + +(module + ;; CHECK: (type $[i8] (array i8)) + (type $[i8] (array i8)) + + ;; CHECK: (func $take-ref-null-data (param $0 (ref null data)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $take-ref-null-data (param (ref null data)) + (unreachable) + ) + ;; CHECK: (func $take-ref-eq (param $0 (ref eq)) + ;; CHECK-NEXT: (unreachable) + ;; CHECK-NEXT: ) + (func $take-ref-eq (param (ref eq)) + (unreachable) + ) + + ;; NOTE: When type A is a subtype of type B and type C, + ;; and func X takes a type B arg, and func Y takes a type C arg. + ;; Then both func X and Y are callable with a type A arg. + ;; But in general, type B and C don't have a common subtype, so + ;; we can't merge call instructions of func X and Y. + + ;; CHECK: (func $no-call-subtyping-same-operand-0 + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $take-ref-null-data + ;; CHECK-NEXT: (array.init_static $[i8]) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $no-call-subtyping-same-operand-0 + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $take-ref-null-data + (array.init_static $[i8]) + ) + ) + ;; CHECK: (func $no-call-subtyping-same-operand-1 + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (nop) + ;; CHECK-NEXT: (call $take-ref-eq + ;; CHECK-NEXT: (array.init_static $[i8]) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $no-call-subtyping-same-operand-1 + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (nop) (nop) (nop) (nop) (nop) (nop) + (call $take-ref-eq + (array.init_static $[i8]) + ) + ) + +) |