4 files changed, 88 insertions, 17 deletions
diff --git a/src/ir/CMakeLists.txt b/src/ir/CMakeLists.txt
index f98f7b7aa..c17a48ac0 100644
--- a/src/ir/CMakeLists.txt
+++ b/src/ir/CMakeLists.txt
@@ -3,6 +3,7 @@ set(ir_SOURCES
   ExpressionAnalyzer.cpp
   ExpressionManipulator.cpp
   names.cpp
+  properties.cpp
   LocalGraph.cpp
   ReFinalize.cpp
   stack-utils.cpp
diff --git a/src/ir/hashed.h b/src/ir/hashed.h
index 4a6e1647e..99488dcfb 100644
--- a/src/ir/hashed.h
+++ b/src/ir/hashed.h
@@ -23,23 +23,6 @@
 
 namespace wasm {
 
-// An expression with a cached hash value
-struct HashedExpression {
-  Expression* expr;
-  size_t digest;
-
-  HashedExpression(Expression* expr) : expr(expr) {
-    if (expr) {
-      digest = ExpressionAnalyzer::hash(expr);
-    } else {
-      digest = hash(0);
-    }
-  }
-
-  HashedExpression(const HashedExpression& other)
-    : expr(other.expr), digest(other.digest) {}
-};
-
 // A pass that hashes all functions
 
 struct FunctionHasher : public WalkerPass<PostWalker<FunctionHasher>> {
diff --git a/src/ir/properties.cpp b/src/ir/properties.cpp
new file mode 100644
index 000000000..889ece57b
--- /dev/null
+++ b/src/ir/properties.cpp
@@ -0,0 +1,42 @@
+/*
+ * Copyright 2021 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "ir/properties.h"
+#include "wasm-traversal.h"
+
+namespace wasm {
+
+namespace Properties {
+
+bool isIntrinsicallyNondeterministic(Expression* curr, FeatureSet features) {
+  // Practically no wasm instructions are intrinsically nondeterministic.
+  // Exceptions occur only in GC atm.
+  if (!features.hasGC()) {
+    return false;
+  }
+
+  struct Scanner : public PostWalker<Scanner> {
+    bool deterministic = true;
+    void visitStructNew(StructNew* curr) { deterministic = false; }
+    void visitArrayNew(ArrayNew* curr) { deterministic = false; }
+  } scanner;
+  scanner.walk(curr);
+  return !scanner.deterministic;
+}
+
+} // namespace Properties
+
+} // namespace wasm
diff --git a/src/ir/properties.h b/src/ir/properties.h
index d477cb11c..4909dfbc8 100644
--- a/src/ir/properties.h
+++ b/src/ir/properties.h
@@ -335,6 +335,51 @@ inline bool canEmitSelectWithArms(Expression* ifTrue, Expression* ifFalse) {
   return ifTrue->type.isSingle() && ifFalse->type.isSingle();
 }
 
+// An intrinsically-nondeterministic expression is one that can return different
+// results for the same inputs, and that difference is *not* explained by
+// other expressions that interact with this one. Hence the cause of
+// nondeterminism can be said to be "intrinsic" - it is internal and inherent in
+// the expression.
+//
+// To see the issue more concretely, consider these:
+//
+//    x = load(100);
+//    ..
+//    y = load(100);
+//
+//  versus
+//
+//    x = struct.new();
+//    ..
+//    y = struct.new();
+//
+// Are x and y identical in both cases? For loads, we can look at the code
+// in ".." to see: if there are no possible stores to memory, then the
+// result is identical (and we have EffectAnalyzer for that). For the GC
+// allocations, though, it doesn't matter what is in "..": there is nothing
+// in the wasm that we can check to find out if the results are the same or
+// not. (In fact, in this case they are always not the same.) So the
+// nondeterminism is "intrinsic."
+//
+// Thus, loads are nondeterministic but not intrinsically so, while GC
+// allocations are actual examples of intrinsically nondeterministic
+// instructions. If wasm were to add "get current time" or "get a random number"
+// instructions then those would also be intrinsically nondeterministic.
+//
+//  * Note that NaN nondeterminism is ignored here. Technically that allows e.g.
+//    an f32.add to be nondeterministic, but it is a valid wasm implementation
+//    to have deterministic NaN behavior, and we optimize under that assumption.
+//    So NaN nondeterminism does not cause anything to be intrinsically
+//    nondeterministic.
+//  * Note that calls are ignored here. In theory this concept could be defined
+//    either way for them (that is, we could potentially define them as either
+//    intrinsically nondeterministic, or not, and each could make sense in its
+//    own way). It is simpler to ignore them here, which means we only consider
+//    the behavior of the expression provided here (including its chldren), and
+//    not external code.
+//
+bool isIntrinsicallyNondeterministic(Expression* curr, FeatureSet features);
+
 } // namespace Properties
 
 } // namespace wasm