SubtypingDiscoverer: Differentiate non-flow subtyping constraints (#6344)

When we do a local.set of a value into a local then we have both a subtyping constraint - for
the value to be valid to put in that local - and also a flow of a value, which can then reach
more places. Such flow then interacts with casts in Unsubtyping, since it needs to know
what can flow where in order to know how casts force us to keep subtyping relations.

That regressed in the not-actually-NFC #6323 in which I added the innocuous lines
to add subtyping constraints in ref.eq. It seems fine to require that the arms of a
RefEq must be of type eqref, but Unsubtyping then assuming those arms flowed into
a location of type eqref... which means casts might force us to not optimize some
things.

To fix this, differentiate the rare case of non-flowing subtyping constraints, which is
basically only RefEq. There are perhaps a few more cases (like i31 operations) but they
do not matter in practice for Unsubtyping anyhow; I suggest we land this first to undo
the regression and then at our leisure investigate the other instructions.

4 files changed, 141 insertions, 2 deletions

diff --git a/src/ir/subtype-exprs.h b/src/ir/subtype-exprs.h
index 6b8348319..1c922521f 100644
--- a/src/ir/subtype-exprs.h
+++ b/src/ir/subtype-exprs.h
@@ -59,6 +59,21 @@ namespace wasm {
 //  * noteCast(Expression, Expression) - An expression's type is cast to
 //                                       another, for example, in RefCast.
 //
+// In addition, we need to differentiate two situations that cause subtyping:
+//  * Flow-based subtyping: E.g. when a value flows out from a block, in which
+//    case the value must be a subtype of the block's type.
+//  * Non-flow-based subtyping: E.g. in RefEq, being in one of the arms means
+//    you must be a subtype of eqref, but your value does not flow anywhere,
+//    because it is processed by the RefEq and does not send it anywhere.
+// The difference between the two matters in some users of this class, and so
+// the above functions all handle flow-based subtyping, while there is also the
+// following:
+//
+//  * noteNonFlowSubtype(Expression, Type)
+//
+// This is the only signature we need for the non-flowing case since it always
+// stems from an expression that is compared against a type.
+//
 // The concrete signatures are:
 //
 //      void noteSubtype(Type, Type);
@@ -66,6 +81,7 @@ namespace wasm {
 //      void noteSubtype(Type, Expression*);
 //      void noteSubtype(Expression*, Type);
 //      void noteSubtype(Expression*, Expression*);
+//      void noteNonFlowSubtype(Expression*, Type);
 //      void noteCast(HeapType, HeapType);
 //      void noteCast(Expression*, Type);
 //      void noteCast(Expression*, Expression*);
@@ -202,8 +218,8 @@ struct SubtypingDiscoverer : public OverriddenVisitor<SubType> {
   void visitRefIsNull(RefIsNull* curr) {}
   void visitRefFunc(RefFunc* curr) {}
   void visitRefEq(RefEq* curr) {
-    self()->noteSubtype(curr->left, Type(HeapType::eq, Nullable));
-    self()->noteSubtype(curr->right, Type(HeapType::eq, Nullable));
+    self()->noteNonFlowSubtype(curr->left, Type(HeapType::eq, Nullable));
+    self()->noteNonFlowSubtype(curr->right, Type(HeapType::eq, Nullable));
   }
   void visitTableGet(TableGet* curr) {}
   void visitTableSet(TableSet* curr) {
diff --git a/src/passes/StringLowering.cpp b/src/passes/StringLowering.cpp
index 1e16295cd..e0d3fbad0 100644
--- a/src/passes/StringLowering.cpp
+++ b/src/passes/StringLowering.cpp
@@ -478,6 +478,10 @@ struct StringLowering : public StringGathering {
         // Only the type matters of the place we assign to.
         noteSubtype(a, b->type);
       }
+      void noteNonFlowSubtype(Expression* a, Type b) {
+        // Flow or non-flow is the same for us.
+        noteSubtype(a, b);
+      }
       void noteCast(HeapType, HeapType) {
         // Casts do not concern us.
       }
diff --git a/src/passes/Unsubtyping.cpp b/src/passes/Unsubtyping.cpp
index 67a3c4e85..897511c35 100644
--- a/src/passes/Unsubtyping.cpp
+++ b/src/passes/Unsubtyping.cpp
@@ -193,6 +193,22 @@ struct Unsubtyping
     noteSubtype(sub->type, super->type);
   }
 
+  void noteNonFlowSubtype(Expression* sub, Type super) {
+    // This expression's type must be a subtype of |super|, but the value does
+    // not flow anywhere - this is a static constraint. As the value does not
+    // flow, it cannot reach anywhere else, which means we need this in order to
+    // validate but it does not interact with casts. Given that, if super is a
+    // basic type then we can simply ignore this: we only remove subtyping
+    // between user types, so subtyping wrt basic types is unchanged, and so
+    // this constraint will never be a problem.
+    if (super.isRef() && super.getHeapType().isBasic()) {
+      return;
+    }
+
+    // Otherwise, we must take this into account.
+    noteSubtype(sub, super);
+  }
+
   void noteCast(HeapType src, HeapType dest) {
     if (src == dest || dest.isBottom()) {
       return;
diff --git a/test/lit/passes/unsubtyping-casts.wast b/test/lit/passes/unsubtyping-casts.wast
index c1993e8b4..8f0f66ef2 100644
--- a/test/lit/passes/unsubtyping-casts.wast
+++ b/test/lit/passes/unsubtyping-casts.wast
@@ -372,6 +372,109 @@
  )
 )
 
+;; As above, but now with some ref.eq added. Those should not inhibit
+;; optimizations: as before, $bot no longer needs to subtype from $mid (but
+;; $mid must subtype from $top). ref.eq does add a requirement on subtyping
+;; (that the type be a subtype of eq), but ref.eq does not actually flow the
+;; inputs it receives anywhere, so that doesn't stop us from removing subtyping
+;; from user types.
+(module
+ (rec
+  ;; CHECK:      (rec
+  ;; CHECK-NEXT:  (type $top (sub (struct )))
+  (type $top (sub (struct)))
+  ;; CHECK:       (type $mid (sub $top (struct )))
+  (type $mid (sub $top (struct)))
+  ;; CHECK:       (type $bot (sub (struct )))
+  (type $bot (sub $mid (struct)))
+ )
+
+ ;; CHECK:       (type $3 (func (param anyref (ref $top) (ref $mid) (ref $bot))))
+
+ ;; CHECK:      (func $cast (type $3) (param $any anyref) (param $top (ref $top)) (param $mid (ref $mid)) (param $bot (ref $bot))
+ ;; CHECK-NEXT:  (local $l anyref)
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $top)
+ ;; CHECK-NEXT:    (local.get $mid)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $top)
+ ;; CHECK-NEXT:    (local.get $bot)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (ref.eq
+ ;; CHECK-NEXT:    (local.get $mid)
+ ;; CHECK-NEXT:    (local.get $bot)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (ref.cast (ref $bot)
+ ;; CHECK-NEXT:    (local.get $any)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (ref.cast (ref $top)
+ ;; CHECK-NEXT:    (local.get $any)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (drop
+ ;; CHECK-NEXT:   (ref.cast (ref $mid)
+ ;; CHECK-NEXT:    (local.get $any)
+ ;; CHECK-NEXT:   )
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT:  (local.set $l
+ ;; CHECK-NEXT:   (struct.new_default $mid)
+ ;; CHECK-NEXT:  )
+ ;; CHECK-NEXT: )
+ (func $cast (param $any anyref) (param $top (ref $top)) (param $mid (ref $mid)) (param $bot (ref $bot))
+  (local $l anyref)
+  (drop
+   (ref.eq
+    (local.get $top)
+    (local.get $mid)
+   )
+  )
+  (drop
+   (ref.eq
+    (local.get $top)
+    (local.get $bot)
+   )
+  )
+  (drop
+   (ref.eq
+    (local.get $mid)
+    (local.get $bot)
+   )
+  )
+  (drop
+   ;; Cast any -> $bot
+   (ref.cast (ref $bot)
+    (local.get $any)
+   )
+  )
+  (drop
+   ;; Cast any -> $top
+   (ref.cast (ref $top)
+    (local.get $any)
+   )
+  )
+  (drop
+   ;; Cast any -> $mid
+   (ref.cast (ref $mid)
+    (local.get $any)
+   )
+  )
+
+  (local.set $l
+   (struct.new $mid)
+  )
+ )
+)
+
 (module
  (rec
   ;; CHECK:      (rec