From 76751bf1f9df4eb2ee6c216744af9ed1e097132e Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Mon, 31 Jul 2017 15:10:38 -0700 Subject: Polymophic stack support (#1117) Emit valid wasm binaries even for corner cases of unreachable code. * emit an unreachable after a node that pushes a value that has unreachable type (where wasm type checking would have pushed a concrete type) * conversely, as a hack, emulate the wasm polymorphic stack mode by not emptying the stack when it has one element and that element is unreachable. this lets further pops work (all returning an unreachable element) --- src/wasm/wasm-binary.cpp | 34 +++++- test/polymorphic_stack.wast | 90 ++++++++++++++ test/polymorphic_stack.wast.from-wast | 93 +++++++++++++++ test/polymorphic_stack.wast.fromBinary | 129 +++++++++++++++++++++ test/polymorphic_stack.wast.fromBinary.noDebugInfo | 129 +++++++++++++++++++++ test/unit.wast.fromBinary | 5 + test/unit.wast.fromBinary.noDebugInfo | 5 + 7 files changed, 484 insertions(+), 1 deletion(-) create mode 100644 test/polymorphic_stack.wast create mode 100644 test/polymorphic_stack.wast.from-wast create mode 100644 test/polymorphic_stack.wast.fromBinary create mode 100644 test/polymorphic_stack.wast.fromBinary.noDebugInfo diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp index 2df7f2e26..346018c7d 100644 --- a/src/wasm/wasm-binary.cpp +++ b/src/wasm/wasm-binary.cpp @@ -648,6 +648,16 @@ void WasmBinaryWriter::visitBreak(Break *curr) { if (curr->condition) recurse(curr->condition); o << int8_t(curr->condition ? BinaryConsts::BrIf : BinaryConsts::Br) << U32LEB(getBreakIndex(curr->name)); + if (curr->condition && curr->type == unreachable) { + // a br_if is normally none or emits a value. if it is unreachable, + // then either the condition or the value is unreachable, which is + // extremely rare, and may require us to make the stack polymorphic + // (if the block we branch to has a value, we may lack one as we + // are not a taken branch; the wasm spec on the other hand does + // presume the br_if emits a value of the right type, even if it + // popped unreachable) + o << int8_t(BinaryConsts::Unreachable); + } } void WasmBinaryWriter::visitSwitch(Switch *curr) { @@ -669,6 +679,9 @@ void WasmBinaryWriter::visitCall(Call *curr) { recurse(operand); } o << int8_t(BinaryConsts::CallFunction) << U32LEB(getFunctionIndex(curr->target)); + if (curr->type == unreachable) { + o << int8_t(BinaryConsts::Unreachable); + } } void WasmBinaryWriter::visitCallImport(CallImport *curr) { @@ -689,6 +702,9 @@ void WasmBinaryWriter::visitCallIndirect(CallIndirect *curr) { o << int8_t(BinaryConsts::CallIndirect) << U32LEB(getFunctionTypeIndex(curr->fullType)) << U32LEB(0); // Reserved flags field + if (curr->type == unreachable) { + o << int8_t(BinaryConsts::Unreachable); + } } void WasmBinaryWriter::visitGetLocal(GetLocal *curr) { @@ -700,6 +716,9 @@ void WasmBinaryWriter::visitSetLocal(SetLocal *curr) { if (debug) std::cerr << "zz node: Set|TeeLocal" << std::endl; recurse(curr->value); o << int8_t(curr->isTee() ? BinaryConsts::TeeLocal : BinaryConsts::SetLocal) << U32LEB(mappedLocals[curr->index]); + if (curr->type == unreachable) { + o << int8_t(BinaryConsts::Unreachable); + } } void WasmBinaryWriter::visitGetGlobal(GetGlobal *curr) { @@ -986,6 +1005,9 @@ void WasmBinaryWriter::visitUnary(Unary *curr) { case ReinterpretInt64: o << int8_t(BinaryConsts::F64ReinterpretI64); break; default: abort(); } + if (curr->type == unreachable) { + o << int8_t(BinaryConsts::Unreachable); + } } void WasmBinaryWriter::visitBinary(Binary *curr) { @@ -1075,6 +1097,9 @@ void WasmBinaryWriter::visitBinary(Binary *curr) { case GeFloat64: o << int8_t(BinaryConsts::F64Ge); break; default: abort(); } + if (curr->type == unreachable) { + o << int8_t(BinaryConsts::Unreachable); + } } void WasmBinaryWriter::visitSelect(Select *curr) { @@ -1083,6 +1108,9 @@ void WasmBinaryWriter::visitSelect(Select *curr) { recurse(curr->ifFalse); recurse(curr->condition); o << int8_t(BinaryConsts::Select); + if (curr->type == unreachable) { + o << int8_t(BinaryConsts::Unreachable); + } } void WasmBinaryWriter::visitReturn(Return *curr) { @@ -1771,7 +1799,11 @@ Expression* WasmBinaryBuilder::popExpression() { throw ParseException("attempted pop from empty stack"); } auto ret = expressionStack.back(); - expressionStack.pop_back(); + // to simulate the wasm polymorphic stack mode, leave a final + // unreachable, don't empty the stack in that case + if (!(expressionStack.size() == 1 && ret->type == unreachable)) { + expressionStack.pop_back(); + } return ret; } diff --git a/test/polymorphic_stack.wast b/test/polymorphic_stack.wast new file mode 100644 index 000000000..2241ab910 --- /dev/null +++ b/test/polymorphic_stack.wast @@ -0,0 +1,90 @@ +(module + (type $FUNCSIG$ii (func (param i32) (result i32))) + (import "env" "table" (table 9 9 anyfunc)) + (func $break-and-binary (result i32) + (block $x (result i32) + (f32.add + (br_if $x + (i32.trunc_u/f64 + (unreachable) + ) + (i32.trunc_u/f64 + (unreachable) + ) + ) + (f32.const 1) + ) + ) + ) + (func $call-and-unary (param i32) (result i32) + (drop + (i64.eqz + (call $call-and-unary + (unreachable) + ) + ) + ) + (drop + (i64.eqz + (i32.eqz + (unreachable) + ) + ) + ) + (drop + (i64.eqz + (call_indirect $FUNCSIG$ii + (unreachable) + (unreachable) + ) + ) + ) + ) + (func $tee (param $x i32) + (local $y f32) + (drop + (i64.eqz + (tee_local $x + (unreachable) + ) + ) + ) + (drop + (tee_local $y + (i64.eqz + (unreachable) + ) + ) + ) + ) + (func $tee2 + (local $0 f32) + (if + (i32.const 259) + (set_local $0 + (unreachable) + ) + ) + ) + (func $select + (drop + (i64.eqz + (select + (unreachable) + (i32.const 1) + (i32.const 2) + ) + ) + ) + ) + (func $untaken-break-should-have-value (result i32) + (block $x (result i32) + (block + (br_if $x ;; ok to not have a value, since an untaken branch. but must emit valid binary for wasm + (unreachable) + ) + ) + ) + ) +) + diff --git a/test/polymorphic_stack.wast.from-wast b/test/polymorphic_stack.wast.from-wast new file mode 100644 index 000000000..b4b88f16b --- /dev/null +++ b/test/polymorphic_stack.wast.from-wast @@ -0,0 +1,93 @@ +(module + (type $FUNCSIG$ii (func (param i32) (result i32))) + (type $1 (func (result i32))) + (type $2 (func (param i32))) + (type $3 (func)) + (import "env" "table" (table 9 9 anyfunc)) + (memory $0 0) + (func $break-and-binary (type $1) (result i32) + (block $x (result i32) + (f32.add + (br_if $x + (i32.trunc_u/f64 + (unreachable) + ) + (i32.trunc_u/f64 + (unreachable) + ) + ) + (f32.const 1) + ) + ) + ) + (func $call-and-unary (type $FUNCSIG$ii) (param $0 i32) (result i32) + (drop + (i64.eqz + (call $call-and-unary + (unreachable) + ) + ) + ) + (drop + (i64.eqz + (i32.eqz + (unreachable) + ) + ) + ) + (drop + (i64.eqz + (call_indirect $FUNCSIG$ii + (unreachable) + (unreachable) + ) + ) + ) + ) + (func $tee (type $2) (param $x i32) + (local $y f32) + (drop + (i64.eqz + (tee_local $x + (unreachable) + ) + ) + ) + (drop + (tee_local $y + (i64.eqz + (unreachable) + ) + ) + ) + ) + (func $tee2 (type $3) + (local $0 f32) + (if + (i32.const 259) + (tee_local $0 + (unreachable) + ) + ) + ) + (func $select (type $3) + (drop + (i64.eqz + (select + (unreachable) + (i32.const 1) + (i32.const 2) + ) + ) + ) + ) + (func $untaken-break-should-have-value (type $1) (result i32) + (block $x (result i32) + (block $block + (br_if $x + (unreachable) + ) + ) + ) + ) +) diff --git a/test/polymorphic_stack.wast.fromBinary b/test/polymorphic_stack.wast.fromBinary new file mode 100644 index 000000000..e0ee6577d --- /dev/null +++ b/test/polymorphic_stack.wast.fromBinary @@ -0,0 +1,129 @@ +(module + (type $0 (func (param i32) (result i32))) + (type $1 (func (result i32))) + (type $2 (func (param i32))) + (type $3 (func)) + (import "env" "table" (table 9 9 anyfunc)) + (memory $0 0) + (func $break-and-binary (type $1) (result i32) + (block $label$0 (result i32) + (unreachable) + (i32.trunc_u/f64 + (unreachable) + ) + (unreachable) + (br_if $label$0 + (i32.trunc_u/f64 + (unreachable) + ) + (unreachable) + ) + (f32.add + (unreachable) + (f32.const 1) + ) + (unreachable) + ) + ) + (func $call-and-unary (type $0) (param $var$0 i32) (result i32) + (block $label$0 (result i32) + (unreachable) + (call $call-and-unary + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + (i32.eqz + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + (call_indirect $0 + (unreachable) + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + ) + ) + (func $tee (type $2) (param $var$0 i32) + (local $var$1 f32) + (block $label$0 + (unreachable) + (tee_local $var$0 + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (tee_local $var$1 + (unreachable) + ) + (drop + (unreachable) + ) + (unreachable) + ) + (unreachable) + ) + (func $tee2 (type $3) + (local $var$0 f32) + (if + (i32.const 259) + (block $label$0 + (unreachable) + (tee_local $var$0 + (unreachable) + ) + (unreachable) + ) + ) + ) + (func $select (type $3) + (unreachable) + (select + (unreachable) + (i32.const 1) + (i32.const 2) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + ) + (func $untaken-break-should-have-value (type $1) (result i32) + (block $label$0 (result i32) + (block $label$1 + (unreachable) + (br_if $label$0 + (unreachable) + (unreachable) + ) + (unreachable) + (unreachable) + ) + (unreachable) + ) + ) +) + diff --git a/test/polymorphic_stack.wast.fromBinary.noDebugInfo b/test/polymorphic_stack.wast.fromBinary.noDebugInfo new file mode 100644 index 000000000..857a3660c --- /dev/null +++ b/test/polymorphic_stack.wast.fromBinary.noDebugInfo @@ -0,0 +1,129 @@ +(module + (type $0 (func (param i32) (result i32))) + (type $1 (func (result i32))) + (type $2 (func (param i32))) + (type $3 (func)) + (import "env" "table" (table 9 9 anyfunc)) + (memory $0 0) + (func $0 (type $1) (result i32) + (block $label$0 (result i32) + (unreachable) + (i32.trunc_u/f64 + (unreachable) + ) + (unreachable) + (br_if $label$0 + (i32.trunc_u/f64 + (unreachable) + ) + (unreachable) + ) + (f32.add + (unreachable) + (f32.const 1) + ) + (unreachable) + ) + ) + (func $1 (type $0) (param $var$0 i32) (result i32) + (block $label$0 (result i32) + (unreachable) + (call $1 + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + (i32.eqz + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + (call_indirect $0 + (unreachable) + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + ) + ) + (func $2 (type $2) (param $var$0 i32) + (local $var$1 f32) + (block $label$0 + (unreachable) + (tee_local $var$0 + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + (i64.eqz + (unreachable) + ) + (tee_local $var$1 + (unreachable) + ) + (drop + (unreachable) + ) + (unreachable) + ) + (unreachable) + ) + (func $3 (type $3) + (local $var$0 f32) + (if + (i32.const 259) + (block $label$0 + (unreachable) + (tee_local $var$0 + (unreachable) + ) + (unreachable) + ) + ) + ) + (func $4 (type $3) + (unreachable) + (select + (unreachable) + (i32.const 1) + (i32.const 2) + ) + (i64.eqz + (unreachable) + ) + (drop + (unreachable) + ) + ) + (func $5 (type $1) (result i32) + (block $label$0 (result i32) + (block $label$1 + (unreachable) + (br_if $label$0 + (unreachable) + (unreachable) + ) + (unreachable) + (unreachable) + ) + (unreachable) + ) + ) +) + diff --git a/test/unit.wast.fromBinary b/test/unit.wast.fromBinary index 7656dc7d7..78ae640b1 100644 --- a/test/unit.wast.fromBinary +++ b/test/unit.wast.fromBinary @@ -479,6 +479,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $unreachable-block-toplevel (type $5) (result i32) (block $label$0 @@ -502,6 +503,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $unreachable-block0-toplevel (type $5) (result i32) (block $label$0 @@ -540,6 +542,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $unreachable-if-toplevel (type $5) (result i32) (if @@ -567,6 +570,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $unreachable-loop0 (type $5) (result i32) (loop $label$0 @@ -577,6 +581,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $unreachable-loop-toplevel (type $5) (result i32) (loop $label$0 diff --git a/test/unit.wast.fromBinary.noDebugInfo b/test/unit.wast.fromBinary.noDebugInfo index bfcc12c6b..3c24886f5 100644 --- a/test/unit.wast.fromBinary.noDebugInfo +++ b/test/unit.wast.fromBinary.noDebugInfo @@ -479,6 +479,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $25 (type $5) (result i32) (block $label$0 @@ -502,6 +503,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $27 (type $5) (result i32) (block $label$0 @@ -540,6 +542,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $30 (type $5) (result i32) (if @@ -567,6 +570,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $32 (type $5) (result i32) (loop $label$0 @@ -577,6 +581,7 @@ (f64.abs (unreachable) ) + (unreachable) ) (func $33 (type $5) (result i32) (loop $label$0 -- cgit v1.2.3