diff options
| -rwxr-xr-x | build-js.sh | 4 | ||||
| -rw-r--r-- | src/passes/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/passes/DuplicateFunctionElimination.cpp | 179 | ||||
| -rw-r--r-- | src/passes/pass.cpp | 2 | ||||
| -rw-r--r-- | test/example/c-api-kitchen-sink.txt | 33 | ||||
| -rw-r--r-- | test/hello_libcxx.cpp | 8 | ||||
| -rw-r--r-- | test/passes/duplicate-function-elimination.txt | 864 | ||||
| -rw-r--r-- | test/passes/duplicate-function-elimination.wast | 702 | ||||
| -rw-r--r-- | test/unit.fromasm | 23 | ||||
| -rw-r--r-- | test/unit.fromasm.imprecise | 23 |
10 files changed, 1760 insertions, 79 deletions
diff --git a/build-js.sh b/build-js.sh index 726955a27..4643143a3 100755 --- a/build-js.sh +++ b/build-js.sh @@ -6,9 +6,9 @@ echo "building wasm.js" -em++ -std=c++11 src/wasm-js.cpp src/passes/pass.cpp src/passes/DeadCodeElimination.cpp src/passes/MergeBlocks.cpp src/passes/Print.cpp src/passes/OptimizeInstructions.cpp src/passes/RemoveUnusedBrs.cpp src/passes/RemoveUnusedNames.cpp src/passes/PostEmscripten.cpp src/passes/SimplifyLocals.cpp src/passes/ReorderLocals.cpp src/passes/Vacuum.cpp src/passes/CoalesceLocals.cpp src/emscripten-optimizer/parser.cpp src/emscripten-optimizer/simple_ast.cpp src/emscripten-optimizer/optimizer-shared.cpp src/support/colors.cpp src/support/safe_integer.cpp src/support/bits.cpp src/support/threads.cpp src/asmjs/asm_v_wasm.cpp src/asmjs/shared-constants.cpp src/wasm.cpp -Isrc/ -o bin/wasm.js -s MODULARIZE=1 -s 'EXPORT_NAME="WasmJS"' --memory-init-file 0 -Oz -s ALLOW_MEMORY_GROWTH=1 -profiling -s DEMANGLE_SUPPORT=1 #-DWASM_JS_DEBUG -DWASM_INTERPRETER_DEBUG=2 +em++ -std=c++11 src/wasm-js.cpp src/passes/pass.cpp src/passes/DeadCodeElimination.cpp src/passes/MergeBlocks.cpp src/passes/Print.cpp src/passes/OptimizeInstructions.cpp src/passes/RemoveUnusedBrs.cpp src/passes/RemoveUnusedNames.cpp src/passes/PostEmscripten.cpp src/passes/SimplifyLocals.cpp src/passes/ReorderLocals.cpp src/passes/Vacuum.cpp src/passes/DuplicateFunctionElimination.cpp src/passes/CoalesceLocals.cpp src/emscripten-optimizer/parser.cpp src/emscripten-optimizer/simple_ast.cpp src/emscripten-optimizer/optimizer-shared.cpp src/support/colors.cpp src/support/safe_integer.cpp src/support/bits.cpp src/support/threads.cpp src/asmjs/asm_v_wasm.cpp src/asmjs/shared-constants.cpp src/wasm.cpp -Isrc/ -o bin/wasm.js -s MODULARIZE=1 -s 'EXPORT_NAME="WasmJS"' --memory-init-file 0 -Oz -s ALLOW_MEMORY_GROWTH=1 -profiling -s DEMANGLE_SUPPORT=1 #-DWASM_JS_DEBUG -DWASM_INTERPRETER_DEBUG=2 echo "building binaryen.js" python ~/Dev/emscripten/tools/webidl_binder.py src/js/binaryen.idl glue -em++ -std=c++11 src/binaryen-js.cpp src/passes/pass.cpp src/passes/MergeBlocks.cpp src/passes/Print.cpp src/passes/RemoveUnusedBrs.cpp src/passes/RemoveUnusedNames.cpp src/passes/PostEmscripten.cpp src/passes/SimplifyLocals.cpp src/passes/ReorderLocals.cpp src/passes/Vacuum.cpp src/passes/CoalesceLocals.cpp src/emscripten-optimizer/parser.cpp src/emscripten-optimizer/simple_ast.cpp src/emscripten-optimizer/optimizer-shared.cpp src/support/colors.cpp src/support/safe_integer.cpp src/support/bits.cpp src/support/threads.cpp src/asmjs/asm_v_wasm.cpp src/asmjs/shared-constants.cpp src/wasm.cpp -Isrc/ -o bin/binaryen.js -s MODULARIZE=1 -s 'EXPORT_NAME="Binaryen"' --memory-init-file 0 -Oz -s ALLOW_MEMORY_GROWTH=1 -profiling -s DEMANGLE_SUPPORT=1 -s INVOKE_RUN=0 --post-js glue.js +em++ -std=c++11 src/binaryen-js.cpp src/passes/pass.cpp src/passes/MergeBlocks.cpp src/passes/Print.cpp src/passes/RemoveUnusedBrs.cpp src/passes/RemoveUnusedNames.cpp src/passes/PostEmscripten.cpp src/passes/SimplifyLocals.cpp src/passes/ReorderLocals.cpp src/passes/Vacuum.cpp src/passes/DuplicateFunctionElimination.cpp src/passes/CoalesceLocals.cpp src/emscripten-optimizer/parser.cpp src/emscripten-optimizer/simple_ast.cpp src/emscripten-optimizer/optimizer-shared.cpp src/support/colors.cpp src/support/safe_integer.cpp src/support/bits.cpp src/support/threads.cpp src/asmjs/asm_v_wasm.cpp src/asmjs/shared-constants.cpp src/wasm.cpp -Isrc/ -o bin/binaryen.js -s MODULARIZE=1 -s 'EXPORT_NAME="Binaryen"' --memory-init-file 0 -Oz -s ALLOW_MEMORY_GROWTH=1 -profiling -s DEMANGLE_SUPPORT=1 -s INVOKE_RUN=0 --post-js glue.js diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt index 0ec2686da..ab55dff85 100644 --- a/src/passes/CMakeLists.txt +++ b/src/passes/CMakeLists.txt @@ -3,6 +3,7 @@ SET(passes_SOURCES CoalesceLocals.cpp DeadCodeElimination.cpp DropReturnValues.cpp + DuplicateFunctionElimination.cpp LowerIfElse.cpp MergeBlocks.cpp Metrics.cpp diff --git a/src/passes/DuplicateFunctionElimination.cpp b/src/passes/DuplicateFunctionElimination.cpp new file mode 100644 index 000000000..593ddb7d9 --- /dev/null +++ b/src/passes/DuplicateFunctionElimination.cpp @@ -0,0 +1,179 @@ +/* + * Copyright 2016 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. + */ + +// +// Removes duplicate functions. That can happen due to C++ templates, +// and also due to types being different at the source level, but +// identical when finally lowered into concrete wasm code. +// + +#include <wasm.h> +#include <pass.h> +#include <ast_utils.h> + +namespace wasm { + +struct FunctionHasher : public PostWalker<FunctionHasher, Visitor<FunctionHasher>> { + bool isFunctionParallel() { return true; } + + FunctionHasher* create() override { + auto* ret = new FunctionHasher; + ret->setOutput(output); + return ret; + } + + void setOutput(std::map<Function*, uint32_t>* output_) { + output = output_; + } + + void walk(Expression*& root) { + assert(digest == 0); + auto* func = getFunction(); + hash(func->getNumParams()); + for (auto type : func->params) hash(type); + hash(func->getNumVars()); + for (auto type : func->vars) hash(type); + hash(func->result); + hash64(func->type.is() ? uint64_t(func->type.str) : uint64_t(0)); + hash(ExpressionAnalyzer::hash(root)); + output->at(func) = digest; + } + +private: + std::map<Function*, uint32_t>* output; + uint32_t digest = 0; + + void hash(uint32_t hash) { + digest = rehash(digest, hash); + } + void hash64(uint64_t hash) { + digest = rehash(rehash(digest, hash >> 32), uint32_t(hash)); + }; +}; + +struct FunctionReplacer : public PostWalker<FunctionReplacer, Visitor<FunctionReplacer>> { + bool isFunctionParallel() { return true; } + + FunctionReplacer* create() override { + auto* ret = new FunctionReplacer; + ret->setReplacements(replacements); + return ret; + } + + void setReplacements(std::map<Name, Name>* replacements_) { + replacements = replacements_; + } + + void visitCall(Call* curr) { + auto iter = replacements->find(curr->target); + if (iter != replacements->end()) { + curr->target = iter->second; + } + } + +private: + std::map<Name, Name>* replacements; +}; + +struct DuplicateFunctionElimination : public Pass { + void run(PassRunner* runner, Module* module) override { + while (1) { + // Hash all the functions + hashes.clear(); + for (auto& func : module->functions) { + hashes[func.get()] = 0; // ensure an entry for each function - we must not modify the map shape in parallel, just the values + } + FunctionHasher hasher; + hasher.setOutput(&hashes); + hasher.startWalk(module); + // Find hash-equal groups + std::map<uint32_t, std::vector<Function*>> hashGroups; + for (auto& func : module->functions) { + hashGroups[hashes[func.get()]].push_back(func.get()); + } + // Find actually equal functions and prepare to replace them + std::map<Name, Name> replacements; + std::set<Name> duplicates; + for (auto& pair : hashGroups) { + auto& group = pair.second; + if (group.size() == 1) continue; + // pick a base for each group, and try to replace everyone else to it. TODO: multiple bases per hash group, for collisions + Function* base = group[0]; + for (auto* func : group) { + if (func != base && equal(func, base)) { + replacements[func->name] = base->name; + duplicates.insert(func->name); + } + } + } + // perform replacements + if (replacements.size() > 0) { + // remove the duplicates + auto& v = module->functions; + v.erase(std::remove_if(v.begin(), v.end(), [&](const std::unique_ptr<Function>& curr) { + return duplicates.count(curr->name) > 0; + }), v.end()); + module->updateFunctionsMap(); + // replace direct calls + FunctionReplacer replacer; + replacer.setReplacements(&replacements); + replacer.startWalk(module); + // replace in table + for (auto& name : module->table.names) { + auto iter = replacements.find(name); + if (iter != replacements.end()) { + name = iter->second; + } + } + // replace in start + if (module->start.is()) { + auto iter = replacements.find(module->start); + if (iter != replacements.end()) { + module->start = iter->second; + } + } + // replace in exports + for (auto& exp : module->exports) { + auto iter = replacements.find(exp->value); + if (iter != replacements.end()) { + exp->value = iter->second; + } + } + } else { + break; + } + } + } + +private: + std::map<Function*, uint32_t> hashes; + + bool equal(Function* left, Function* right) { + if (left->getNumParams() != right->getNumParams()) return false; + if (left->getNumVars() != right->getNumVars()) return false; + for (Index i = 0; i < left->getNumLocals(); i++) { + if (left->getLocalType(i) != right->getLocalType(i)) return false; + } + if (left->result != right->result) return false; + if (left->type != right->type) return false; + return ExpressionAnalyzer::equal(left->body, right->body); + } +}; + +static RegisterPass<DuplicateFunctionElimination> registerPass("duplicate-function-elimination", "removes duplicate functions"); + +} // namespace wasm + diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp index b358243f7..ca9f477a3 100644 --- a/src/passes/pass.cpp +++ b/src/passes/pass.cpp @@ -58,6 +58,7 @@ std::string PassRegistry::getPassDescription(std::string name) { // PassRunner void PassRunner::addDefaultOptimizationPasses() { + add("duplicate-function-elimination"); add("dce"); add("remove-unused-brs"); add("remove-unused-names"); @@ -70,6 +71,7 @@ void PassRunner::addDefaultOptimizationPasses() { add("merge-blocks"); add("optimize-instructions"); add("vacuum"); // should not be needed, last few passes do not create garbage, but just to be safe + add("duplicate-function-elimination"); // optimizations show more functions as duplicate } void PassRunner::run() { diff --git a/test/example/c-api-kitchen-sink.txt b/test/example/c-api-kitchen-sink.txt index 27cd7d91e..52b6cd6ed 100644 --- a/test/example/c-api-kitchen-sink.txt +++ b/test/example/c-api-kitchen-sink.txt @@ -635,39 +635,6 @@ optimized: (func $just-one-block (type $v) (nop) ) - (func $two-blocks (type $v) - (nop) - ) - (func $two-blocks-plus-code (type $v) - (nop) - ) - (func $loop (type $v) - (nop) - ) - (func $loop-plus-code (type $v) - (nop) - ) - (func $split (type $v) - (nop) - ) - (func $split-plus-code (type $v) - (nop) - ) - (func $if (type $v) - (nop) - ) - (func $if-plus-code (type $v) - (nop) - ) - (func $if-else (type $v) - (nop) - ) - (func $loop-tail (type $v) - (nop) - ) - (func $nontrivial-loop-plus-phi-to-head (type $v) - (nop) - ) ) module loaded from binary form: (module diff --git a/test/hello_libcxx.cpp b/test/hello_libcxx.cpp new file mode 100644 index 000000000..445c5513b --- /dev/null +++ b/test/hello_libcxx.cpp @@ -0,0 +1,8 @@ +#include <iostream> + +int main() +{ + std::cout << "hello, world!" << std::endl; + return 0; +} + diff --git a/test/passes/duplicate-function-elimination.txt b/test/passes/duplicate-function-elimination.txt new file mode 100644 index 000000000..9595f5705 --- /dev/null +++ b/test/passes/duplicate-function-elimination.txt @@ -0,0 +1,864 @@ +(module + (memory 0) + (func $erase + (nop) + ) +) +(module + (memory 0) + (func $keep2 + (i32.const 0) + ) + (func $other + (nop) + ) +) +(module + (memory 0) + (func $erase + (i32.const 0) + ) +) +(module + (memory 0) + (func $keep2 + (i32.const 0) + ) + (func $other + (i32.const 1) + ) +) +(module + (memory 0) + (start $keep2) + (export "keep2" $keep2) + (export "other" $keep2) + (table $keep2 $keep2 $caller) + (func $keep2 + (nop) + ) + (func $caller + (call $keep2) + (call $keep2) + ) +) +(module + (memory 0) + (func $keep2-after-two-passes + (nop) + ) + (func $keep-caller + (call $keep2-after-two-passes) + ) +) +(module + (memory 0) + (func $keep-4 + (nop) + ) + (func $other + (unreachable) + ) + (func $keep-caller + (call $keep-4) + ) + (func $other-caller + (call $other) + ) +) +(module + (memory 0) + (type $T (func (result i32))) + (type $S (func (result i32))) + (func $keep4-similar-but-func-sig-differs + (i32.const 0) + ) + (func $other1 (param $i i32) + (i32.const 0) + ) + (func $other2 (type $T) (result i32) + (i32.const 0) + ) + (func $other3 (type $S) (result i32) + (i32.const 0) + ) +) +(module + (memory 0) + (type $S (func (result i32))) + (func $keep2-similar-but-func-sig-differs (param $i i32) + (i32.const 0) + ) + (func $other2 (type $S) (result i32) + (i32.const 0) + ) +) +(module + (memory 0) + (func $keep2 + (nop) + ) + (func $other + (nop) + (nop) + ) +) +(module + (memory 0) + (func $erase + (block $block0 + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $block0 + ) + ) + (func $other + (block $block0 + (nop) + ) + ) +) +(module + (memory 0) + (func $erase + (block $block0 + (nop) + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $block0 + (nop) + ) + ) + (func $other + (block $block0 + (nop) + (unreachable) + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $block0 + (nop) + ) + ) + (func $other + (block $block0 + (unreachable) + ) + ) +) +(module + (memory 0) + (func $erase-since-block-names-do-not-matter + (block $foo + ) + ) +) +(module + (memory 0) + (func $erase-since-block-names-do-not-matter + (block $foo + (br $foo) + (br_table $foo $foo + (i32.const 0) + ) + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $foo + (br $foo + (i32.const 0) + ) + ) + ) + (func $other + (block $bar + (br $bar + (i32.const 1) + ) + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $foo + (br_if $foo + (i32.const 0) + ) + ) + ) + (func $other + (block $bar + (br_if $bar + (i32.const 1) + ) + ) + ) +) +(module + (memory 0) + (func $erase + (block $foo + (br_if $foo + (i32.const 0) + ) + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $foo + (br_table $foo $foo + (i32.const 0) + ) + ) + ) + (func $other + (block $bar + (br_table $bar $bar + (i32.const 1) + ) + ) + ) +) +(module + (memory 0) + (func $erase + (loop $foo $bar + (nop) + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $foo + (br_table $foo $foo + (i32.const 0) + (i32.const 0) + ) + ) + ) + (func $other + (block $bar + (br_table $bar $bar + (i32.const 0) + (i32.const 1) + ) + ) + ) +) +(module + (memory 0) + (func $keep2 + (block $foo + (block $bar + (br_table $foo $bar + (i32.const 0) + ) + ) + ) + ) +) +(module + (memory 0) + (func $erase + (block $foo + (block $bar + (br_table $foo $bar + (i32.const 0) + ) + ) + ) + ) + (func $other + (block $bar + (block $foo + (br_table $foo $bar + (i32.const 0) + ) + ) + ) + ) +) +(module + (memory 0) + (func $erase + (call $erase) + ) +) +(module + (memory 0) + (func $keep2-but-in-theory-we-could-erase + (call $keep2-but-in-theory-we-could-erase) + ) + (func $other + (call $other) + ) +) +(module + (memory 0) + (type $FUNCSIG$v (func)) + (import $i "env" "i") + (import $i "env" "j") + (func $erase + (call_import $i) + ) +) +(module + (memory 0) + (type $FUNCSIG$v (func)) + (import $i "env" "i") + (import $j "env" "j") + (func $keep2 + (call_import $i) + ) + (func $other + (call_import $j) + ) +) +(module + (memory 0) + (type $T (func)) + (table $erase $erase) + (func $erase + (call_indirect $T + (i32.const 0) + ) + ) +) +(module + (memory 0) + (type $T (func)) + (table $keep2 $other) + (func $keep2 + (call_indirect $T + (i32.const 0) + ) + ) + (func $other + (call_indirect $T + (i32.const 1) + ) + ) +) +(module + (memory 0) + (type $T (func)) + (type $S (func)) + (table $keep2 $other) + (func $keep2 + (call_indirect $T + (i32.const 0) + ) + ) + (func $other + (call_indirect $S + (i32.const 0) + ) + ) +) +(module + (memory 0) + (func $erase-even-locals-with-different-names + (local $i i32) + (get_local $i) + ) +) +(module + (memory 0) + (func $keep2 + (local $i i32) + (get_local $i) + ) + (func $other + (local $j i64) + (get_local $j) + ) +) +(module + (memory 0) + (func $erase-even-locals-with-different-names + (local $i i32) + (set_local $i + (i32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep2 + (local $i i32) + (set_local $i + (i32.const 0) + ) + ) + (func $other + (local $j i64) + (set_local $j + (i64.const 0) + ) + ) +) +(module + (memory 0) + (func $keep2 + (local $i i32) + (set_local $i + (i32.const 0) + ) + ) + (func $other + (local $j i32) + (set_local $j + (i32.const 1) + ) + ) +) +(module + (memory 10) + (func $erase + (i32.load + (i32.const 0) + ) + (i32.load8_s offset=3 align=2 + (i32.const 0) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load16_s offset=3 + (i32.const 0) + ) + ) + (func $other + (i32.load8_s offset=3 align=2 + (i32.const 0) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_s offset=3 + (i32.const 0) + ) + ) + (func $other + (i32.load8_s offset=3 align=2 + (i32.const 0) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_s align=2 + (i32.const 0) + ) + ) + (func $other + (i32.load8_s offset=3 align=2 + (i32.const 0) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_s offset=3 align=2 + (i32.const 0) + ) + ) + (func $other + (i32.load8_s offset=3 align=2 + (i32.const 1) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_u offset=3 align=2 + (i32.const 0) + ) + ) + (func $other + (i32.load8_s offset=3 align=2 + (i32.const 0) + ) + ) +) +(module + (memory 10) + (func $erase + (i32.store + (i32.const 0) + (i32.const 100) + ) + (i32.store8 offset=3 align=2 + (i32.const 0) + (i32.const 100) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store16 offset=3 + (i32.const 0) + (i32.const 100) + ) + ) + (func $other + (i32.store8 offset=3 align=2 + (i32.const 0) + (i32.const 100) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 offset=3 + (i32.const 0) + (i32.const 100) + ) + ) + (func $other + (i32.store8 offset=3 align=2 + (i32.const 0) + (i32.const 100) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 align=2 + (i32.const 0) + (i32.const 100) + ) + ) + (func $other + (i32.store8 offset=3 align=2 + (i32.const 0) + (i32.const 100) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 offset=3 align=2 + (i32.const 0) + (i32.const 100) + ) + ) + (func $other + (i32.store8 offset=3 align=2 + (i32.const 1) + (i32.const 100) + ) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 offset=3 align=2 + (i32.const 0) + (i32.const 100) + ) + ) + (func $other + (i32.store8 offset=3 align=2 + (i32.const 0) + (i32.const 101) + ) + ) +) +(module + (memory 0) + (func $keep2 + (i32.const 0) + ) + (func $other + (i64.const 0) + ) +) +(module + (memory 0) + (func $keep2 + (i32.const 0) + ) + (func $other + (f32.const 0) + ) +) +(module + (memory 0) + (func $keep2 + (i32.const 0) + ) + (func $other + (f64.const 0) + ) +) +(module + (memory 0) + (func $keep2 + (i64.const 0) + ) + (func $other + (i64.const 1) + ) +) +(module + (memory 0) + (func $keep2 + (f32.const 0.10000000149011612) + ) + (func $other + (f32.const -0.10000000149011612) + ) +) +(module + (memory 0) + (func $keep2 + (f64.const 0.1) + ) + (func $other + (f64.const 0.2) + ) +) +(module + (memory 0) + (func $erase + (f32.abs + (f32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep2 + (f32.abs + (f32.const 0) + ) + ) + (func $other + (f32.abs + (f32.const 1) + ) + ) +) +(module + (memory 0) + (func $keep2 + (f32.abs + (f32.const 0) + ) + ) + (func $other + (f32.neg + (f32.const 0) + ) + ) +) +(module + (memory 0) + (func $erase + (f32.add + (f32.const 0) + (f32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep2 + (f32.add + (f32.const 0) + (f32.const 0) + ) + ) + (func $other + (f32.add + (f32.const 0) + (f32.const 1) + ) + ) +) +(module + (memory 0) + (func $keep2 + (f32.add + (f32.const 0) + (f32.const 0) + ) + ) + (func $other + (f32.add + (f32.const 1) + (f32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep2 + (f32.add + (f32.const 0) + (f32.const 0) + ) + ) + (func $other + (f32.sub + (f32.const 0) + (f32.const 0) + ) + ) +) +(module + (memory 0) + (func $erase + (select + (i32.const 0) + (i32.const 0) + (i32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep + (select + (i32.const 0) + (i32.const 0) + (i32.const 0) + ) + ) + (func $other + (select + (i32.const 1) + (i32.const 0) + (i32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep + (select + (i32.const 0) + (i32.const 0) + (i32.const 0) + ) + ) + (func $other + (select + (i32.const 0) + (i32.const 2) + (i32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep + (select + (i32.const 0) + (i32.const 0) + (i32.const 0) + ) + ) + (func $other + (select + (i32.const 0) + (i32.const 0) + (i32.const 3) + ) + ) +) +(module + (memory 0) + (func $erase + (return) + ) +) +(module + (memory 0) + (func $erase (result i32) + (return + (i32.const 0) + ) + ) +) +(module + (memory 0) + (func $keep (result i32) + (return + (i32.const 0) + ) + ) + (func $other (result i32) + (return + (i32.const 1) + ) + ) +) +(module + (memory 0) + (func $erase + (current_memory) + ) +) +(module + (memory 0) + (func $erase + (grow_memory + (i32.const 10) + ) + ) +) +(module + (memory 0) + (func $keep + (grow_memory + (i32.const 10) + ) + ) + (func $other + (grow_memory + (i32.const 11) + ) + ) +) +(module + (memory 0) + (func $keep + (current_memory) + ) + (func $other + (grow_memory + (i32.const 10) + ) + ) +) diff --git a/test/passes/duplicate-function-elimination.wast b/test/passes/duplicate-function-elimination.wast new file mode 100644 index 000000000..8d1a85cd5 --- /dev/null +++ b/test/passes/duplicate-function-elimination.wast @@ -0,0 +1,702 @@ +(module + (func $erase + (nop) + ) + (func $other + (nop) + ) +) +(module + (func $keep2 + (i32.const 0) + ) + (func $other + (nop) + ) +) +(module + (func $erase + (i32.const 0) + ) + (func $other + (i32.const 0) + ) +) +(module + (func $keep2 + (i32.const 0) + ) + (func $other + (i32.const 1) + ) +) +(module + (export "keep2" $keep2) + (export "other" $other) + (start $other) + (table $keep2 $other $caller) + (func $keep2 + (nop) + ) + (func $other + (nop) + ) + (func $caller + (call $keep2) + (call $other) + ) +) +(module + (func $keep2-after-two-passes + (nop) + ) + (func $other + (nop) + ) + (func $keep-caller + (call $keep2-after-two-passes) + ) + (func $other-caller + (call $other) + ) +) +(module + (func $keep-4 + (nop) + ) + (func $other + (unreachable) + ) + (func $keep-caller + (call $keep-4) + ) + (func $other-caller + (call $other) + ) +) +(module + (type T (func (result i32))) + (type S (func (result i32))) + (func $keep4-similar-but-func-sig-differs + (i32.const 0) + ) + (func $other1 (param $i i32) + (i32.const 0) + ) + (func $other2 (type $T) (result i32) + (i32.const 0) + ) + (func $other3 (type $S) (result i32) + (i32.const 0) + ) +) +(module + (type S (func (result i32))) + (func $keep2-similar-but-func-sig-differs (param $i i32) + (i32.const 0) + ) + (func $other1 (param $i i32) + (i32.const 0) + ) + (func $other2 (type $S) (result i32) + (i32.const 0) + ) + (func $other3 (type $S) (result i32) + (i32.const 0) + ) +) +;; hashing tests for expressions +(module + (func $keep2 + (nop) + ) + (func $other + (nop) + (nop) + ) +) +(module + (func $erase + (block) + ) + (func $other + (block) + ) +) +(module + (func $keep2 + (block) + ) + (func $other + (block (nop)) + ) +) +(module + (func $erase + (block (nop)) + ) + (func $other + (block (nop)) + ) +) +(module + (func $keep2 + (block (nop)) + ) + (func $other + (block (nop) (unreachable)) + ) +) +(module + (func $keep2 + (block (nop)) + ) + (func $other + (block (unreachable)) + ) +) +(module + (func $erase-since-block-names-do-not-matter + (block $foo) + ) + (func $other + (block $bar) + ) +) +(module + (func $erase-since-block-names-do-not-matter + (block $foo + (br $foo) + (br_table $foo $foo (i32.const 0)) + ) + ) + (func $other + (block $bar + (br $bar) + (br_table $bar $bar (i32.const 0)) + ) + ) +) +(module + (func $keep2 + (block $foo + (br $foo (i32.const 0)) + ) + ) + (func $other + (block $bar + (br $bar (i32.const 1)) + ) + ) +) +(module + (func $keep2 + (block $foo + (br_if $foo (i32.const 0)) + ) + ) + (func $other + (block $bar + (br_if $bar (i32.const 1)) + ) + ) +) +(module + (func $erase + (block $foo + (br_if $foo (i32.const 0)) + ) + ) + (func $other + (block $bar + (br_if $bar (i32.const 0)) + ) + ) +) +(module + (func $keep2 + (block $foo + (br_table $foo $foo (i32.const 0)) + ) + ) + (func $other + (block $bar + (br_table $bar $bar (i32.const 1)) + ) + ) +) +(module + (func $erase + (loop $foo $bar) + ) + (func $other + (loop $sfo $sjc) + ) +) +(module + (func $keep2 + (block $foo + (br_table $foo $foo (i32.const 0) (i32.const 0)) + ) + ) + (func $other + (block $bar + (br_table $bar $bar (i32.const 0) (i32.const 1)) + ) + ) +) +(module + (func $keep2 + (block $foo + (block $bar + (br_table $foo $bar (i32.const 0)) + ) + ) + ) + (func $other + (block $bar + (block $foo + (br_table $bar $foo (i32.const 0)) + ) + ) + ) +) +(module + (func $erase + (block $foo + (block $bar + (br_table $foo $bar (i32.const 0)) + ) + ) + ) + (func $other + (block $bar + (block $foo + (br_table $foo $bar (i32.const 0)) + ) + ) + ) +) +(module + (func $erase + (call $erase) + ) + (func $other + (call $erase) + ) +) +(module + (func $keep2-but-in-theory-we-could-erase ;; TODO FIXME + (call $keep2-but-in-theory-we-could-erase) + ) + (func $other + (call $other) + ) +) +(module + (import $i "env" "i") + (import $i "env" "j") + (func $erase + (call_import $i) + ) + (func $other + (call_import $i) + ) +) +(module + (import $i "env" "i") + (import $j "env" "j") + (func $keep2 + (call_import $i) + ) + (func $other + (call_import $j) + ) +) +(module + (type T (func)) + (table $erase $other) + (func $erase + (call_indirect $T (i32.const 0)) + ) + (func $other + (call_indirect $T (i32.const 0)) + ) +) +(module + (type T (func)) + (table $keep2 $other) + (func $keep2 + (call_indirect $T (i32.const 0)) + ) + (func $other + (call_indirect $T (i32.const 1)) + ) +) +(module + (type T (func)) + (type S (func)) + (table $keep2 $other) + (func $keep2 + (call_indirect $T (i32.const 0)) + ) + (func $other + (call_indirect $S (i32.const 0)) + ) +) +(module + (func $erase-even-locals-with-different-names + (local $i i32) + (get_local $i) + ) + (func $other + (local $j i32) + (get_local $j) + ) +) +(module + (func $keep2 + (local $i i32) + (get_local $i) + ) + (func $other + (local $j i64) + (get_local $j) + ) +) +(module + (func $erase-even-locals-with-different-names + (local $i i32) + (set_local $i (i32.const 0)) + ) + (func $other + (local $j i32) + (set_local $j (i32.const 0)) + ) +) +(module + (func $keep2 + (local $i i32) + (set_local $i (i32.const 0)) + ) + (func $other + (local $j i64) + (set_local $j (i64.const 0)) + ) +) +(module + (func $keep2 + (local $i i32) + (set_local $i (i32.const 0)) + ) + (func $other + (local $j i32) + (set_local $j (i32.const 1)) + ) +) +(module + (memory 10) + (func $erase + (i32.load (i32.const 0)) + (i32.load8_s align=2 offset=3 (i32.const 0)) + ) + (func $other + (i32.load (i32.const 0)) + (i32.load8_s align=2 offset=3 (i32.const 0)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load16_s align=2 offset=3 (i32.const 0)) + ) + (func $other + (i32.load8_s align=2 offset=3 (i32.const 0)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_s offset=3 (i32.const 0)) + ) + (func $other + (i32.load8_s align=2 offset=3 (i32.const 0)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_s align=2 (i32.const 0)) + ) + (func $other + (i32.load8_s align=2 offset=3 (i32.const 0)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_s align=2 offset=3 (i32.const 0)) + ) + (func $other + (i32.load8_s align=2 offset=3 (i32.const 1)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.load8_u align=2 offset=3 (i32.const 0)) + ) + (func $other + (i32.load8_s align=2 offset=3 (i32.const 0)) + ) +) + +(module + (memory 10) + (func $erase + (i32.store (i32.const 0) (i32.const 100)) + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) + (func $other + (i32.store (i32.const 0) (i32.const 100)) + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store16 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) + (func $other + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 offset=3 (i32.const 0) (i32.const 100)) + ) + (func $other + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 align=2 (i32.const 0) (i32.const 100)) + ) + (func $other + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) + (func $other + (i32.store8 align=2 offset=3 (i32.const 1) (i32.const 100)) + ) +) +(module + (memory 10) + (func $keep2 + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 100)) + ) + (func $other + (i32.store8 align=2 offset=3 (i32.const 0) (i32.const 101)) + ) +) +(module + (func $keep2 + (i32.const 0) + ) + (func $other + (i64.const 0) + ) +) +(module + (func $keep2 + (i32.const 0) + ) + (func $other + (f32.const 0) + ) +) +(module + (func $keep2 + (i32.const 0) + ) + (func $other + (f64.const 0) + ) +) +(module + (func $keep2 + (i64.const 0) + ) + (func $other + (i64.const 1) + ) +) +(module + (func $keep2 + (f32.const 0.1) + ) + (func $other + (f32.const -0.1) + ) +) +(module + (func $keep2 + (f64.const 0.1) + ) + (func $other + (f64.const 0.2) + ) +) +(module + (func $erase + (f32.abs (f32.const 0)) + ) + (func $other + (f32.abs (f32.const 0)) + ) +) +(module + (func $keep2 + (f32.abs (f32.const 0)) + ) + (func $other + (f32.abs (f32.const 1)) + ) +) +(module + (func $keep2 + (f32.abs (f32.const 0)) + ) + (func $other + (f32.neg (f32.const 0)) + ) +) +(module + (func $erase + (f32.add (f32.const 0) (f32.const 0)) + ) + (func $other + (f32.add (f32.const 0) (f32.const 0)) + ) +) +(module + (func $keep2 + (f32.add (f32.const 0) (f32.const 0)) + ) + (func $other + (f32.add (f32.const 0) (f32.const 1)) + ) +) +(module + (func $keep2 + (f32.add (f32.const 0) (f32.const 0)) + ) + (func $other + (f32.add (f32.const 1) (f32.const 0)) + ) +) +(module + (func $keep2 + (f32.add (f32.const 0) (f32.const 0)) + ) + (func $other + (f32.sub (f32.const 0) (f32.const 0)) + ) +) +(module + (func $erase + (select (i32.const 0) (i32.const 0) (i32.const 0)) + ) + (func $other + (select (i32.const 0) (i32.const 0) (i32.const 0)) + ) +) +(module + (func $keep + (select (i32.const 0) (i32.const 0) (i32.const 0)) + ) + (func $other + (select (i32.const 1) (i32.const 0) (i32.const 0)) + ) +) +(module + (func $keep + (select (i32.const 0) (i32.const 0) (i32.const 0)) + ) + (func $other + (select (i32.const 0) (i32.const 2) (i32.const 0)) + ) +) +(module + (func $keep + (select (i32.const 0) (i32.const 0) (i32.const 0)) + ) + (func $other + (select (i32.const 0) (i32.const 0) (i32.const 3)) + ) +) +(module + (func $erase + (return) + ) + (func $other + (return) + ) +) +(module + (func $erase (result i32) + (return (i32.const 0)) + ) + (func $other (result i32) + (return (i32.const 0)) + ) +) +(module + (func $keep (result i32) + (return (i32.const 0)) + ) + (func $other (result i32) + (return (i32.const 1)) + ) +) +(module + (func $erase + (current_memory) + ) + (func $other + (current_memory) + ) +) +(module + (func $erase + (grow_memory (i32.const 10)) + ) + (func $other + (grow_memory (i32.const 10)) + ) +) +(module + (func $keep + (grow_memory (i32.const 10)) + ) + (func $other + (grow_memory (i32.const 11)) + ) +) +(module + (func $keep + (current_memory) + ) + (func $other + (grow_memory (i32.const 10)) + ) +) + diff --git a/test/unit.fromasm b/test/unit.fromasm index b51ff4ba1..288b3af3b 100644 --- a/test/unit.fromasm +++ b/test/unit.fromasm @@ -11,7 +11,7 @@ (import $f64-to-int "asm2wasm" "f64-to-int" (param f64) (result i32)) (import $f64-rem "asm2wasm" "f64-rem" (param f64 f64) (result f64)) (export "big_negative" $big_negative) - (table $z $big_negative $z $z $w $w $importedDoubles $w $z $cneg) + (table $big_negative $big_negative $big_negative $big_negative $big_negative $big_negative $importedDoubles $big_negative $big_negative $cneg) (func $big_negative (nop) ) @@ -87,9 +87,6 @@ (get_local $0) ) ) - (func $hexLiterals - (nop) - ) (func $conversions (local $0 f64) (local $1 f32) @@ -105,9 +102,6 @@ ) ) ) - (func $seq - (nop) - ) (func $switcher (param $0 i32) (result i32) (block $switch-default$3 (block $switch-case$2 @@ -205,9 +199,6 @@ ) (i32.const 0) ) - (func $blocker - (nop) - ) (func $frem (result f64) (call_import $f64-rem (f64.const 5.5) @@ -229,9 +220,6 @@ (func $negZero (result f64) (f64.const -0) ) - (func $abs - (nop) - ) (func $neg (local $0 f32) (call_indirect $FUNCSIG$vf @@ -259,9 +247,6 @@ (get_local $0) ) ) - (func $___syscall_ret - (nop) - ) (func $smallCompare (result i32) (local $0 i32) (local $1 i32) @@ -439,10 +424,4 @@ ) (i32.const 0) ) - (func $z - (nop) - ) - (func $w - (nop) - ) ) diff --git a/test/unit.fromasm.imprecise b/test/unit.fromasm.imprecise index 0ea85eb6c..303a0cabf 100644 --- a/test/unit.fromasm.imprecise +++ b/test/unit.fromasm.imprecise @@ -9,7 +9,7 @@ (import $h "env" "h" (param i32)) (import $f64-rem "asm2wasm" "f64-rem" (param f64 f64) (result f64)) (export "big_negative" $big_negative) - (table $z $big_negative $z $z $w $w $importedDoubles $w $z $cneg) + (table $big_negative $big_negative $big_negative $big_negative $big_negative $big_negative $importedDoubles $big_negative $big_negative $cneg) (func $big_negative (nop) ) @@ -85,9 +85,6 @@ (get_local $0) ) ) - (func $hexLiterals - (nop) - ) (func $conversions (local $0 f32) (local $1 i32) @@ -97,9 +94,6 @@ ) ) ) - (func $seq - (nop) - ) (func $switcher (param $0 i32) (result i32) (block $switch-default$3 (block $switch-case$2 @@ -197,9 +191,6 @@ ) (i32.const 0) ) - (func $blocker - (nop) - ) (func $frem (result f64) (call_import $f64-rem (f64.const 5.5) @@ -221,9 +212,6 @@ (func $negZero (result f64) (f64.const -0) ) - (func $abs - (nop) - ) (func $neg (local $0 f32) (call_indirect $FUNCSIG$vf @@ -251,9 +239,6 @@ (get_local $0) ) ) - (func $___syscall_ret - (nop) - ) (func $smallCompare (result i32) (local $0 i32) (local $1 i32) @@ -431,10 +416,4 @@ ) (i32.const 0) ) - (func $z - (nop) - ) - (func $w - (nop) - ) ) |