add a pass that eliminates duplicate functions

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)
-  )
 )