From 04418d5617f6ab7015c5cf7b905b4775a5219f4b Mon Sep 17 00:00:00 2001 From: "Alon Zakai (kripken)" Date: Mon, 31 Jul 2017 14:11:33 -0700 Subject: use effective shifts in more places in optimize-instructions --- src/ast/bits.h | 3 ++- src/ast/properties.h | 8 ++++---- src/passes/OptimizeInstructions.cpp | 4 ++-- 3 files changed, 8 insertions(+), 7 deletions(-) (limited to 'src') diff --git a/src/ast/bits.h b/src/ast/bits.h index 11cf7b06d..0aee50ffe 100644 --- a/src/ast/bits.h +++ b/src/ast/bits.h @@ -51,7 +51,8 @@ struct Bits { WASM_UNREACHABLE(); } - static Index getEffectiveShifts(Const* amount) { + static Index getEffectiveShifts(Expression* expr) { + auto* amount = expr->cast(); if (amount->type == i32) { return getEffectiveShifts(amount->value.geti32(), i32); } else if (amount->type == i64) { diff --git a/src/ast/properties.h b/src/ast/properties.h index 097f7a8f0..8c8655c07 100644 --- a/src/ast/properties.h +++ b/src/ast/properties.h @@ -79,7 +79,7 @@ struct Properties { // gets the size of the sign-extended value static Index getSignExtBits(Expression* curr) { - return 32 - curr->cast()->right->cast()->value.geti32(); + return 32 - Bits::getEffectiveShifts(curr->cast()->right); } // Check if an expression is almost a sign-extend: perhaps the inner shift @@ -93,7 +93,7 @@ struct Properties { if (auto* inner = outer->left->dynCast()) { if (inner->op == ShlInt32) { if (auto* innerConst = inner->right->dynCast()) { - if (outerConst->value.leU(innerConst->value).geti32()) { + if (Bits::getEffectiveShifts(outerConst) <= Bits::getEffectiveShifts(innerConst)) { return inner->left; } } @@ -109,8 +109,8 @@ struct Properties { // gets the size of the almost sign-extended value, as well as the // extra shifts, if any static Index getAlmostSignExtBits(Expression* curr, Index& extraShifts) { - extraShifts = curr->cast()->left->cast()->right->cast()->value.geti32() - - curr->cast()->right->cast()->value.geti32(); + extraShifts = Bits::getEffectiveShifts(curr->cast()->left->cast()->right) - + Bits::getEffectiveShifts(curr->cast()->right); return getSignExtBits(curr); } diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 4fd7cbe8d..578a01f11 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -779,7 +779,7 @@ private: return; } else if (binary->op == ShlInt32) { if (auto* c = binary->right->dynCast()) { - seek(binary->left, mul * Pow2(c->value.geti32())); + seek(binary->left, mul * Pow2(Bits::getEffectiveShifts(c))); return; } } else if (binary->op == MulInt32) { @@ -836,7 +836,7 @@ private: } } else if (curr->op == ShlInt32) { // shifting a 0 is a 0, unless the shift has side effects - if (left && left->value.geti32() == 0 && !EffectAnalyzer(passOptions, curr->right).hasSideEffects()) { + if (left && Bits::getEffectiveShifts(left) == 0 && !EffectAnalyzer(passOptions, curr->right).hasSideEffects()) { replaceCurrent(left); return; } -- cgit v1.2.3 From 114ed43b24d3c74112b922a7469c48c736172833 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Tue, 1 Aug 2017 10:22:31 -0700 Subject: fix proper wasm emitting of untaken br_tables --- src/wasm/wasm-binary.cpp | 10 +++++++++- test/polymorphic_stack.wast | 10 ++++++++++ test/polymorphic_stack.wast.from-wast | 10 ++++++++++ test/polymorphic_stack.wast.fromBinary | 11 +++++++++++ test/polymorphic_stack.wast.fromBinary.noDebugInfo | 11 +++++++++++ 5 files changed, 51 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp index 88b967fdf..47bcc8ba5 100644 --- a/src/wasm/wasm-binary.cpp +++ b/src/wasm/wasm-binary.cpp @@ -666,6 +666,14 @@ void WasmBinaryWriter::visitSwitch(Switch *curr) { recurse(curr->value); } recurse(curr->condition); + if (!BranchUtils::isBranchTaken(curr)) { + // if the branch is not taken, then it's dangerous to emit it, as + // wasm type checking rules are stricter than ours - we tolerate + // an untaken branch to a target with a different value, but not + // wasm. so just don't emit it + o << int8_t(BinaryConsts::Unreachable); + return; + } o << int8_t(BinaryConsts::TableSwitch) << U32LEB(curr->targets.size()); for (auto target : curr->targets) { o << U32LEB(getBreakIndex(target)); @@ -1796,7 +1804,7 @@ void WasmBinaryBuilder::processExpressions() { // until an end or else marker, o Expression* WasmBinaryBuilder::popExpression() { if (expressionStack.empty()) { - throw ParseException("attempted pop from empty stack"); + throw ParseException("attempted pop from empty stack at " + std::to_string(pos)); } auto ret = expressionStack.back(); // to simulate the wasm polymorphic stack mode, leave a final diff --git a/test/polymorphic_stack.wast b/test/polymorphic_stack.wast index 2241ab910..b618fbb6c 100644 --- a/test/polymorphic_stack.wast +++ b/test/polymorphic_stack.wast @@ -86,5 +86,15 @@ ) ) ) + (func $br_table_unreachable_to_also_unreachable (result i32) + (block $a (result i32) + (block $b + (br_table $a $b ;; seems to send a value, but is not taken + (unreachable) + (unreachable) + ) + ) + ) + ) ) diff --git a/test/polymorphic_stack.wast.from-wast b/test/polymorphic_stack.wast.from-wast index b4b88f16b..c20f9218d 100644 --- a/test/polymorphic_stack.wast.from-wast +++ b/test/polymorphic_stack.wast.from-wast @@ -90,4 +90,14 @@ ) ) ) + (func $br_table_unreachable_to_also_unreachable (type $1) (result i32) + (block $a (result i32) + (block $b + (br_table $a $b + (unreachable) + (unreachable) + ) + ) + ) + ) ) diff --git a/test/polymorphic_stack.wast.fromBinary b/test/polymorphic_stack.wast.fromBinary index e0ee6577d..b139c9c06 100644 --- a/test/polymorphic_stack.wast.fromBinary +++ b/test/polymorphic_stack.wast.fromBinary @@ -125,5 +125,16 @@ (unreachable) ) ) + (func $br_table_unreachable_to_also_unreachable (type $1) (result i32) + (block $label$0 (result i32) + (block $label$1 + (unreachable) + (unreachable) + (unreachable) + (unreachable) + ) + (unreachable) + ) + ) ) diff --git a/test/polymorphic_stack.wast.fromBinary.noDebugInfo b/test/polymorphic_stack.wast.fromBinary.noDebugInfo index 857a3660c..e707d5046 100644 --- a/test/polymorphic_stack.wast.fromBinary.noDebugInfo +++ b/test/polymorphic_stack.wast.fromBinary.noDebugInfo @@ -125,5 +125,16 @@ (unreachable) ) ) + (func $6 (type $1) (result i32) + (block $label$0 (result i32) + (block $label$1 + (unreachable) + (unreachable) + (unreachable) + (unreachable) + ) + (unreachable) + ) + ) ) -- cgit v1.2.3 From 6d686bd1a5b3610ad49fd607ae5e49c70410af51 Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Tue, 1 Aug 2017 15:42:24 -0700 Subject: fix off-by-one error in clz/ctz/popcount used bits computation --- src/passes/OptimizeInstructions.cpp | 4 +-- test/passes/optimize-instructions.txt | 62 +++++++++++++++++++++++++++++----- test/passes/optimize-instructions.wast | 40 ++++++++++++++++++++++ 3 files changed, 95 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp index 578a01f11..f458a58b2 100644 --- a/src/passes/OptimizeInstructions.cpp +++ b/src/passes/OptimizeInstructions.cpp @@ -228,8 +228,8 @@ Index getMaxBits(Expression* curr, LocalInfoProvider* localInfoProvider) { } } else if (auto* unary = curr->dynCast()) { switch (unary->op) { - case ClzInt32: case CtzInt32: case PopcntInt32: return 5; - case ClzInt64: case CtzInt64: case PopcntInt64: return 6; + case ClzInt32: case CtzInt32: case PopcntInt32: return 6; + case ClzInt64: case CtzInt64: case PopcntInt64: return 7; case EqZInt32: case EqZInt64: return 1; case WrapInt64: return std::min(Index(32), getMaxBits(unary->value, localInfoProvider)); default: {} diff --git a/test/passes/optimize-instructions.txt b/test/passes/optimize-instructions.txt index 2e46379fb..55501dfb8 100644 --- a/test/passes/optimize-instructions.txt +++ b/test/passes/optimize-instructions.txt @@ -7,6 +7,7 @@ (type $5 (func (param i32))) (type $6 (func (param i32 i32) (result i32))) (type $7 (func (param i64) (result i64))) + (type $8 (func (result i64))) (memory $0 0) (export "load-off-2" (func $load-off-2)) (func $f (type $0) (param $i1 i32) (param $i2 i64) @@ -827,11 +828,14 @@ ) ) (drop - (i32.shl - (i32.clz - (i32.const 0) + (i32.shr_s + (i32.shl + (i32.clz + (i32.const 0) + ) + (i32.const 26) ) - (i32.const 2) + (i32.const 24) ) ) (drop @@ -853,13 +857,16 @@ ) ) (drop - (i32.shl - (i32.wrap/i64 - (i64.clz - (i64.const 0) + (i32.shr_s + (i32.shl + (i32.wrap/i64 + (i64.clz + (i64.const 0) + ) ) + (i32.const 25) ) - (i32.const 1) + (i32.const 24) ) ) (drop @@ -2076,4 +2083,41 @@ (func $less-shifts-than-it-seems (type $3) (param $x i32) (result i32) (i32.const 4800) ) + (func $and-popcount32 (type $2) (result i32) + (i32.and + (i32.popcnt + (i32.const -1) + ) + (i32.const 31) + ) + ) + (func $and-popcount32-big (type $2) (result i32) + (i32.popcnt + (i32.const -1) + ) + ) + (func $and-popcount64 (type $8) (result i64) + (i64.and + (i64.popcnt + (i64.const -1) + ) + (i64.const 63) + ) + ) + (func $and-popcount64-big (type $8) (result i64) + (i64.and + (i64.popcnt + (i64.const -1) + ) + (i64.const 127) + ) + ) + (func $and-popcount64-bigger (type $8) (result i64) + (i64.and + (i64.popcnt + (i64.const -1) + ) + (i64.const 255) + ) + ) ) diff --git a/test/passes/optimize-instructions.wast b/test/passes/optimize-instructions.wast index 517c74ea6..c26aad196 100644 --- a/test/passes/optimize-instructions.wast +++ b/test/passes/optimize-instructions.wast @@ -2526,4 +2526,44 @@ ) ) ) + (func $and-popcount32 (result i32) + (i32.and + (i32.popcnt + (i32.const -1) + ) + (i32.const 31) + ) + ) + (func $and-popcount32-big (result i32) + (i32.and + (i32.popcnt + (i32.const -1) + ) + (i32.const 63) + ) + ) + (func $and-popcount64 (result i64) ;; these are TODOs + (i64.and + (i64.popcnt + (i64.const -1) + ) + (i64.const 63) + ) + ) + (func $and-popcount64-big (result i64) + (i64.and + (i64.popcnt + (i64.const -1) + ) + (i64.const 127) + ) + ) + (func $and-popcount64-bigger (result i64) + (i64.and + (i64.popcnt + (i64.const -1) + ) + (i64.const 255) + ) + ) ) -- cgit v1.2.3