Directize: turns indirect calls into direct ones (#1974)

* wip [ci skip]

* works

* test output

* test update

* js build

* better location for running directize

4 files changed, 136 insertions, 2 deletions

diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index 2848946f8..2b1b64d84 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -12,6 +12,7 @@ SET(passes_SOURCES
   DataFlowOpts.cpp
   DeadArgumentElimination.cpp
   DeadCodeElimination.cpp
+  Directize.cpp
   DuplicateFunctionElimination.cpp
   ExtractFunction.cpp
   Flatten.cpp
diff --git a/src/passes/Directize.cpp b/src/passes/Directize.cpp
new file mode 100644
index 000000000..d9400cce7
--- /dev/null
+++ b/src/passes/Directize.cpp
@@ -0,0 +1,132 @@
+/*
+ * 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.
+ */
+
+//
+// Turn indirect calls into direct calls. This is possible if we know
+// the table cannot change, and if we see a constant argument for the
+// indirect call's index.
+//
+
+#include <unordered_map>
+
+#include "wasm.h"
+#include "pass.h"
+#include "wasm-builder.h"
+#include "wasm-traversal.h"
+#include "asm_v_wasm.h"
+
+namespace wasm {
+
+namespace {
+
+struct FlatTable {
+  std::vector<Name> names;
+  bool valid;
+
+  FlatTable(Table& table) {
+    valid = true;
+    for (auto& segment : table.segments) {
+      auto offset = segment.offset;
+      if (!offset->is<Const>()) {
+        // TODO: handle some non-constant segments
+        valid = false;
+        return;
+      }
+      Index start = offset->cast<Const>()->value.geti32();
+      Index end = start + segment.data.size();
+      if (end > names.size()) {
+        names.resize(end);
+      }
+      for (Index i = 0; i < segment.data.size(); i++) {
+        names[start + i] = segment.data[i];
+      }
+    }
+  }
+};
+
+struct FunctionDirectizer : public WalkerPass<PostWalker<FunctionDirectizer>> {
+  bool isFunctionParallel() override { return true; }
+
+  Pass* create() override { return new FunctionDirectizer(flatTable); }
+
+  FunctionDirectizer(FlatTable* flatTable) : flatTable(flatTable) {}
+
+  void visitCallIndirect(CallIndirect* curr) {
+    if (auto* c = curr->target->dynCast<Const>()) {
+      Index index = c->value.geti32();
+      // If the index is invalid, or the type is wrong, we can
+      // emit an unreachable here, since in Binaryen it is ok to
+      // reorder/replace traps when optimizing (but never to
+      // remove them, at least not by default).
+      if (index >= flatTable->names.size()) {
+        replaceWithUnreachable();
+        return;
+      }
+      auto name = flatTable->names[index];
+      if (!name.is()) {
+        replaceWithUnreachable();
+        return;
+      }
+      auto* func = getModule()->getFunction(name);
+      if (getSig(getModule()->getFunctionType(curr->fullType)) !=
+          getSig(func)) {
+        replaceWithUnreachable();
+        return;
+      }
+      // Everything looks good!
+      replaceCurrent(Builder(*getModule()).makeCall(
+        name,
+        curr->operands,
+        curr->type
+      ));
+    }
+  }
+
+private:
+  FlatTable* flatTable;
+
+  void replaceWithUnreachable() {
+    replaceCurrent(Builder(*getModule()).makeUnreachable());
+  }
+};
+
+struct Directize : public Pass {
+  void run(PassRunner* runner, Module* module) override {
+    if (!module->table.exists) return;
+    if (module->table.imported()) return;
+    for (auto& ex : module->exports) {
+      if (ex->kind == ExternalKind::Table) return;
+    }
+    FlatTable flatTable(module->table);
+    if (!flatTable.valid) return;
+    // The table exists and is constant, so this is possible.
+    {
+      PassRunner runner(module);
+      runner.setIsNested(true);
+      runner.add<FunctionDirectizer>(&flatTable);
+      runner.run();
+    }
+  }
+};
+
+} // anonymous namespace
+
+Pass *createDirectizePass() {
+  return new Directize();
+}
+
+} // namespace wasm
+
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 82a804eb5..fecb644b5 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -75,6 +75,7 @@ void PassRegistry::registerPasses() {
   registerPass("code-folding", "fold code, merging duplicates", createCodeFoldingPass);
   registerPass("const-hoisting", "hoist repeated constants to a local", createConstHoistingPass);
   registerPass("dce", "removes unreachable code", createDeadCodeEliminationPass);
+  registerPass("directize", "turns indirect calls into direct ones", createDirectizePass);
   registerPass("dfo", "optimizes using the DataFlow SSA IR", createDataFlowOptsPass);
   registerPass("duplicate-function-elimination", "removes duplicate functions", createDuplicateFunctionEliminationPass);
   registerPass("extract-function", "leaves just one function (useful for debugging)", createExtractFunctionPass);
@@ -228,17 +229,16 @@ void PassRunner::addDefaultGlobalOptimizationPrePasses() {
 }
 
 void PassRunner::addDefaultGlobalOptimizationPostPasses() {
-  // inlining/dae+optimizing can remove debug annotations
   if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) {
     add("dae-optimizing");
   }
-  // inline when working hard, and when not preserving debug info
   if (options.optimizeLevel >= 2 || options.shrinkLevel >= 2) {
     add("inlining-optimizing");
   }
   add("duplicate-function-elimination"); // optimizations show more functions as duplicate
   add("remove-unused-module-elements");
   add("memory-packing");
+  add("directize"); // may allow more inlining/dae/etc., need --converge for that
   // perform Stack IR optimizations here, at the very end of the
   // optimization pipeline
   if (options.optimizeLevel >= 2 || options.shrinkLevel >= 1) {
diff --git a/src/passes/passes.h b/src/passes/passes.h
index 5ad54f705..fea06e388 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -31,6 +31,7 @@ Pass* createDAEPass();
 Pass* createDAEOptimizingPass();
 Pass* createDataFlowOptsPass();
 Pass* createDeadCodeEliminationPass();
+Pass* createDirectizePass();
 Pass* createDuplicateFunctionEliminationPass();
 Pass* createExtractFunctionPass();
 Pass* createFlattenPass();