diff options
| -rw-r--r-- | src/ir/possible-contents.cpp | 23 | ||||
| -rw-r--r-- | test/lit/passes/gufa-refs.wast | 46 |
2 files changed, 59 insertions, 10 deletions
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp index 35e87175a..d388d281c 100644 --- a/src/ir/possible-contents.cpp +++ b/src/ir/possible-contents.cpp @@ -22,13 +22,8 @@ #include "ir/local-graph.h" #include "ir/module-utils.h" #include "ir/possible-contents.h" -#include "wasm.h" - -#ifdef POSSIBLE_CONTENTS_INSERT_ORDERED -// Use an insert-ordered set for easier debugging with deterministic queue -// ordering. #include "support/insert_ordered.h" -#endif +#include "wasm.h" namespace std { @@ -1338,11 +1333,19 @@ private: // possible is helpful as anything reading them meanwhile (before we get to // their work item in the queue) will see the newer value, possibly avoiding // flowing an old value that would later be overwritten. -#ifdef POSSIBLE_CONTENTS_INSERT_ORDERED + // + // This must be ordered to avoid nondeterminism. The problem is that our + // operations are imprecise and so the transitive property does not hold: + // (AvB)vC may differ from Av(BvC). Likewise (AvB)^C may differ from + // (A^C)v(B^C). An example of the latter is if a location is sent a null func + // and an i31, and the location can only contain funcref. If the null func + // arrives first, then later we'd merge null func + i31 which ends up as Many, + // and then we filter that to funcref and get funcref. But if the i31 arrived + // first, we'd filter it into nothing, and then the null func that arrives + // later would be the final result. This would not happen if our operations + // were precise, but we only make approximations here to avoid unacceptable + // overhead, such as cone types but not arbitrary unions, etc. InsertOrderedSet<LocationIndex> workQueue; -#else - std::unordered_set<LocationIndex> workQueue; -#endif // All existing links in the graph. We keep this to know when a link we want // to add is new or not. diff --git a/test/lit/passes/gufa-refs.wast b/test/lit/passes/gufa-refs.wast index fc01dd481..3f2e166a2 100644 --- a/test/lit/passes/gufa-refs.wast +++ b/test/lit/passes/gufa-refs.wast @@ -14,6 +14,8 @@ ;; CHECK: (type $none_=>_ref|any| (func_subtype (result (ref any)) func)) + ;; CHECK: (type $none_=>_funcref (func_subtype (result funcref) func)) + ;; CHECK: (import "a" "b" (func $import (result i32))) (import "a" "b" (func $import (result i32))) @@ -358,6 +360,50 @@ (local.get $z) ) ) + + ;; CHECK: (func $nondeterminism (type $none_=>_funcref) (result funcref) + ;; CHECK-NEXT: (block $label$1 (result funcref) + ;; CHECK-NEXT: (drop + ;; CHECK-NEXT: (br_on_func $label$1 + ;; CHECK-NEXT: (i31.new + ;; CHECK-NEXT: (i32.const 1337) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: (ref.null nofunc) + ;; CHECK-NEXT: ) + ;; CHECK-NEXT: ) + (func $nondeterminism (result funcref) + ;; This block is sent an i31 and a null. The null is compatible with the + ;; type and the i31 is not. The order in which we process this matters: + ;; + ;; * If the i31 arrives first, we'll filter it out as incompatible with the + ;; type of the block. Then the null arrives and the final result is that + ;; null, which we can then optimize the block to return. + ;; * Or, if the null arrives first, then when the i31 arrives the + ;; combination of nullfunc + i31 is Many (since the types are + ;; incompatible). We then filter that to the block's type, ending up with + ;; a cone of funcref. We cannot optimize in that case, unlike before. + ;; + ;; Ideally we'd optimize here, but atm we do not since the order in + ;; practice is a less ideal one. At minimum we should be deterministic in + ;; how we handle this, which this test enforces at least. + ;; + ;; TODO: Find a way to actually optimize such cases, perhaps by filtering + ;; when sending as well and not just when receiving (the br_on_func + ;; here should not send anything, as what it sends should be first + ;; intersected with funcref). + (block $label$1 (result funcref) + (drop + (br_on_func $label$1 + (i31.new + (i32.const 1337) + ) + ) + ) + (ref.null nofunc) + ) + ) ) (module |