Duplicate Import Elimination (#2292)

This is both an optimization and a workaround for the problem that emscripten-core/emscripten#7641 uncovered and had to be reverted because of.

What's going on there is that wasm-emscripten-finalize turns emscripten_longjmp_jmpbuf into emscripten_longjmp (for some LLVM internal reason - there's a long comment in the source that I didn't fully follow). There are two such imports already, one for each name, and before that PR, we ended up with just one. After that PR, we end up with two. And with two, the minification of import names gets confused - we have two imports with the same name, and the code there ends up ignoring one of them.

I'm not sure why that PR changed things - I guess the wasm-emscripten-finalize code looks at the name, and that PR changed what name appears? @sbc100 maybe #2285 is related?

Anyhow, it's not trivial to make import minification code support two identical imports, but I don't think we should - we should avoid having such duplication anyhow. And we should add an assert that they don't exist (I'll open a PR for that later when it's possible).

This fixes the duplication by adding a useful pass to remove duplicate imports (just functions, for now). Pretty simple, but we didn't do it yet. Even if there is a wasm-emscripten-finalize bug we need to fix with those duplicate imports, I think this pass is still a good thing to add.

I confirmed that this fixes the issue caused by that PR.

9 files changed, 158 insertions, 46 deletions

diff --git a/build-js.sh b/build-js.sh
index 26d5f4466..dd43545b0 100755
--- a/build-js.sh
+++ b/build-js.sh
@@ -103,6 +103,7 @@ mkdir -p ${OUT}
   $BINARYEN_SRC/passes/DataFlowOpts.cpp \
   $BINARYEN_SRC/passes/DeadCodeElimination.cpp \
   $BINARYEN_SRC/passes/Directize.cpp \
+  $BINARYEN_SRC/passes/DuplicateImportElimination.cpp \
   $BINARYEN_SRC/passes/DuplicateFunctionElimination.cpp \
   $BINARYEN_SRC/passes/ExtractFunction.cpp \
   $BINARYEN_SRC/passes/Flatten.cpp \
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index cb51ea55a..41a6a72a6 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -16,6 +16,7 @@ SET(passes_SOURCES
   DeadArgumentElimination.cpp
   DeadCodeElimination.cpp
   Directize.cpp
+  DuplicateImportElimination.cpp
   DuplicateFunctionElimination.cpp
   ExtractFunction.cpp
   Flatten.cpp
diff --git a/src/passes/DuplicateFunctionElimination.cpp b/src/passes/DuplicateFunctionElimination.cpp
index 445a024e4..12da32806 100644
--- a/src/passes/DuplicateFunctionElimination.cpp
+++ b/src/passes/DuplicateFunctionElimination.cpp
@@ -24,32 +24,12 @@
 #include "ir/hashed.h"
 #include "ir/module-utils.h"
 #include "ir/utils.h"
+#include "opt-utils.h"
 #include "pass.h"
 #include "wasm.h"
 
 namespace wasm {
 
-struct FunctionReplacer : public WalkerPass<PostWalker<FunctionReplacer>> {
-  bool isFunctionParallel() override { return true; }
-
-  FunctionReplacer(std::map<Name, Name>* replacements)
-    : replacements(replacements) {}
-
-  FunctionReplacer* create() override {
-    return new FunctionReplacer(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 {
     // Multiple iterations may be necessary: A and B may be identical only after
@@ -117,31 +97,7 @@ struct DuplicateFunctionElimination : public Pass {
                                }),
                 v.end());
         module->updateMaps();
-        // replace direct calls
-        FunctionReplacer(&replacements).run(runner, module);
-        // replace in table
-        for (auto& segment : module->table.segments) {
-          for (auto& name : segment.data) {
-            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;
-          }
-        }
+        OptUtils::replaceFunctions(runner, *module, replacements);
       } else {
         break;
       }
diff --git a/src/passes/DuplicateImportElimination.cpp b/src/passes/DuplicateImportElimination.cpp
new file mode 100644
index 000000000..39b126b6c
--- /dev/null
+++ b/src/passes/DuplicateImportElimination.cpp
@@ -0,0 +1,67 @@
+/*
+ * Copyright 2019 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 imports.
+//
+// TODO: non-function imports too
+//
+
+#include "asm_v_wasm.h"
+#include "ir/import-utils.h"
+#include "opt-utils.h"
+#include "pass.h"
+#include "wasm.h"
+
+namespace wasm {
+
+struct DuplicateImportElimination : public Pass {
+  void run(PassRunner* runner, Module* module) override {
+    ImportInfo imports(*module);
+    std::map<Name, Name> replacements;
+    std::map<std::pair<Name, Name>, Name> seen;
+    std::vector<Name> toRemove;
+    for (auto* func : imports.importedFunctions) {
+      auto pair = std::make_pair(func->module, func->base);
+      auto iter = seen.find(pair);
+      if (iter != seen.end()) {
+        auto previousName = iter->second;
+        auto previousFunc = module->getFunction(previousName);
+        // It is ok to import the same thing with multiple types; we can only
+        // merge if the types match, of course.
+        if (getSig(previousFunc) == getSig(func)) {
+          replacements[func->name] = previousName;
+          toRemove.push_back(func->name);
+          continue;
+        }
+      }
+      seen[pair] = func->name;
+    }
+    if (!replacements.empty()) {
+      module->updateMaps();
+      OptUtils::replaceFunctions(runner, *module, replacements);
+      for (auto name : toRemove) {
+        module->removeFunction(name);
+      }
+    }
+  }
+};
+
+Pass* createDuplicateImportEliminationPass() {
+  return new DuplicateImportElimination();
+}
+
+} // namespace wasm
diff --git a/src/passes/opt-utils.h b/src/passes/opt-utils.h
index 9ac6da4a2..e9141c4f1 100644
--- a/src/passes/opt-utils.h
+++ b/src/passes/opt-utils.h
@@ -53,6 +53,57 @@ inline void optimizeAfterInlining(std::unordered_set<Function*>& funcs,
   module->updateMaps();
 }
 
+struct CallTargetReplacer : public WalkerPass<PostWalker<CallTargetReplacer>> {
+  bool isFunctionParallel() override { return true; }
+
+  CallTargetReplacer(std::map<Name, Name>* replacements)
+    : replacements(replacements) {}
+
+  CallTargetReplacer* create() override {
+    return new CallTargetReplacer(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;
+};
+
+inline void replaceFunctions(PassRunner* runner,
+                             Module& module,
+                             std::map<Name, Name>& replacements) {
+  // replace direct calls
+  CallTargetReplacer(&replacements).run(runner, &module);
+  // replace in table
+  for (auto& segment : module.table.segments) {
+    for (auto& name : segment.data) {
+      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;
+    }
+  }
+}
+
 } // namespace OptUtils
 } // namespace wasm
 
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 5d8fb6d61..daa575c6d 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -107,6 +107,9 @@ void PassRegistry::registerPasses() {
     "directize", "turns indirect calls into direct ones", createDirectizePass);
   registerPass(
     "dfo", "optimizes using the DataFlow SSA IR", createDataFlowOptsPass);
+  registerPass("duplicate-import-elimination",
+               "removes duplicate imports",
+               createDuplicateImportEliminationPass);
   registerPass("duplicate-function-elimination",
                "removes duplicate functions",
                createDuplicateFunctionEliminationPass);
@@ -412,6 +415,7 @@ void PassRunner::addDefaultGlobalOptimizationPostPasses() {
   }
   // optimizations show more functions as duplicate
   add("duplicate-function-elimination");
+  add("duplicate-import-elimination");
   add("simplify-globals");
   add("remove-unused-module-elements");
   add("memory-packing");
diff --git a/src/passes/passes.h b/src/passes/passes.h
index d99a5a6f1..115e9bab6 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -35,6 +35,7 @@ Pass* createDAEOptimizingPass();
 Pass* createDataFlowOptsPass();
 Pass* createDeadCodeEliminationPass();
 Pass* createDirectizePass();
+Pass* createDuplicateImportEliminationPass();
 Pass* createDuplicateFunctionEliminationPass();
 Pass* createEmitTargetFeaturesPass();
 Pass* createExtractFunctionPass();
diff --git a/test/passes/duplicate-import-elimination.txt b/test/passes/duplicate-import-elimination.txt
new file mode 100644
index 000000000..ee90ebfba
--- /dev/null
+++ b/test/passes/duplicate-import-elimination.txt
@@ -0,0 +1,17 @@
+(module
+ (type $FUNCSIG$v (func))
+ (type $FUNCSIG$vi (func (param i32)))
+ (import "env" "waka" (func $foo))
+ (import "env" "waka" (func $wrong (param i32)))
+ (table $0 2 2 funcref)
+ (elem (i32.const 0) $foo $foo)
+ (export "baz" (func $0))
+ (start $foo)
+ (func $0 (; 2 ;) (type $FUNCSIG$v)
+  (call $foo)
+  (call $foo)
+  (call $wrong
+   (i32.const 1)
+  )
+ )
+)
diff --git a/test/passes/duplicate-import-elimination.wast b/test/passes/duplicate-import-elimination.wast
new file mode 100644
index 000000000..cd0c9dbf7
--- /dev/null
+++ b/test/passes/duplicate-import-elimination.wast
@@ -0,0 +1,14 @@
+(module
+  (import "env" "waka" (func $foo))
+  (import "env" "waka" (func $bar))
+  (import "env" "waka" (func $wrong (param i32)))
+  (table 2 2 funcref)
+  (elem (i32.const 0) $foo $bar)
+  (start $bar)
+  (func "baz"
+    (call $foo)
+    (call $bar)
+    (call $wrong (i32.const 1))
+  )
+)
+