[threads] Shared basic heap types (#6667)

Implement binary and text parsing and printing of shared basic heap types and
incorporate them into the type hierarchy.

To avoid the massive amount of code duplication that would be necessary if we
were to add separate enum variants for each of the shared basic heap types, use
bit 0 to indicate whether the type is shared and replace `getBasic()` with
`getBasic(Unshared)`, which clears that bit. Update all the use sites to record
whether the original type was shared and produce shared or unshared output
without code duplication.

3 files changed, 138 insertions, 89 deletions

diff --git a/src/wasm/literal.cpp b/src/wasm/literal.cpp
index d4e1bfc45..f13ea504f 100644
--- a/src/wasm/literal.cpp
+++ b/src/wasm/literal.cpp
@@ -127,7 +127,7 @@ Literal::Literal(const Literal& other) : type(other.type) {
     assert(!type.isNullable());
     auto heapType = type.getHeapType();
     if (heapType.isBasic()) {
-      switch (heapType.getBasic()) {
+      switch (heapType.getBasic(Unshared)) {
         case HeapType::i31:
           i32 = other.i32;
           return;
@@ -620,8 +620,11 @@ std::ostream& operator<<(std::ostream& o, Literal literal) {
   } else {
     assert(literal.type.isRef());
     auto heapType = literal.type.getHeapType();
+    if (heapType.isShared()) {
+      o << "shared ";
+    }
     if (heapType.isBasic()) {
-      switch (heapType.getBasic()) {
+      switch (heapType.getBasic(Unshared)) {
         case HeapType::i31:
           o << "i31ref(" << literal.geti31() << ")";
           break;
@@ -2686,11 +2689,12 @@ Literal Literal::externalize() const {
     return Literal(std::shared_ptr<GCData>{}, HeapType::noext);
   }
   auto heapType = type.getHeapType();
+  auto extType = HeapTypes::ext.getBasic(heapType.getShared());
   if (heapType.isBasic()) {
-    switch (heapType.getBasic()) {
+    switch (heapType.getBasic(Unshared)) {
       case HeapType::i31: {
         return Literal(std::make_shared<GCData>(HeapType::i31, Literals{*this}),
-                       HeapType::ext);
+                       extType);
       }
       case HeapType::string:
         WASM_UNREACHABLE("TODO: string literals");
@@ -2698,7 +2702,7 @@ Literal Literal::externalize() const {
         WASM_UNREACHABLE("unexpected type");
     }
   }
-  return Literal(gcData, HeapType::ext);
+  return Literal(gcData, extType);
 }
 
 Literal Literal::internalize() const {
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index b05dd5237..524f4b98c 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1538,8 +1538,8 @@ void WasmBinaryWriter::writeType(Type type) {
       WASM_UNREACHABLE("bad type without GC");
     }
     auto heapType = type.getHeapType();
-    if (heapType.isBasic() && type.isNullable()) {
-      switch (heapType.getBasic()) {
+    if (type.isNullable() && heapType.isBasic() && !heapType.isShared()) {
+      switch (heapType.getBasic(Unshared)) {
         case HeapType::ext:
           o << S32LEB(BinaryConsts::EncodedType::externref);
           return;
@@ -1644,14 +1644,16 @@ void WasmBinaryWriter::writeHeapType(HeapType type) {
     }
   }
 
-  if (type.isSignature() || type.isContinuation() || type.isStruct() ||
-      type.isArray()) {
+  if (!type.isBasic()) {
     o << S64LEB(getTypeIndex(type)); // TODO: Actually s33
     return;
   }
+
   int ret = 0;
-  assert(type.isBasic());
-  switch (type.getBasic()) {
+  if (type.isShared()) {
+    o << S32LEB(BinaryConsts::EncodedType::Shared);
+  }
+  switch (type.getBasic(Unshared)) {
     case HeapType::ext:
       ret = BinaryConsts::EncodedHeapType::ext;
       break;
@@ -2083,7 +2085,7 @@ bool WasmBinaryReader::getBasicHeapType(int64_t code, HeapType& out) {
       out = HeapType::func;
       return true;
     case BinaryConsts::EncodedHeapType::cont:
-      out = HeapType::func;
+      out = HeapType::cont;
       return true;
     case BinaryConsts::EncodedHeapType::ext:
       out = HeapType::ext;
@@ -2168,9 +2170,14 @@ HeapType WasmBinaryReader::getHeapType() {
     }
     return types[type];
   }
+  auto share = Unshared;
+  if (type == BinaryConsts::EncodedType::Shared) {
+    share = Shared;
+    type = getS64LEB(); // TODO: Actually s33
+  }
   HeapType ht;
   if (getBasicHeapType(type, ht)) {
-    return ht;
+    return ht.getBasic(share);
   } else {
     throwError("invalid wasm heap type: " + std::to_string(type));
   }
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 532ebb913..ae6fd4b30 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -86,7 +86,7 @@ struct HeapTypeInfo {
   // global store.
   bool isTemp = false;
   bool isOpen = false;
-  bool isShared = false;
+  Shareability share = Unshared;
   // 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
@@ -436,18 +436,18 @@ bool isTemp(HeapType type) {
 
 HeapType::BasicHeapType getBasicHeapSupertype(HeapType type) {
   if (type.isBasic()) {
-    return type.getBasic();
+    return HeapType::BasicHeapType(type.getID());
   }
   auto* info = getHeapTypeInfo(type);
   switch (info->kind) {
     case HeapTypeInfo::SignatureKind:
-      return HeapType::func;
+      return HeapTypes::func.getBasic(info->share);
     case HeapTypeInfo::ContinuationKind:
-      return HeapType::cont;
+      return HeapTypes::cont.getBasic(info->share);
     case HeapTypeInfo::StructKind:
-      return HeapType::struct_;
+      return HeapTypes::struct_.getBasic(info->share);
     case HeapTypeInfo::ArrayKind:
-      return HeapType::array;
+      return HeapTypes::array.getBasic(info->share);
   }
   WASM_UNREACHABLE("unexpected kind");
 };
@@ -470,42 +470,53 @@ std::optional<HeapType> getBasicHeapTypeLUB(HeapType::BasicHeapType a,
   if (unsigned(a) > unsigned(b)) {
     std::swap(a, b);
   }
-  switch (a) {
+  auto bUnshared = HeapType(b).getBasic(Unshared);
+  HeapType lubUnshared;
+  switch (HeapType(a).getBasic(Unshared)) {
     case HeapType::ext:
     case HeapType::func:
     case HeapType::cont:
     case HeapType::exn:
       return std::nullopt;
     case HeapType::any:
-      return {HeapType::any};
+      lubUnshared = HeapType::any;
+      break;
     case HeapType::eq:
-      if (b == HeapType::i31 || b == HeapType::struct_ ||
-          b == HeapType::array) {
-        return {HeapType::eq};
+      if (bUnshared == HeapType::i31 || bUnshared == HeapType::struct_ ||
+          bUnshared == HeapType::array) {
+        lubUnshared = HeapType::eq;
+      } else {
+        lubUnshared = HeapType::any;
       }
-      return {HeapType::any};
+      break;
     case HeapType::i31:
-      if (b == HeapType::struct_ || b == HeapType::array) {
-        return {HeapType::eq};
+      if (bUnshared == HeapType::struct_ || bUnshared == HeapType::array) {
+        lubUnshared = HeapType::eq;
+      } else {
+        lubUnshared = HeapType::any;
       }
-      return {HeapType::any};
+      break;
     case HeapType::struct_:
-      if (b == HeapType::array) {
-        return {HeapType::eq};
+      if (bUnshared == HeapType::array) {
+        lubUnshared = HeapType::eq;
+      } else {
+        lubUnshared = HeapType::any;
       }
-      return {HeapType::any};
+      break;
     case HeapType::array:
     case HeapType::string:
-      return {HeapType::any};
+      lubUnshared = HeapType::any;
+      break;
     case HeapType::none:
     case HeapType::noext:
     case HeapType::nofunc:
     case HeapType::nocont:
     case HeapType::noexn:
       // Bottom types already handled.
-      break;
+      WASM_UNREACHABLE("unexpected basic type");
   }
-  WASM_UNREACHABLE("unexpected basic type");
+  auto share = HeapType(a).getShared();
+  return {lubUnshared.getBasic(share)};
 }
 
 TypeInfo::TypeInfo(const TypeInfo& other) {
@@ -898,7 +909,7 @@ FeatureSet Type::getFeatures() const {
 
         void noteChild(HeapType* heapType) {
           if (heapType->isBasic()) {
-            switch (heapType->getBasic()) {
+            switch (heapType->getBasic(Unshared)) {
               case HeapType::ext:
               case HeapType::func:
                 feats |= FeatureSet::ReferenceTypes;
@@ -1228,7 +1239,7 @@ bool HeapType::isString() const { return *this == HeapType::string; }
 
 bool HeapType::isBottom() const {
   if (isBasic()) {
-    switch (getBasic()) {
+    switch (getBasic(Unshared)) {
       case ext:
       case func:
       case cont:
@@ -1259,12 +1270,11 @@ bool HeapType::isOpen() const {
   }
 }
 
-bool HeapType::isShared() const {
+Shareability HeapType::getShared() const {
   if (isBasic()) {
-    // TODO: shared basic heap types
-    return false;
+    return (id & 1) != 0 ? Shared : Unshared;
   } else {
-    return getHeapTypeInfo(*this)->isShared;
+    return getHeapTypeInfo(*this)->share;
   }
 }
 
@@ -1305,9 +1315,11 @@ std::optional<HeapType> HeapType::getSuperType() const {
     return ret;
   }
 
+  auto share = getShared();
+
   // There may be a basic supertype.
   if (isBasic()) {
-    switch (getBasic()) {
+    switch (getBasic(Unshared)) {
       case ext:
       case noext:
       case func:
@@ -1321,24 +1333,24 @@ std::optional<HeapType> HeapType::getSuperType() const {
       case string:
         return {};
       case eq:
-        return any;
+        return HeapType(any).getBasic(share);
       case i31:
       case struct_:
       case array:
-        return eq;
+        return HeapType(eq).getBasic(share);
     }
   }
 
   auto* info = getHeapTypeInfo(*this);
   switch (info->kind) {
     case HeapTypeInfo::SignatureKind:
-      return func;
+      return HeapType(func).getBasic(share);
     case HeapTypeInfo::ContinuationKind:
-      return cont;
+      return HeapType(cont).getBasic(share);
     case HeapTypeInfo::StructKind:
-      return struct_;
+      return HeapType(struct_).getBasic(share);
     case HeapTypeInfo::ArrayKind:
-      return array;
+      return HeapType(array).getBasic(share);
   }
   WASM_UNREACHABLE("unexpected kind");
 }
@@ -1365,7 +1377,7 @@ size_t HeapType::getDepth() const {
     }
   } else {
     // Some basic types have supers.
-    switch (getBasic()) {
+    switch (getBasic(Unshared)) {
       case HeapType::ext:
       case HeapType::func:
       case HeapType::cont:
@@ -1393,9 +1405,9 @@ size_t HeapType::getDepth() const {
   return depth;
 }
 
-HeapType::BasicHeapType HeapType::getBottom() const {
+HeapType::BasicHeapType HeapType::getUnsharedBottom() const {
   if (isBasic()) {
-    switch (getBasic()) {
+    switch (getBasic(Unshared)) {
       case ext:
         return noext;
       case func:
@@ -1435,8 +1447,8 @@ HeapType::BasicHeapType HeapType::getBottom() const {
   WASM_UNREACHABLE("unexpected kind");
 }
 
-HeapType::BasicHeapType HeapType::getTop() const {
-  switch (getBottom()) {
+HeapType::BasicHeapType HeapType::getUnsharedTop() const {
+  switch (getUnsharedBottom()) {
     case none:
       return any;
     case nofunc:
@@ -1730,30 +1742,34 @@ bool SubTyper::isSubType(HeapType a, HeapType b) {
   if (a == b) {
     return true;
   }
+  if (a.isShared() != b.isShared()) {
+    return false;
+  }
   if (b.isBasic()) {
-    switch (b.getBasic()) {
+    auto aTop = a.getUnsharedTop();
+    auto aUnshared = a.isBasic() ? a.getBasic(Unshared) : a;
+    switch (b.getBasic(Unshared)) {
       case HeapType::ext:
-        return a.getTop() == HeapType::ext;
+        return aTop == HeapType::ext;
       case HeapType::func:
-        return a.getTop() == HeapType::func;
+        return aTop == HeapType::func;
       case HeapType::cont:
-        return a.getTop() == HeapType::cont;
+        return aTop == HeapType::cont;
       case HeapType::exn:
-        return a.getTop() == HeapType::exn;
+        return aTop == HeapType::exn;
       case HeapType::any:
-        return a.getTop() == HeapType::any;
+        return aTop == HeapType::any;
       case HeapType::eq:
-        return a == HeapType::i31 || a == HeapType::none ||
-               a == HeapType::struct_ || a == HeapType::array || a.isStruct() ||
-               a.isArray();
+        return aUnshared == HeapType::i31 || aUnshared == HeapType::none ||
+               aUnshared == HeapType::struct_ || aUnshared == HeapType::array ||
+               a.isStruct() || a.isArray();
       case HeapType::i31:
-        return a == HeapType::none;
+      case HeapType::string:
+        return aUnshared == HeapType::none;
       case HeapType::struct_:
-        return a == HeapType::none || a.isStruct();
+        return aUnshared == HeapType::none || a.isStruct();
       case HeapType::array:
-        return a == HeapType::none || a.isArray();
-      case HeapType::string:
-        return a == HeapType::none;
+        return aUnshared == HeapType::none || a.isArray();
       case HeapType::none:
       case HeapType::noext:
       case HeapType::nofunc:
@@ -1865,9 +1881,9 @@ std::ostream& TypePrinter::print(Type type) {
     print(type.getTuple());
   } else if (type.isRef()) {
     auto heapType = type.getHeapType();
-    if (heapType.isBasic() && type.isNullable()) {
+    if (type.isNullable() && heapType.isBasic() && !heapType.isShared()) {
       // Print shorthands for certain basic heap types.
-      switch (heapType.getBasic()) {
+      switch (heapType.getBasic(Unshared)) {
         case HeapType::ext:
           return os << "externref";
         case HeapType::func:
@@ -1914,38 +1930,60 @@ std::ostream& TypePrinter::print(Type type) {
 
 std::ostream& TypePrinter::print(HeapType type) {
   if (type.isBasic()) {
-    switch (type.getBasic()) {
+    if (type.isShared()) {
+      os << "(shared ";
+    }
+    switch (type.getBasic(Unshared)) {
       case HeapType::ext:
-        return os << "extern";
+        os << "extern";
+        break;
       case HeapType::func:
-        return os << "func";
+        os << "func";
+        break;
       case HeapType::cont:
-        return os << "cont";
+        os << "cont";
+        break;
       case HeapType::any:
-        return os << "any";
+        os << "any";
+        break;
       case HeapType::eq:
-        return os << "eq";
+        os << "eq";
+        break;
       case HeapType::i31:
-        return os << "i31";
+        os << "i31";
+        break;
       case HeapType::struct_:
-        return os << "struct";
+        os << "struct";
+        break;
       case HeapType::array:
-        return os << "array";
+        os << "array";
+        break;
       case HeapType::exn:
-        return os << "exn";
+        os << "exn";
+        break;
       case HeapType::string:
-        return os << "string";
+        os << "string";
+        break;
       case HeapType::none:
-        return os << "none";
+        os << "none";
+        break;
       case HeapType::noext:
-        return os << "noextern";
+        os << "noextern";
+        break;
       case HeapType::nofunc:
-        return os << "nofunc";
+        os << "nofunc";
+        break;
       case HeapType::nocont:
-        return os << "nocont";
+        os << "nocont";
+        break;
       case HeapType::noexn:
-        return os << "noexn";
+        os << "noexn";
+        break;
+    }
+    if (type.isShared()) {
+      os << ')';
     }
+    return os;
   }
 
   auto names = generator(type);
@@ -2144,7 +2182,7 @@ size_t RecGroupHasher::hash(const HeapTypeInfo& info) const {
     hash_combine(digest, hash(HeapType(uintptr_t(info.supertype))));
   }
   wasm::rehash(digest, info.isOpen);
-  wasm::rehash(digest, info.isShared);
+  wasm::rehash(digest, info.share);
   wasm::rehash(digest, info.kind);
   switch (info.kind) {
     case HeapTypeInfo::SignatureKind:
@@ -2281,7 +2319,7 @@ bool RecGroupEquator::eq(const HeapTypeInfo& a, const HeapTypeInfo& b) const {
   if (a.isOpen != b.isOpen) {
     return false;
   }
-  if (a.isShared != b.isShared) {
+  if (a.share != b.share) {
     return false;
   }
   if (a.kind != b.kind) {
@@ -2559,9 +2597,9 @@ void TypeBuilder::setOpen(size_t i, bool open) {
   impl->entries[i].info->isOpen = open;
 }
 
-void TypeBuilder::setShared(size_t i, bool shared) {
+void TypeBuilder::setShared(size_t i, Shareability share) {
   assert(i < size() && "index out of bounds");
-  impl->entries[i].info->isShared = shared;
+  impl->entries[i].info->share = share;
 }
 
 namespace {
@@ -2570,7 +2608,7 @@ bool isValidSupertype(const HeapTypeInfo& sub, const HeapTypeInfo& super) {
   if (!super.isOpen) {
     return false;
   }
-  if (sub.isShared != super.isShared) {
+  if (sub.share != super.share) {
     return false;
   }
   if (sub.kind != super.kind) {