From 097e63a43b7681677ef54819b75d3c2bc756acce Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Fri, 11 Nov 2022 16:19:49 -0800 Subject: [Wasm GC] Fix nondeterminism in GUFA due to ordering (#5243) We don't actually have the distributive property since our PossibleContents representation is an approximation, and the fuzzer found a case where that is noticeable. See more details in the new comment + testcase. I measured speed and memory usage and this actually causes almost no noticeable change. --- src/ir/possible-contents.cpp | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-) (limited to 'src/ir/possible-contents.cpp') 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 workQueue; -#else - std::unordered_set workQueue; -#endif // All existing links in the graph. We keep this to know when a link we want // to add is new or not. -- cgit v1.2.3