summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xbuild-js.sh1
-rw-r--r--src/passes/CMakeLists.txt1
-rw-r--r--src/passes/Directize.cpp132
-rw-r--r--src/passes/pass.cpp4
-rw-r--r--src/passes/passes.h1
-rw-r--r--test/passes/directize.txt159
-rw-r--r--test/passes/directize.wast182
-rw-r--r--test/reduce/memory_table.wast.txt25
8 files changed, 486 insertions, 19 deletions
diff --git a/build-js.sh b/build-js.sh
index cfcb914ef..192ef662a 100755
--- a/build-js.sh
+++ b/build-js.sh
@@ -98,6 +98,7 @@ echo "building shared bitcode"
$BINARYEN_SRC/passes/ConstHoisting.cpp \
$BINARYEN_SRC/passes/DataFlowOpts.cpp \
$BINARYEN_SRC/passes/DeadCodeElimination.cpp \
+ $BINARYEN_SRC/passes/Directize.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 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();
diff --git a/test/passes/directize.txt b/test/passes/directize.txt
new file mode 100644
index 000000000..6e0644c01
--- /dev/null
+++ b/test/passes/directize.txt
@@ -0,0 +1,159 @@
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (call $foo
+ (local.get $x)
+ (local.get $y)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 4) $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (call $foo
+ (local.get $x)
+ (local.get $y)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 0) $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (call $foo
+ (local.get $x)
+ (local.get $y)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 0) $foo $foo $foo $foo $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (call $foo
+ (local.get $x)
+ (local.get $y)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (import "env" "table" (table $0 5 5 funcref))
+ (elem (i32.const 1) $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (export "tab" (table $0))
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (global.get $g) $foo)
+ (global $g (mut i32) (i32.const 1))
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (type $1 (func (param i32 i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $1) (param $x i32) (param $y i32) (param $z i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (local.get $z)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (unreachable)
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (; 0 ;) (type $ii) (param $0 i32) (param $1 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (unreachable)
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (type $1 (func (param i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (; 0 ;) (type $1) (param $0 i32)
+ (unreachable)
+ )
+ (func $bar (; 1 ;) (type $ii) (param $x i32) (param $y i32)
+ (unreachable)
+ )
+)
+(module
+ (type $0 (func (param i32)))
+ (func $foo (; 0 ;) (type $0) (param $0 i32)
+ (unreachable)
+ )
+)
diff --git a/test/passes/directize.wast b/test/passes/directize.wast
new file mode 100644
index 000000000..8e6839457
--- /dev/null
+++ b/test/passes/directize.wast
@@ -0,0 +1,182 @@
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+;; at table edges
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 4) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 4)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 0) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 0)
+ )
+ )
+)
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 0) $foo $foo $foo $foo $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 2)
+ )
+ )
+)
+;; imported table
+(module
+ (type $ii (func (param i32 i32)))
+ (import "env" "table" (table $table 5 5 funcref))
+ (elem (i32.const 1) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+;; exported table
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (export "tab" (table $0))
+ (elem (i32.const 1) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+;; non-constant table offset
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (global $g (mut i32) (i32.const 1))
+ (elem (global.get $g) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+;; non-constant call index
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32) (param $z i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (local.get $z)
+ )
+ )
+)
+;; bad index
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 5)
+ )
+ )
+)
+;; missing index
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (param i32) (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 2)
+ )
+ )
+)
+;; bad type
+(module
+ (type $ii (func (param i32 i32)))
+ (table $0 5 5 funcref)
+ (elem (i32.const 1) $foo)
+ (func $foo (param i32)
+ (unreachable)
+ )
+ (func $bar (param $x i32) (param $y i32)
+ (call_indirect (type $ii)
+ (local.get $x)
+ (local.get $y)
+ (i32.const 1)
+ )
+ )
+)
+;; no table
+(module
+ (func $foo (param i32)
+ (unreachable)
+ )
+)
+
diff --git a/test/reduce/memory_table.wast.txt b/test/reduce/memory_table.wast.txt
index 3c3b80ca8..1665c7a4e 100644
--- a/test/reduce/memory_table.wast.txt
+++ b/test/reduce/memory_table.wast.txt
@@ -2,18 +2,13 @@
(type $0 (func (result i32)))
(type $1 (func))
(memory $0 256 256)
- (table $0 481 481 funcref)
- (elem (i32.const 0) $0 $0 $0 $2)
- (export "f1" (func $1))
- (export "f2" (func $2))
- (export "f4" (func $3))
- (func $0 (; 0 ;) (type $0) (result i32)
- (i32.const 1234)
- )
- (func $1 (; 1 ;) (type $1)
+ (export "f1" (func $0))
+ (export "f2" (func $1))
+ (export "f4" (func $2))
+ (func $0 (; 0 ;) (type $1)
(nop)
)
- (func $2 (; 2 ;) (type $0) (result i32)
+ (func $1 (; 1 ;) (type $0) (result i32)
(i32.store
(i32.const 0)
(i32.const 65530)
@@ -22,14 +17,10 @@
(i32.const 0)
)
)
- (func $3 (; 3 ;) (type $0) (result i32)
+ (func $2 (; 2 ;) (type $0) (result i32)
(i32.add
- (call_indirect (type $0)
- (i32.const 3)
- )
- (call_indirect (type $0)
- (i32.const 0)
- )
+ (call $1)
+ (i32.const 1234)
)
)
)
generated by cgit v1.2.3 (git 2.39.1) at 2025-08-13 06:42:50 +0000