diff options
| -rw-r--r-- | src/passes/Precompute.cpp | 54 | ||||
| -rw-r--r-- | src/wasm/literal.cpp | 3 | ||||
| -rw-r--r-- | test/lit/passes/precompute-gc.wast | 359 | ||||
| -rw-r--r-- | test/passes/Oz_fuzz-exec_all-features.txt | 141 | ||||
| -rw-r--r-- | test/passes/Oz_fuzz-exec_all-features.wast | 4 |
5 files changed, 531 insertions, 30 deletions
diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp index 85e09f875..c07286ec9 100644 --- a/src/passes/Precompute.cpp +++ b/src/passes/Precompute.cpp @@ -87,6 +87,15 @@ public: return ConstantExpressionRunner< PrecomputingExpressionRunner>::visitLocalGet(curr); } + + // Heap data may be modified in ways we do not see. We would need escape + // analysis to avoid that risk. For now, disallow all heap operations. + // TODO: immutability might also be good enough + Flow visitStructNew(StructNew* curr) { return Flow(NONCONSTANT_FLOW); } + Flow visitStructGet(StructGet* curr) { return Flow(NONCONSTANT_FLOW); } + Flow visitArrayNew(ArrayNew* curr) { return Flow(NONCONSTANT_FLOW); } + Flow visitArrayGet(ArrayGet* curr) { return Flow(NONCONSTANT_FLOW); } + Flow visitArrayLen(ArrayLen* curr) { return Flow(NONCONSTANT_FLOW); } }; struct Precompute @@ -226,16 +235,21 @@ private: // Precompute an expression, returning a flow, which may be a constant // (that we can replace the expression with if replaceExpression is set). Flow precomputeExpression(Expression* curr, bool replaceExpression = true) { - if (!canEmitConstantFor(curr->type)) { - return Flow(NONCONSTANT_FLOW); - } + Flow flow; try { - return PrecomputingExpressionRunner( - getModule(), getValues, replaceExpression) - .visit(curr); + flow = + PrecomputingExpressionRunner(getModule(), getValues, replaceExpression) + .visit(curr); } catch (PrecomputingExpressionRunner::NonconstantException&) { return Flow(NONCONSTANT_FLOW); } + // If we are replacing the expression, then the resulting value must be of + // a type we can emit a constant for. + if (!flow.breaking() && replaceExpression && + !canEmitConstantFor(flow.values)) { + return Flow(NONCONSTANT_FLOW); + } + return flow; } // Precomputes the value of an expression, as opposed to the expression @@ -286,6 +300,17 @@ private: if (setValues[set].isConcrete()) { continue; // already known constant } + // Precompute the value. Note that this executes the code from scratch + // each time we reach this point, and so we need to be careful about + // repeating side effects if those side effects are expressed *in the + // value*. A case where that can happen is GC data (each struct.new + // creates a new, unique struct, even if the data is equal), and so + // PrecomputingExpressionRunner will return a nonconstant flow for all + // GC heap operations. + // (Other side effects are fine; if an expression does a call and we + // somehow know the entire expression precomputes to a 42, then we can + // propagate that 42 along to the users, regardless of whatever the call + // did globally.) auto values = setValues[set] = precomputeValue(Properties::getFallthrough( set->value, getPassOptions(), getModule()->features)); @@ -360,19 +385,22 @@ private: if (value.isNull()) { return true; } + return canEmitConstantFor(value.type); + } + + bool canEmitConstantFor(Type type) { // A function is fine to emit a constant for - we'll emit a RefFunc, which // is compact and immutable, so there can't be a problem. - if (value.type.isFunction()) { + if (type.isFunction()) { return true; } - // All other reference types cannot be precomputed. - if (value.type.isRef()) { + // All other reference types cannot be precomputed. Even an immutable GC + // reference is not currently something this pass can handle, as it will + // evaluate and reevaluate code multiple times in e.g. optimizeLocals, see + // the comment above. + if (type.isRef()) { return false; } - return canEmitConstantFor(value.type); - } - - bool canEmitConstantFor(Type type) { // For now, don't try to precompute an Rtt. TODO figure out when that would // be safe and useful. return !type.isRtt(); diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp index 0c5a48b8e..4f3979097 100644 --- a/src/wasm/literal.cpp +++ b/src/wasm/literal.cpp @@ -350,6 +350,9 @@ bool Literal::operator==(const Literal& other) const { assert(func.is() && other.func.is()); return func == other.func; } + if (type.isData()) { + return gcData == other.gcData; + } // other non-null reference type literals cannot represent concrete values, // i.e. there is no concrete externref, anyref or eqref other than null. WASM_UNREACHABLE("unexpected type"); diff --git a/test/lit/passes/precompute-gc.wast b/test/lit/passes/precompute-gc.wast index 9402aa068..0cd6d2c2c 100644 --- a/test/lit/passes/precompute-gc.wast +++ b/test/lit/passes/precompute-gc.wast @@ -1,8 +1,13 @@ ;; NOTE: Assertions have been generated by update_lit_checks.py and should not be edited. -;; RUN: wasm-opt %s --remove-unused-names --precompute-propagate -all -S -o - \ +;; RUN: wasm-opt %s --remove-unused-names --precompute-propagate --fuzz-exec -all -S -o - \ ;; RUN: | filecheck %s (module + (type $struct (struct (mut i32))) + (type $empty (struct)) + + (import "fuzzing-support" "log-i32" (func $log (param i32))) + ;; CHECK: (func $test-fallthrough (result i32) ;; CHECK-NEXT: (local $x funcref) ;; CHECK-NEXT: (local.set $x @@ -34,4 +39,356 @@ (local.get $x) ) ) + + ;; CHECK: (func $load-from-struct + ;; CHECK-NEXT: (local $x (ref null $struct)) + ;; CHECK-NEXT: (local.set $x + ;; CHECK-NEXT: (struct.new_with_rtt $struct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (rtt.canon $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.set $x + ;; CHECK-NEXT: (struct.new_with_rtt $struct + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: (rtt.canon $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.set $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.const 3) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $load-from-struct + (local $x (ref null $struct)) + (local.set $x + (struct.new_with_rtt $struct + (i32.const 1) + (rtt.canon $struct) + ) + ) + ;; we don't precompute these, as we don't know if the GC data was modified + ;; elsewhere (we'd need immutability or escape analysis) + (call $log + (struct.get $struct 0 (local.get $x)) + ) + ;; Assign a new struct + (local.set $x + (struct.new_with_rtt $struct + (i32.const 2) + (rtt.canon $struct) + ) + ) + (call $log + (struct.get $struct 0 (local.get $x)) + ) + ;; Assign a new value + (struct.set $struct 0 + (local.get $x) + (i32.const 3) + ) + (call $log + (struct.get $struct 0 (local.get $x)) + ) + ) + ;; CHECK: (func $load-from-struct-bad-merge (param $i i32) + ;; CHECK-NEXT: (local $x (ref null $struct)) + ;; CHECK-NEXT: (if + ;; CHECK-NEXT: (local.get $i) + ;; CHECK-NEXT: (local.set $x + ;; CHECK-NEXT: (struct.new_with_rtt $struct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (rtt.canon $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.set $x + ;; CHECK-NEXT: (struct.new_with_rtt $struct + ;; CHECK-NEXT: (i32.const 2) + ;; CHECK-NEXT: (rtt.canon $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $load-from-struct-bad-merge (param $i i32) + (local $x (ref null $struct)) + ;; a merge of two different $x values cannot be precomputed + (if + (local.get $i) + (local.set $x + (struct.new_with_rtt $struct + (i32.const 1) + (rtt.canon $struct) + ) + ) + (local.set $x + (struct.new_with_rtt $struct + (i32.const 2) + (rtt.canon $struct) + ) + ) + ) + (call $log + (struct.get $struct 0 (local.get $x)) + ) + ) + ;; CHECK: (func $modify-gc-heap (param $x (ref null $struct)) + ;; CHECK-NEXT: (struct.set $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (i32.add + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $modify-gc-heap (param $x (ref null $struct)) + (struct.set $struct 0 + (local.get $x) + (i32.add + (struct.get $struct 0 + (local.get $x) + ) + (i32.const 1) + ) + ) + ) + ;; --fuzz-exec verifies the output of this function, checking that the change + ;; makde in modify-gc-heap is not ignored + ;; CHECK: (func $load-from-struct-bad-escape + ;; CHECK-NEXT: (local $x (ref null $struct)) + ;; CHECK-NEXT: (local.set $x + ;; CHECK-NEXT: (struct.new_with_rtt $struct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (rtt.canon $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $modify-gc-heap + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $load-from-struct-bad-escape (export "test") + (local $x (ref null $struct)) + (local.set $x + (struct.new_with_rtt $struct + (i32.const 1) + (rtt.canon $struct) + ) + ) + (call $modify-gc-heap + (local.get $x) + ) + (call $log + (struct.get $struct 0 (local.get $x)) + ) + ) + ;; CHECK: (func $load-from-struct-bad-arrive (param $x (ref null $struct)) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (struct.get $struct 0 + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $load-from-struct-bad-arrive (param $x (ref null $struct)) + ;; a parameter cannot be precomputed + (call $log + (struct.get $struct 0 (local.get $x)) + ) + ) + ;; CHECK: (func $ref-comparisons (param $x (ref null $struct)) (param $y (ref null $struct)) + ;; CHECK-NEXT: (local $z (ref null $struct)) + ;; CHECK-NEXT: (local $w (ref null $struct)) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (ref.null $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (call $log + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $ref-comparisons + (param $x (ref null $struct)) + (param $y (ref null $struct)) + (local $z (ref null $struct)) + (local $w (ref null $struct)) + ;; incoming parameters are unknown + (call $log + (ref.eq + (local.get $x) + (local.get $y) + ) + ) + (call $log + (ref.eq + (local.get $x) + ;; locals are ref.null which are known, and will be propagated + (local.get $z) + ) + ) + (call $log + (ref.eq + (local.get $x) + (local.get $w) + ) + ) + ;; null-initialized locals are known and can be compared + (call $log + (ref.eq + (local.get $z) + (local.get $w) + ) + ) + ) + ;; CHECK: (func $new-ref-comparisons (result i32) + ;; CHECK-NEXT: (local $x (ref null $struct)) + ;; CHECK-NEXT: (local $y (ref null $struct)) + ;; CHECK-NEXT: (local $tempresult i32) + ;; CHECK-NEXT: (local.set $x + ;; CHECK-NEXT: (struct.new_with_rtt $struct + ;; CHECK-NEXT: (i32.const 1) + ;; CHECK-NEXT: (rtt.canon $struct) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.set $y + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.set $tempresult + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (local.get $x) + ;; CHECK-NEXT: (local.get $y) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $tempresult) + ;; CHECK-NEXT: ) + (func $new-ref-comparisons (result i32) + (local $x (ref null $struct)) + (local $y (ref null $struct)) + (local $tempresult i32) + (local.set $x + (struct.new_with_rtt $struct + (i32.const 1) + (rtt.canon $struct) + ) + ) + (local.set $y + (local.get $x) + ) + ;; assign the result, so that propagate calculates the ref.eq + (local.set $tempresult + (ref.eq + (local.get $x) + (local.get $y) + ) + ) + ;; this value could be precomputed in principle, however, we currently do not + ;; precompute GC references, and so nothing will be done. + (local.get $tempresult) + ) + ;; CHECK: (func $propagate-equal (result i32) + ;; CHECK-NEXT: (local $tempresult i32) + ;; CHECK-NEXT: (local $tempref (ref null $empty)) + ;; CHECK-NEXT: (local.set $tempresult + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (local.tee $tempref + ;; CHECK-NEXT: (struct.new_default_with_rtt $empty + ;; CHECK-NEXT: (rtt.canon $empty) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $tempref) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $tempresult) + ;; CHECK-NEXT: ) + (func $propagate-equal (result i32) + (local $tempresult i32) + (local $tempref (ref null $empty)) + ;; assign the result, so that propagate calculates the ref.eq + (local.set $tempresult + (ref.eq + ;; allocate one struct + (local.tee $tempref + (struct.new_with_rtt $empty + (rtt.canon $empty) + ) + ) + (local.get $tempref) + ) + ) + ;; this value could be precomputed in principle, however, we currently do not + ;; precompute GC references, and so nothing will be done. + (local.get $tempresult) + ) + ;; CHECK: (func $propagate-unequal (result i32) + ;; CHECK-NEXT: (local $tempresult i32) + ;; CHECK-NEXT: (local $tempref (ref null $empty)) + ;; CHECK-NEXT: (local.set $tempresult + ;; CHECK-NEXT: (ref.eq + ;; CHECK-NEXT: (struct.new_default_with_rtt $empty + ;; CHECK-NEXT: (rtt.canon $empty) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (struct.new_default_with_rtt $empty + ;; CHECK-NEXT: (rtt.canon $empty) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (local.get $tempresult) + ;; CHECK-NEXT: ) + (func $propagate-unequal (result i32) + (local $tempresult i32) + (local $tempref (ref null $empty)) + ;; assign the result, so that propagate calculates the ref.eq + (local.set $tempresult + ;; allocate two different structs + (ref.eq + (struct.new_with_rtt $empty + (rtt.canon $empty) + ) + (struct.new_with_rtt $empty + (rtt.canon $empty) + ) + ) + ) + ;; this value could be precomputed in principle, however, we currently do not + ;; precompute GC references, and so nothing will be done. + (local.get $tempresult) + ) ) diff --git a/test/passes/Oz_fuzz-exec_all-features.txt b/test/passes/Oz_fuzz-exec_all-features.txt index b7c7688b5..618fa2333 100644 --- a/test/passes/Oz_fuzz-exec_all-features.txt +++ b/test/passes/Oz_fuzz-exec_all-features.txt @@ -35,11 +35,13 @@ [fuzz-exec] calling array-alloc-failure [host limit allocation failure] (module + (type $struct (struct (field (mut i32)))) (type $void_func (func)) + (type $extendedstruct (struct (field (mut i32)) (field f64))) + (type $bytes (array (mut i8))) (type $i32_=>_none (func (param i32))) (type $anyref_=>_none (func (param anyref))) (type $int_func (func (result i32))) - (type $struct (struct (field (mut i32)))) (import "fuzzing-support" "log-i32" (func $log (param i32))) (elem declare func $a-void-func) (export "structs" (func $0)) @@ -51,37 +53,85 @@ (export "rtt-and-cast-on-func" (func $8)) (export "array-alloc-failure" (func $9)) (func $0 (; has Stack IR ;) + (local $0 (ref null $struct)) (call $log - (i32.const 0) + (struct.get $struct 0 + (local.tee $0 + (struct.new_default_with_rtt $struct + (rtt.canon $struct) + ) + ) + ) ) - (call $log + (struct.set $struct 0 + (local.get $0) (i32.const 42) ) (call $log + (struct.get $struct 0 + (local.get $0) + ) + ) + (struct.set $struct 0 + (local.get $0) (i32.const 100) ) (call $log - (i32.const 100) + (struct.get $struct 0 + (local.get $0) + ) + ) + (call $log + (struct.get $struct 0 + (local.get $0) + ) ) ) (func $1 (; has Stack IR ;) + (local $0 (ref null $bytes)) (call $log - (i32.const 50) + (array.len $bytes + (local.tee $0 + (array.new_with_rtt $bytes + (i32.const 42) + (i32.const 50) + (rtt.canon $bytes) + ) + ) + ) ) (call $log - (i32.const 42) + (array.get_u $bytes + (local.get $0) + (i32.const 10) + ) ) - (call $log + (array.set $bytes + (local.get $0) + (i32.const 10) (i32.const 128) ) (call $log - (i32.const -128) + (array.get_u $bytes + (local.get $0) + (i32.const 10) + ) ) (call $log - (i32.const 42) + (array.get_s $bytes + (local.get $0) + (i32.const 10) + ) + ) + (call $log + (array.get_s $bytes + (local.get $0) + (i32.const 20) + ) ) ) (func $2 (; has Stack IR ;) + (local $0 anyref) (call $log (i32.const 1) ) @@ -89,25 +139,86 @@ (i32.const 0) ) (call $log - (i32.const 0) + (ref.test + (array.new_with_rtt $bytes + (i32.const 20) + (i32.const 10) + (rtt.canon $bytes) + ) + (rtt.canon $struct) + ) ) (call $log - (i32.const 1) + (ref.test + (struct.new_default_with_rtt $struct + (rtt.canon $struct) + ) + (rtt.canon $struct) + ) ) (call $log - (i32.const 0) + (ref.test + (struct.new_default_with_rtt $struct + (rtt.canon $struct) + ) + (rtt.canon $extendedstruct) + ) ) (call $log - (i32.const 1) + (ref.test + (local.tee $0 + (struct.new_default_with_rtt $extendedstruct + (rtt.sub $extendedstruct + (rtt.canon $struct) + ) + ) + ) + (rtt.sub $extendedstruct + (rtt.canon $struct) + ) + ) ) (call $log - (i32.const 0) + (ref.test + (local.get $0) + (rtt.canon $extendedstruct) + ) ) (call $log - (i32.const 1) + (ref.test + (local.get $0) + (rtt.canon $struct) + ) ) ) (func $3 (; has Stack IR ;) + (drop + (block $block (result (ref $struct)) + (drop + (block $extendedblock (result (ref $extendedstruct)) + (drop + (br_on_cast $block + (br_on_cast $extendedblock + (struct.new_default_with_rtt $struct + (rtt.canon $struct) + ) + (rtt.canon $extendedstruct) + ) + (rtt.canon $struct) + ) + ) + (call $log + (i32.const -1) + ) + (return) + ) + ) + (call $log + (i32.const -2) + ) + (return) + ) + ) (call $log (i32.const 3) ) diff --git a/test/passes/Oz_fuzz-exec_all-features.wast b/test/passes/Oz_fuzz-exec_all-features.wast index c88133c3a..87f2e24e3 100644 --- a/test/passes/Oz_fuzz-exec_all-features.wast +++ b/test/passes/Oz_fuzz-exec_all-features.wast @@ -17,7 +17,9 @@ ) ) ;; The value is initialized to 0 - ;; Note: -Oz will optimize all these to constants thanks to Precompute + ;; Note: We cannot optimize these to constants without either immutability or + ;; some kind of escape analysis (to verify that the GC data referred to is not + ;; written to elsewhere). (call $log (struct.get $struct 0 (local.get $x)) ) |