Initial support for `final` types (#5803)

Implement support in the type system for final types, which are not allowed to
have any subtypes. Final types are syntactically different from similar
non-final types, so type canonicalization is made aware of finality. Similarly,
TypeMerging and TypeSSA are updated to work correctly in the presence of final
types as well.

Implement binary and text parsing and emitting of final types. Use the standard
text format to represent final types and interpret the non-standard
"struct_subtype" and friends as non-final. This allows a graceful upgrade path
for users currently using the non-standard text format, where they can update
their code to use final types correctly at the point when they update to use the
standard format. Once users have migrated to using the fully expanded standard
text format, we can update update Binaryen's parsers to interpret the MVP
shorthands as final types to match the spec without breaking those users.

To make it safe for V8 to independently start interpreting types declared
without `sub` as final, also reserve that shorthand encoding only for types that
have no strict subtypes.

17 files changed, 356 insertions, 172 deletions

diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index aa042d86e..e11705812 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -70,6 +70,7 @@ void GlobalTypeRewriter::update() {
   // Create the temporary heap types.
   i = 0;
   for (auto [type, _] : typeIndices) {
+    typeBuilder[i].setFinal(type.isFinal());
     if (type.isSignature()) {
       auto sig = type.getSignature();
       TypeList newParams, newResults;
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 5d49ad900..67d0dbdcc 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -3017,13 +3017,20 @@ struct PrintSExpression : public UnifiedExpressionVisitor<PrintSExpression> {
     o << ')';
   }
   void handleHeapType(HeapType type) {
-    bool hasSuper = false;
-    // TODO: Consider finality once we support that.
-    if (auto super = type.getSuperType()) {
-      hasSuper = true;
+    auto super = type.getSuperType();
+    bool useSub = false;
+    // TODO: Once we parse MVP signature types as final, use the MVP shorthand
+    // for final types without supertypes.
+    if (super || type.isFinal()) {
+      useSub = true;
       o << "(sub ";
-      TypeNamePrinter(o, currModule).print(*super);
-      o << ' ';
+      if (type.isFinal()) {
+        o << "final ";
+      }
+      if (super) {
+        TypeNamePrinter(o, currModule).print(*super);
+        o << ' ';
+      }
     }
     if (type.isSignature()) {
       handleSignature(type);
@@ -3034,7 +3041,7 @@ struct PrintSExpression : public UnifiedExpressionVisitor<PrintSExpression> {
     } else {
       o << type;
     }
-    if (hasSuper) {
+    if (useSub) {
       o << ')';
     }
   }
diff --git a/src/passes/TypeMerging.cpp b/src/passes/TypeMerging.cpp
index 1897adc3c..fa36eb767 100644
--- a/src/passes/TypeMerging.cpp
+++ b/src/passes/TypeMerging.cpp
@@ -467,6 +467,9 @@ bool shapeEq(HeapType a, HeapType b) {
   // Check whether `a` and `b` have the same top-level structure, including the
   // position and identity of any children that are not included as transitions
   // in the DFA, i.e. any children that are not nontrivial references.
+  if (a.isFinal() != b.isFinal()) {
+    return false;
+  }
   if (a.isStruct() && b.isStruct()) {
     return shapeEq(a.getStruct(), b.getStruct());
   }
@@ -480,15 +483,15 @@ bool shapeEq(HeapType a, HeapType b) {
 }
 
 size_t shapeHash(HeapType a) {
-  size_t digest;
+  size_t digest = hash(a.isFinal());
   if (a.isStruct()) {
-    digest = hash(0);
+    rehash(digest, 0);
     hash_combine(digest, shapeHash(a.getStruct()));
   } else if (a.isArray()) {
-    digest = hash(1);
+    rehash(digest, 1);
     hash_combine(digest, shapeHash(a.getArray()));
   } else if (a.isSignature()) {
-    digest = hash(2);
+    rehash(digest, 2);
     hash_combine(digest, shapeHash(a.getSignature()));
   } else {
     WASM_UNREACHABLE("unexpected kind");
diff --git a/src/passes/TypeSSA.cpp b/src/passes/TypeSSA.cpp
index 33433083f..25575e70e 100644
--- a/src/passes/TypeSSA.cpp
+++ b/src/passes/TypeSSA.cpp
@@ -109,6 +109,7 @@ std::vector<HeapType> ensureTypesAreInNewRecGroup(RecGroup recGroup,
         if (auto super = type.getSuperType()) {
           builder[i].subTypeOf(*super);
         }
+        builder[i].setFinal(type.isFinal());
       }
 
       // Implement the hash as a struct with "random" fields, and add it.
@@ -306,6 +307,11 @@ struct TypeSSA : public Pass {
       return false;
     }
 
+    if (curr->type.getHeapType().isFinal()) {
+      // We can't create new subtypes of a final type anyway.
+      return false;
+    }
+
     // Look for at least one interesting operand. We will consider each operand
     // against the declared type, that is, the type declared for where it is
     // stored. If it has more information than the declared type then it is
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 26cc518be..2f77c5765 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -85,6 +85,13 @@ struct HeapTypeGeneratorImpl {
       }
     }
 
+    // Types without nontrivial subtypes may be marked final.
+    for (Index i = 0; i < builder.size(); ++i) {
+      if (subtypeIndices[i].size() == 1 && rand.oneIn(2)) {
+        builder[i].setFinal();
+      }
+    }
+
     // Initialize the recursion groups.
     recGroupEnds.reserve(builder.size());
     // Create isorecursive recursion groups. Choose an expected group size
@@ -878,7 +885,7 @@ std::vector<HeapType> Inhabitator::build() {
     start += size;
   }
 
-  // Establish supertypes.
+  // Establish supertypes and finality.
   for (size_t i = 0; i < types.size(); ++i) {
     if (auto super = types[i].getSuperType()) {
       if (auto it = typeIndices.find(*super); it != typeIndices.end()) {
@@ -887,6 +894,7 @@ std::vector<HeapType> Inhabitator::build() {
         builder[i].subTypeOf(*super);
       }
     }
+    builder[i].setFinal(types[i].isFinal());
   }
 
   auto built = builder.build();
diff --git a/src/tools/wasm-fuzz-types.cpp b/src/tools/wasm-fuzz-types.cpp
index 4f480ba9d..50f1e1e3c 100644
--- a/src/tools/wasm-fuzz-types.cpp
+++ b/src/tools/wasm-fuzz-types.cpp
@@ -262,6 +262,11 @@ void Fuzzer::checkCanonicalization() {
         }
       }
 
+      // Set finality
+      for (size_t i = 0; i < types.size(); ++i) {
+        builder[i].setFinal(types[i].isFinal());
+      }
+
       // Set up recursion groups and record group ends to ensure we only select
       // valid children.
       recGroupEnds.reserve(builder.size());
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 745358cbc..c6b3e7b6f 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -384,10 +384,11 @@ enum EncodedType {
   nullfuncref = -0x18,   // 0x68
   nullref = -0x1b,       // 0x65
   // type forms
-  Func = -0x20,   // 0x60
-  Struct = -0x21, // 0x5f
-  Array = -0x22,  // 0x5e
-  Sub = -0x30,    // 0x50
+  Func = -0x20,     // 0x60
+  Struct = -0x21,   // 0x5f
+  Array = -0x22,    // 0x5e
+  Sub = -0x30,      // 0x50
+  SubFinal = -0x32, // 0x4e
   // prototype nominal forms we still parse
   FuncSubtype = -0x23,   // 0x5d
   StructSubtype = -0x24, // 0x5c
diff --git a/src/wasm-type.h b/src/wasm-type.h
index a8a331ace..323ef0207 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -359,6 +359,7 @@ public:
   bool isArray() const;
   bool isString() const;
   bool isBottom() const;
+  bool isFinal() const;
 
   Signature getSignature() const;
   const Struct& getStruct() const;
@@ -584,6 +585,8 @@ struct TypeBuilder {
   // not overlap or go out of bounds.
   void createRecGroup(size_t i, size_t length);
 
+  void setFinal(size_t i, bool final = true);
+
   enum class ErrorReason {
     // There is a cycle in the supertype relation.
     SelfSupertype,
@@ -645,6 +648,10 @@ struct TypeBuilder {
       builder.setSubType(index, other);
       return *this;
     }
+    Entry& setFinal(bool final = true) {
+      builder.setFinal(index, final);
+      return *this;
+    }
   };
 
   Entry operator[](size_t i) { return Entry{*this, i}; }
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index d9b7e1a84..639f4b848 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -236,6 +236,19 @@ void WasmBinaryWriter::writeTypes() {
       lastGroup = currGroup;
     }
   }
+
+  // As a temporary measure, detect which types have subtypes and always use
+  // `sub` or `sub final` for these types. The standard says that types without
+  // `sub` or `sub final` are final, but we currently treat them as non-final.
+  // To avoid unsafe ambiguity, only use the short form for types that it would
+  // be safe to treat as final, i.e. types without subtypes.
+  std::vector<bool> hasSubtypes(indexedTypes.types.size());
+  for (auto type : indexedTypes.types) {
+    if (auto super = type.getSuperType()) {
+      hasSubtypes[indexedTypes.indices[*super]] = true;
+    }
+  }
+
   BYN_TRACE("== writeTypes\n");
   auto start = startSection(BinaryConsts::Section::Type);
   o << U32LEB(numGroups);
@@ -251,10 +264,21 @@ void WasmBinaryWriter::writeTypes() {
     lastGroup = currGroup;
     // Emit the type definition.
     BYN_TRACE("write " << type << std::endl);
-    if (auto super = type.getSuperType()) {
-      // Subtype constructor and vector of 1 supertype.
-      o << S32LEB(BinaryConsts::EncodedType::Sub) << U32LEB(1);
-      writeHeapType(*super);
+    auto super = type.getSuperType();
+    // TODO: Use the binary shorthand for final types once we parse MVP
+    // signatures as final.
+    if (type.isFinal() || super || hasSubtypes[i]) {
+      if (type.isFinal()) {
+        o << S32LEB(BinaryConsts::EncodedType::SubFinal);
+      } else {
+        o << S32LEB(BinaryConsts::EncodedType::Sub);
+      }
+      if (super) {
+        o << U32LEB(1);
+        writeHeapType(*super);
+      } else {
+        o << U32LEB(0);
+      }
     }
     if (type.isSignature()) {
       o << S32LEB(BinaryConsts::EncodedType::Func);
@@ -2210,7 +2234,12 @@ void WasmBinaryReader::readTypes() {
       form = getS32LEB();
     }
     std::optional<uint32_t> superIndex;
-    if (form == BinaryConsts::EncodedType::Sub) {
+    if (form == BinaryConsts::EncodedType::Sub ||
+        form == BinaryConsts::EncodedType::SubFinal) {
+      if (form == BinaryConsts::EncodedType::SubFinal) {
+        // TODO: Interpret type definitions without any `sub` as final as well.
+        builder[i].setFinal();
+      }
       uint32_t supers = getU32LEB();
       if (supers > 0) {
         if (supers != 1) {
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index e99200d58..9b7a1a90d 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -52,7 +52,8 @@ namespace wasm {
 static Name STRUCT("struct"), FIELD("field"), ARRAY("array"),
   FUNC_SUBTYPE("func_subtype"), STRUCT_SUBTYPE("struct_subtype"),
   ARRAY_SUBTYPE("array_subtype"), EXTENDS("extends"), REC("rec"), I8("i8"),
-  I16("i16"), DECLARE("declare"), ITEM("item"), OFFSET("offset"), SUB("sub");
+  I16("i16"), DECLARE("declare"), ITEM("item"), OFFSET("offset"), SUB("sub"),
+  FINAL("final");
 
 static Address getAddress(const Element* s) {
   return std::stoll(s->toString());
@@ -926,11 +927,19 @@ void SExpressionWasmBuilder::preParseHeapTypes(Element& module) {
     Element& kind = *def[0];
     Element* super = nullptr;
     if (kind == SUB) {
-      if (def.size() != 3) {
+      Index i = 1;
+      if (*def[i] == FINAL) {
+        builder[index].setFinal();
+        ++i;
+      }
+      if (def[i]->dollared()) {
+        super = def[i];
+        ++i;
+      }
+      Element& subtype = *def[i++];
+      if (i != def.size()) {
         throw ParseException("invalid 'sub' form", kind.line, kind.col);
       }
-      super = def[1];
-      Element& subtype = *def[2];
       if (!subtype.isList() || subtype.size() < 1) {
         throw ParseException(
           "invalid subtype definition", subtype.line, subtype.col);
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index aa08c52c2..6baf0feb0 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -85,6 +85,7 @@ struct HeapTypeInfo {
   // Used in assertions to ensure that temporary types don't leak into the
   // global store.
   bool isTemp = false;
+  bool isFinal = false;
   // The supertype of this HeapType, if it exists.
   HeapTypeInfo* supertype = nullptr;
   // The recursion group of this type or null if the recursion group is trivial
@@ -153,12 +154,9 @@ struct TypePrinter {
   std::ostream& print(HeapType type);
   std::ostream& print(const Tuple& tuple);
   std::ostream& print(const Field& field);
-  std::ostream& print(const Signature& sig,
-                      std::optional<HeapType> super = std::nullopt);
-  std::ostream& print(const Struct& struct_,
-                      std::optional<HeapType> super = std::nullopt);
-  std::ostream& print(const Array& array,
-                      std::optional<HeapType> super = std::nullopt);
+  std::ostream& print(const Signature& sig);
+  std::ostream& print(const Struct& struct_);
+  std::ostream& print(const Array& array);
 };
 
 struct RecGroupHasher {
@@ -1156,6 +1154,14 @@ bool HeapType::isBottom() const {
   return false;
 }
 
+bool HeapType::isFinal() const {
+  if (isBasic()) {
+    return false;
+  } else {
+    return getHeapTypeInfo(*this)->isFinal;
+  }
+}
+
 Signature HeapType::getSignature() const {
   assert(isSignature());
   return getHeapTypeInfo(*this)->signature;
@@ -1735,19 +1741,38 @@ std::ostream& TypePrinter::print(HeapType type) {
   if (isTemp(type)) {
     os << "(; temp ;) ";
   }
+
 #if TRACE_CANONICALIZATION
   os << "(;" << ((type.getID() >> 4) % 1000) << ";)";
 #endif
+
+  // TODO: Use shorthand for final types once we parse MVP signatures as final.
+  bool useSub = false;
+  auto super = type.getSuperType();
+  if (super || type.isFinal()) {
+    useSub = true;
+    os << "(sub ";
+    if (type.isFinal()) {
+      os << "final ";
+    }
+    if (super) {
+      printHeapTypeName(*super);
+      os << ' ';
+    }
+  }
   if (type.isSignature()) {
-    print(type.getSignature(), type.getSuperType());
+    print(type.getSignature());
   } else if (type.isStruct()) {
-    print(type.getStruct(), type.getSuperType());
+    print(type.getStruct());
   } else if (type.isArray()) {
-    print(type.getArray(), type.getSuperType());
+    print(type.getArray());
   } else {
     WASM_UNREACHABLE("unexpected type");
   }
-  return os << ")";
+  if (useSub) {
+    os << ')';
+  }
+  return os << ')';
 }
 
 std::ostream& TypePrinter::print(const Tuple& tuple) {
@@ -1783,8 +1808,7 @@ std::ostream& TypePrinter::print(const Field& field) {
   return os;
 }
 
-std::ostream& TypePrinter::print(const Signature& sig,
-                                 std::optional<HeapType> super) {
+std::ostream& TypePrinter::print(const Signature& sig) {
   auto printPrefixed = [&](const char* prefix, Type type) {
     os << '(' << prefix;
     for (Type t : type) {
@@ -1795,9 +1819,6 @@ std::ostream& TypePrinter::print(const Signature& sig,
   };
 
   os << "(func";
-  if (super) {
-    os << "_subtype";
-  }
   if (sig.params.getID() != Type::none) {
     os << ' ';
     printPrefixed("param", sig.params);
@@ -1806,19 +1827,11 @@ std::ostream& TypePrinter::print(const Signature& sig,
     os << ' ';
     printPrefixed("result", sig.results);
   }
-  if (super) {
-    os << ' ';
-    printHeapTypeName(*super);
-  }
   return os << ')';
 }
 
-std::ostream& TypePrinter::print(const Struct& struct_,
-                                 std::optional<HeapType> super) {
+std::ostream& TypePrinter::print(const Struct& struct_) {
   os << "(struct";
-  if (super) {
-    os << "_subtype";
-  }
   if (struct_.fields.size()) {
     os << " (field";
   }
@@ -1829,25 +1842,12 @@ std::ostream& TypePrinter::print(const Struct& struct_,
   if (struct_.fields.size()) {
     os << ')';
   }
-  if (super) {
-    os << ' ';
-    printHeapTypeName(*super);
-  }
   return os << ')';
 }
 
-std::ostream& TypePrinter::print(const Array& array,
-                                 std::optional<HeapType> super) {
-  os << "(array";
-  if (super) {
-    os << "_subtype";
-  }
-  os << ' ';
+std::ostream& TypePrinter::print(const Array& array) {
+  os << "(array ";
   print(array.element);
-  if (super) {
-    os << ' ';
-    printHeapTypeName(*super);
-  }
   return os << ')';
 }
 
@@ -1916,6 +1916,7 @@ size_t RecGroupHasher::hash(const HeapTypeInfo& info) const {
   if (info.supertype) {
     hash_combine(digest, hash(HeapType(uintptr_t(info.supertype))));
   }
+  wasm::rehash(digest, info.isFinal);
   wasm::rehash(digest, info.kind);
   switch (info.kind) {
     case HeapTypeInfo::SignatureKind:
@@ -2038,6 +2039,9 @@ bool RecGroupEquator::eq(const HeapTypeInfo& a, const HeapTypeInfo& b) const {
       return false;
     }
   }
+  if (a.isFinal != b.isFinal) {
+    return false;
+  }
   if (a.kind != b.kind) {
     return false;
   }
@@ -2291,9 +2295,17 @@ void TypeBuilder::createRecGroup(size_t index, size_t length) {
     {RecGroup(uintptr_t(groupInfo.get())), std::move(groupInfo)});
 }
 
+void TypeBuilder::setFinal(size_t i, bool final) {
+  assert(i < size() && "index out of bounds");
+  impl->entries[i].info->isFinal = final;
+}
+
 namespace {
 
 bool isValidSupertype(const HeapTypeInfo& sub, const HeapTypeInfo& super) {
+  if (super.isFinal) {
+    return false;
+  }
   if (sub.kind != super.kind) {
     return false;
   }
diff --git a/test/gtest/type-builder.cpp b/test/gtest/type-builder.cpp
index 0744e2b5e..1c30d9cb9 100644
--- a/test/gtest/type-builder.cpp
+++ b/test/gtest/type-builder.cpp
@@ -256,6 +256,22 @@ TEST_F(TypeTest, InvalidSupertype) {
   EXPECT_EQ(error->index, 1u);
 }
 
+TEST_F(TypeTest, InvalidFinalSupertype) {
+  TypeBuilder builder(2);
+  builder[0] = Struct{};
+  builder[1] = Struct{};
+  builder[0].setFinal();
+  builder[1].subTypeOf(builder[0]);
+
+  auto result = builder.build();
+  EXPECT_FALSE(result);
+
+  const auto* error = result.getError();
+  ASSERT_TRUE(error);
+  EXPECT_EQ(error->reason, TypeBuilder::ErrorReason::InvalidSupertype);
+  EXPECT_EQ(error->index, 1u);
+}
+
 TEST_F(TypeTest, ForwardReferencedChild) {
   TypeBuilder builder(3);
   builder.createRecGroup(0, 2);
@@ -434,6 +450,22 @@ TEST_F(TypeTest, CanonicalizeSupertypes) {
   EXPECT_NE(built[4], built[5]);
 }
 
+TEST_F(TypeTest, CanonicalizeFinal) {
+  // Types are different if their finality flag is different.
+  TypeBuilder builder(2);
+  builder[0] = Struct{};
+  builder[1] = Struct{};
+  builder[0].setFinal();
+
+  auto result = builder.build();
+  ASSERT_TRUE(result);
+  auto built = *result;
+
+  EXPECT_NE(built[0], built[1]);
+  EXPECT_TRUE(built[0].isFinal());
+  EXPECT_FALSE(built[1].isFinal());
+}
+
 TEST_F(TypeTest, HeapTypeConstructors) {
   HeapType sig(Signature(Type::i32, Type::i32));
   HeapType struct_(Struct({Field(Type(sig, Nullable), Mutable)}));
diff --git a/test/lit/fuzz-types.test b/test/lit/fuzz-types.test
index c1748e646..43a9947f2 100644
--- a/test/lit/fuzz-types.test
+++ b/test/lit/fuzz-types.test
@@ -1,66 +1,59 @@
-;; RUN: wasm-fuzz-types -v --seed=1 | filecheck %s
+;; RUN: wasm-fuzz-types -v --seed=0 | filecheck %s
 
-;; CHECK:      (rec
-;; CHECK-NEXT:  (type $0 (struct (field (mut (ref $1)) f64 v128 (mut (ref null $1)) (mut (ref null $0)) (ref $1))))
-;; CHECK-NEXT:  (type $1 (struct (field (mut v128) (mut (ref null $1)) (mut i8) (mut i16) (mut i16))))
-;; CHECK-NEXT: )
-;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $2 (array (mut i16)))
-;; CHECK-NEXT:  (type $3 (func))
-;; CHECK-NEXT: )
+;; CHECK:      Built 20 types:
 ;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $4 (func (param f32) (result f64)))
-;; CHECK-NEXT:  (type $5 (array v128))
-;; CHECK-NEXT:  (type $6 (array (mut (ref null $3))))
-;; CHECK-NEXT:  (type $7 (func (param v128) (result f32)))
-;; CHECK-NEXT:  (type $8 (struct_subtype (field (mut v128) (mut (ref null $1)) (mut i8) (mut i16) (mut i16) (mut i64)) $1))
+;; CHECK-NEXT:  (type $0 (struct (field i32)))
+;; CHECK-NEXT:  (type $1 (func (param (ref $2)) (result externref)))
+;; CHECK-NEXT:  (type $2 (struct))
 ;; CHECK-NEXT: )
-;; CHECK-NEXT: (type $9 (func_subtype (param v128) (result f32) $7))
-;; CHECK-NEXT: (type $10 (struct_subtype (field (mut (ref $1)) f64 v128 (mut (ref null $1)) (mut (ref null $0)) (ref $1)) $0))
 ;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $11 (struct))
-;; CHECK-NEXT:  (type $12 (struct (field (mut i32) (mut i32) v128)))
+;; CHECK-NEXT:  (type $3 (sub $0 (struct (field i32 (ref $5) (ref $5)))))
+;; CHECK-NEXT:  (type $4 (sub final $3 (struct (field i32 (ref $5) (ref $5) i8 (ref null $13) (mut i64)))))
+;; CHECK-NEXT:  (type $5 (array (mut f64)))
+;; CHECK-NEXT:  (type $6 (sub final $1 (func (param anyref) (result externref))))
+;; CHECK-NEXT:  (type $7 (sub $2 (struct (field (mut (ref null $14)) (ref $3)))))
+;; CHECK-NEXT:  (type $8 (sub $1 (func (param (ref struct)) (result (ref extern)))))
+;; CHECK-NEXT:  (type $9 (sub $5 (array (mut f64))))
+;; CHECK-NEXT:  (type $10 (sub $8 (func (param (ref any)) (result (ref noextern)))))
+;; CHECK-NEXT:  (type $11 (array (mut anyref)))
+;; CHECK-NEXT:  (type $12 (sub $2 (struct (field (mut f64)))))
+;; CHECK-NEXT:  (type $13 (sub $1 (func (param (ref $2)) (result (ref extern)))))
+;; CHECK-NEXT:  (type $14 (array (mut (ref null $14))))
 ;; CHECK-NEXT: )
 ;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $13 (func (param (ref null $4)) (result f32)))
-;; CHECK-NEXT:  (type $14 (array_subtype (mut i16) $2))
-;; CHECK-NEXT:  (type $15 (struct (field (mut v128) (ref extern) (mut (ref $15)))))
-;; CHECK-NEXT:  (type $16 (struct_subtype (field (mut v128) (ref extern) (mut (ref $15))) $15))
-;; CHECK-NEXT:  (type $17 (struct_subtype (field (mut (ref $1)) f64 v128 (mut (ref null $1)) (mut (ref null $0)) (ref $1)) $0))
-;; CHECK-NEXT:  (type $18 (func_subtype (param f32) (result f64) $4))
+;; CHECK-NEXT:  (type $15 (sub $11 (array (mut anyref))))
+;; CHECK-NEXT:  (type $16 (sub $12 (struct (field (mut f64)))))
+;; CHECK-NEXT:  (type $17 (sub final (struct (field f32 (mut i32) i8 (ref array)))))
+;; CHECK-NEXT:  (type $18 (sub final $11 (array (mut anyref))))
+;; CHECK-NEXT:  (type $19 (sub $9 (array (mut f64))))
 ;; CHECK-NEXT: )
-;; CHECK-NEXT: (type $19 (func (result v128)))
 ;; CHECK-NEXT:
 ;; CHECK-NEXT: Inhabitable types:
 ;; CHECK-NEXT:
 ;; CHECK-NEXT: Built 20 types:
 ;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $0 (struct (field (mut (ref $1)) f64 v128 (mut (ref null $1)) (mut (ref null $0)) (ref $1))))
-;; CHECK-NEXT:  (type $1 (struct (field (mut v128) (mut (ref null $1)) (mut i8) (mut i16) (mut i16))))
-;; CHECK-NEXT: )
-;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $2 (array (mut i16)))
-;; CHECK-NEXT:  (type $3 (func))
-;; CHECK-NEXT: )
-;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $4 (func (param f32) (result f64)))
-;; CHECK-NEXT:  (type $5 (array v128))
-;; CHECK-NEXT:  (type $6 (array (mut (ref null $3))))
-;; CHECK-NEXT:  (type $7 (func (param v128) (result f32)))
-;; CHECK-NEXT:  (type $8 (struct_subtype (field (mut v128) (mut (ref null $1)) (mut i8) (mut i16) (mut i16) (mut i64)) $1))
+;; CHECK-NEXT:  (type $0 (struct (field i32)))
+;; CHECK-NEXT:  (type $1 (func (param (ref $2)) (result externref)))
+;; CHECK-NEXT:  (type $2 (struct))
 ;; CHECK-NEXT: )
-;; CHECK-NEXT: (type $9 (func_subtype (param v128) (result f32) $7))
-;; CHECK-NEXT: (type $10 (struct_subtype (field (mut (ref $1)) f64 v128 (mut (ref null $1)) (mut (ref null $0)) (ref $1)) $0))
 ;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $11 (struct))
-;; CHECK-NEXT:  (type $12 (struct (field (mut i32) (mut i32) v128)))
+;; CHECK-NEXT:  (type $3 (sub $0 (struct (field i32 (ref $5) (ref $5)))))
+;; CHECK-NEXT:  (type $4 (sub final $3 (struct (field i32 (ref $5) (ref $5) i8 (ref null $13) (mut i64)))))
+;; CHECK-NEXT:  (type $5 (array (mut f64)))
+;; CHECK-NEXT:  (type $6 (sub final $1 (func (param anyref) (result externref))))
+;; CHECK-NEXT:  (type $7 (sub $2 (struct (field (mut (ref null $14)) (ref $3)))))
+;; CHECK-NEXT:  (type $8 (sub $1 (func (param (ref struct)) (result (ref extern)))))
+;; CHECK-NEXT:  (type $9 (sub $5 (array (mut f64))))
+;; CHECK-NEXT:  (type $10 (sub $8 (func (param (ref any)) (result (ref noextern)))))
+;; CHECK-NEXT:  (type $11 (array (mut anyref)))
+;; CHECK-NEXT:  (type $12 (sub $2 (struct (field (mut f64)))))
+;; CHECK-NEXT:  (type $13 (sub $1 (func (param (ref $2)) (result (ref extern)))))
+;; CHECK-NEXT:  (type $14 (array (mut (ref null $14))))
 ;; CHECK-NEXT: )
 ;; CHECK-NEXT: (rec
-;; CHECK-NEXT:  (type $13 (func (param (ref null $4)) (result f32)))
-;; CHECK-NEXT:  (type $14 (array_subtype (mut i16) $2))
-;; CHECK-NEXT:  (type $15 (struct (field (mut v128) externref (mut (ref null $15)))))
-;; CHECK-NEXT:  (type $16 (struct_subtype (field (mut v128) externref (mut (ref null $15))) $15))
-;; CHECK-NEXT:  (type $17 (struct_subtype (field (mut (ref $1)) f64 v128 (mut (ref null $1)) (mut (ref null $0)) (ref $1)) $0))
-;; CHECK-NEXT:  (type $18 (func_subtype (param f32) (result f64) $4))
+;; CHECK-NEXT:  (type $15 (sub $11 (array (mut anyref))))
+;; CHECK-NEXT:  (type $16 (sub $12 (struct (field (mut f64)))))
+;; CHECK-NEXT:  (type $17 (sub final (struct (field f32 (mut i32) i8 (ref array)))))
+;; CHECK-NEXT:  (type $18 (sub final $11 (array (mut anyref))))
+;; CHECK-NEXT:  (type $19 (sub $9 (array (mut f64))))
 ;; CHECK-NEXT: )
-;; CHECK-NEXT: (type $19 (func (result v128)))
diff --git a/test/lit/isorecursive-good.wast b/test/lit/isorecursive-good.wast
index 8e15d3190..1d5e9c7df 100644
--- a/test/lit/isorecursive-good.wast
+++ b/test/lit/isorecursive-good.wast
@@ -7,66 +7,82 @@
   (rec
     ;; CHECK:      (rec
     ;; CHECK-NEXT:  (type $super-struct (struct (field i32)))
-    (type $super-struct (struct i32))
+    (type $super-struct (sub (struct i32)))
     ;; CHECK:       (type $sub-struct (sub $super-struct (struct (field i32) (field i64))))
     (type $sub-struct (sub $super-struct (struct i32 i64)))
+    ;; CHECK:       (type $final-struct (sub final $sub-struct (struct (field i32) (field i64) (field f32))))
+    (type $final-struct (sub final $sub-struct (struct i32 i64 f32)))
   )
 
   (rec
     ;; CHECK:      (rec
     ;; CHECK-NEXT:  (type $super-array (array (ref $super-struct)))
-    (type $super-array (array (ref $super-struct)))
+    (type $super-array (sub (array (ref $super-struct))))
     ;; CHECK:       (type $sub-array (sub $super-array (array (ref $sub-struct))))
     (type $sub-array (sub $super-array (array (ref $sub-struct))))
+    ;; CHECK:       (type $final-array (sub final $sub-array (array (ref $final-struct))))
+    (type $final-array (sub final $sub-array (array (ref $final-struct))))
   )
 
   (rec
     ;; CHECK:      (rec
     ;; CHECK-NEXT:  (type $super-func (func (param (ref $sub-array)) (result (ref $super-array))))
-    (type $super-func (func (param (ref $sub-array)) (result (ref $super-array))))
+    (type $super-func (sub (func (param (ref $sub-array)) (result (ref $super-array)))))
     ;; CHECK:       (type $sub-func (sub $super-func (func (param (ref $super-array)) (result (ref $sub-array)))))
     (type $sub-func (sub $super-func (func (param (ref $super-array)) (result (ref $sub-array)))))
+    ;; CHECK:       (type $final-func (sub final $sub-func (func (param (ref $super-array)) (result (ref $final-array)))))
+    (type $final-func (sub final $sub-func (func (param (ref $super-array)) (result (ref $final-array)))))
   )
 
+  ;; CHECK:      (type $final-root (sub final (struct )))
+  (type $final-root (sub final (struct)))
+
   ;; CHECK:      (func $make-super-struct (type $none_=>_ref|$super-struct|) (result (ref $super-struct))
-  ;; CHECK-NEXT:  (call $make-sub-struct)
+  ;; CHECK-NEXT:  (call $make-final-struct)
   ;; CHECK-NEXT: )
   (func $make-super-struct (result (ref $super-struct))
-    (call $make-sub-struct)
+    (call $make-final-struct)
   )
 
-  ;; CHECK:      (func $make-sub-struct (type $none_=>_ref|$sub-struct|) (result (ref $sub-struct))
+  ;; CHECK:      (func $make-final-struct (type $none_=>_ref|$final-struct|) (result (ref $final-struct))
   ;; CHECK-NEXT:  (unreachable)
   ;; CHECK-NEXT: )
-  (func $make-sub-struct (result (ref $sub-struct))
+  (func $make-final-struct (result (ref $final-struct))
     (unreachable)
   )
 
   ;; CHECK:      (func $make-super-array (type $none_=>_ref|$super-array|) (result (ref $super-array))
-  ;; CHECK-NEXT:  (call $make-sub-array)
+  ;; CHECK-NEXT:  (call $make-final-array)
   ;; CHECK-NEXT: )
   (func $make-super-array (result (ref $super-array))
-    (call $make-sub-array)
+    (call $make-final-array)
   )
 
-  ;; CHECK:      (func $make-sub-array (type $none_=>_ref|$sub-array|) (result (ref $sub-array))
+  ;; CHECK:      (func $make-final-array (type $none_=>_ref|$final-array|) (result (ref $final-array))
   ;; CHECK-NEXT:  (unreachable)
   ;; CHECK-NEXT: )
-  (func $make-sub-array (result (ref $sub-array))
+  (func $make-final-array (result (ref $final-array))
     (unreachable)
   )
 
   ;; CHECK:      (func $make-super-func (type $none_=>_ref|$super-func|) (result (ref $super-func))
-  ;; CHECK-NEXT:  (call $make-sub-func)
+  ;; CHECK-NEXT:  (call $make-final-func)
   ;; CHECK-NEXT: )
   (func $make-super-func (result (ref $super-func))
-    (call $make-sub-func)
+    (call $make-final-func)
+  )
+
+  ;; CHECK:      (func $make-final-func (type $none_=>_ref|$final-func|) (result (ref $final-func))
+  ;; CHECK-NEXT:  (unreachable)
+  ;; CHECK-NEXT: )
+  (func $make-final-func (result (ref $final-func))
+    (unreachable)
   )
 
-  ;; CHECK:      (func $make-sub-func (type $none_=>_ref|$sub-func|) (result (ref $sub-func))
+  ;; CHECK:      (func $make-final-root (type $none_=>_ref|$final-root|) (result (ref $final-root))
   ;; CHECK-NEXT:  (unreachable)
   ;; CHECK-NEXT: )
-  (func $make-sub-func (result (ref $sub-func))
+  (func $make-final-root (result (ref $final-root))
     (unreachable)
   )
 )
diff --git a/test/lit/passes/type-merging.wast b/test/lit/passes/type-merging.wast
index 639810886..37d5337ac 100644
--- a/test/lit/passes/type-merging.wast
+++ b/test/lit/passes/type-merging.wast
@@ -7,6 +7,8 @@
     ;; CHECK-NEXT:  (type $A (struct (field anyref)))
     (type $A (struct_subtype (field anyref) data))
     (type $B (struct_subtype (field anyref) $A))
+    ;; CHECK:       (type $G (sub final $A (struct (field anyref))))
+
     ;; CHECK:       (type $F (sub $A (struct (field anyref))))
 
     ;; CHECK:       (type $E (sub $A (struct (field eqref))))
@@ -18,6 +20,7 @@
     (type $D (struct_subtype (field (ref any)) $A))
     (type $E (struct_subtype (field eqref) $A))
     (type $F (struct_subtype (field anyref) $A))
+    (type $G (sub final $A (struct (field anyref))))
   )
 
   ;; CHECK:       (type $none_=>_none (func))
@@ -29,6 +32,7 @@
   ;; CHECK-NEXT:  (local $d (ref null $D))
   ;; CHECK-NEXT:  (local $e (ref null $E))
   ;; CHECK-NEXT:  (local $f (ref null $F))
+  ;; CHECK-NEXT:  (local $g (ref null $G))
   ;; CHECK-NEXT:  (drop
   ;; CHECK-NEXT:   (ref.cast null $A
   ;; CHECK-NEXT:    (local.get $a)
@@ -53,6 +57,8 @@
     (local $e (ref null $E))
     ;; $F cannot because it has a cast.
     (local $f (ref null $F))
+    ;; $G cannot because it changes finality.
+    (local $g (ref null $G))
 
     ;; A cast of $A has no effect.
     (drop
diff --git a/test/lit/passes/type-ssa.wast b/test/lit/passes/type-ssa.wast
index 1ed55ff7d..6980cb46e 100644
--- a/test/lit/passes/type-ssa.wast
+++ b/test/lit/passes/type-ssa.wast
@@ -74,6 +74,65 @@
   )
 )
 
+;; The same module as before, except that now the type is final, so we cannot
+;; create any subtypes.
+(module
+  ;; CHECK:      (type $struct (sub final (struct (field i32))))
+  (type $struct (sub final (struct (field i32))))
+
+  ;; CHECK:      (type $none_=>_none (func))
+
+  ;; CHECK:      (global $g (ref $struct) (struct.new $struct
+  ;; CHECK-NEXT:  (i32.const 42)
+  ;; CHECK-NEXT: ))
+  (global $g (ref $struct) (struct.new $struct
+    (i32.const 42)
+  ))
+
+  ;; CHECK:      (global $h (ref $struct) (struct.new $struct
+  ;; CHECK-NEXT:  (i32.const 42)
+  ;; CHECK-NEXT: ))
+  (global $h (ref $struct) (struct.new $struct
+    (i32.const 42)
+  ))
+
+  ;; CHECK:      (func $foo (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (struct.new_default $struct)
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (struct.new $struct
+  ;; CHECK-NEXT:    (i32.const 10)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $foo
+    (drop
+      (struct.new_default $struct)
+    )
+    (drop
+      (struct.new $struct
+        (i32.const 10)
+      )
+    )
+  )
+
+  ;; CHECK:      (func $another-func (type $none_=>_none)
+  ;; CHECK-NEXT:  (drop
+  ;; CHECK-NEXT:   (struct.new $struct
+  ;; CHECK-NEXT:    (i32.const 100)
+  ;; CHECK-NEXT:   )
+  ;; CHECK-NEXT:  )
+  ;; CHECK-NEXT: )
+  (func $another-func
+    (drop
+      (struct.new $struct
+        (i32.const 100)
+      )
+    )
+  )
+)
+
 ;; Some of these are uninteresting and should not get a new type.
 (module
 
diff --git a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
index b5efc4c85..11da6a35b 100644
--- a/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
+++ b/test/passes/translate-to-fuzz_all-features_metrics_noprint.txt
@@ -1,50 +1,40 @@
 total
- [exports]      : 9       
- [funcs]        : 16      
- [globals]      : 16      
+ [exports]      : 3       
+ [funcs]        : 6       
+ [globals]      : 1       
  [imports]      : 5       
  [memories]     : 1       
  [memory-data]  : 20      
- [table-data]   : 2       
+ [table-data]   : 0       
  [tables]       : 1       
- [tags]         : 1       
- [total]        : 666     
- [vars]         : 32      
- ArrayFill      : 1       
- ArrayLen       : 1       
- ArrayNew       : 7       
- ArrayNewFixed  : 3       
- AtomicCmpxchg  : 1       
- AtomicFence    : 2       
- AtomicNotify   : 1       
- Binary         : 81      
- Block          : 84      
- Break          : 8       
- Call           : 23      
- Const          : 152     
- Drop           : 6       
- GlobalGet      : 40      
- GlobalSet      : 38      
- I31Get         : 1       
- I31New         : 3       
- If             : 29      
- Load           : 19      
- LocalGet       : 39      
- LocalSet       : 20      
- Loop           : 5       
- Nop            : 9       
- RefAs          : 5       
- RefEq          : 2       
- RefFunc        : 6       
- RefIsNull      : 2       
- RefNull        : 9       
+ [tags]         : 2       
+ [total]        : 463     
+ [vars]         : 19      
+ ArrayCopy      : 1       
+ ArrayLen       : 6       
+ ArrayNew       : 8       
+ ArraySet       : 1       
+ AtomicFence    : 1       
+ Binary         : 79      
+ Block          : 49      
+ Break          : 5       
+ Call           : 7       
+ CallRef        : 2       
+ Const          : 96      
+ Drop           : 2       
+ GlobalGet      : 20      
+ GlobalSet      : 20      
+ If             : 17      
+ Load           : 18      
+ LocalGet       : 44      
+ LocalSet       : 34      
+ Loop           : 6       
+ Nop            : 6       
+ RefAs          : 3       
+ RefFunc        : 2       
+ RefNull        : 3       
  Return         : 4       
- Select         : 1       
- Store          : 4       
- StructGet      : 1       
- StructNew      : 10      
- Try            : 2       
- TupleExtract   : 1       
- TupleMake      : 3       
- Unary          : 23      
- Unreachable    : 20      
+ Store          : 2       
+ StructNew      : 1       
+ Unary          : 14      
+ Unreachable    : 12