[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.

13 files changed, 322 insertions, 209 deletions

diff --git a/src/analysis/lattices/shared.h b/src/analysis/lattices/shared.h
index 54acf92b4..f345014b9 100644
--- a/src/analysis/lattices/shared.h
+++ b/src/analysis/lattices/shared.h
@@ -27,10 +27,10 @@ namespace wasm::analysis {
 
 // A lattice whose elements are a single ascending chain in lattice `L`.
 // Internally, there is only ever a single monotonically increasing element of L
-// materialized. Dereferencing any element of the Shared lattice will produce
-// the current value of that single element of L, which is generally safe
-// because the current value always overapproximates (i.e. is higher in the
-// lattice than) the value at the time of the Shared element's construction.
+// materialized. Dereferencing any element of the SharedPath lattice will
+// produce the current value of that single element of L, which is generally
+// safe because the current value always overapproximates (i.e. is higher in the
+// lattice than) the value at the time of the SharedPath element's construction.
 //
 // Each element of this lattice maintains a sequence number that corresponds to
 // a value the shared underlying element has had at some point in time. Higher
@@ -38,7 +38,7 @@ namespace wasm::analysis {
 // Elements of this lattice are compared and joined using these sequence
 // numbers, so blocks will correctly be re-analyzed if the value has increased
 // since the last time they were analyzed.
-template<Lattice L> struct Shared {
+template<Lattice L> struct SharedPath {
   // If we ever have extremely long-running analyses, this may need to be
   // changed to uint64_t.
   using Seq = uint32_t;
@@ -70,7 +70,7 @@ template<Lattice L> struct Shared {
       return !(*this == other);
     }
 
-    friend Shared;
+    friend SharedPath;
   };
 
   L lattice;
@@ -84,7 +84,7 @@ template<Lattice L> struct Shared {
   mutable typename L::Element val;
   mutable Seq seq = 0;
 
-  Shared(L&& l) : lattice(std::move(l)), val(lattice.getBottom()) {}
+  SharedPath(L&& l) : lattice(std::move(l)), val(lattice.getBottom()) {}
 
   // TODO: Delete the move constructor and the move assignment operator. This
   // requires fixing the lattice fuzzer first, since it depends on lattices
@@ -119,10 +119,10 @@ template<Lattice L> struct Shared {
 };
 
 // Deduction guide.
-template<typename L> Shared(L&&) -> Shared<L>;
+template<typename L> SharedPath(L&&) -> SharedPath<L>;
 
 #if __cplusplus >= 202002L
-static_assert(Lattice<Shared<Bool>>);
+static_assert(Lattice<SharedPath<Bool>>);
 #endif // __cplusplus >= 202002L
 
 } // namespace wasm::analysis
diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp
index 4e7fb0b61..841fa61ee 100644
--- a/src/binaryen-c.cpp
+++ b/src/binaryen-c.cpp
@@ -78,7 +78,7 @@ BinaryenLiteral toBinaryenLiteral(Literal x) {
   assert(x.type.isRef());
   auto heapType = x.type.getHeapType();
   if (heapType.isBasic()) {
-    switch (heapType.getBasic()) {
+    switch (heapType.getBasic(Unshared)) {
       case HeapType::i31:
         WASM_UNREACHABLE("TODO: i31");
       case HeapType::ext:
@@ -132,7 +132,7 @@ Literal fromBinaryenLiteral(BinaryenLiteral x) {
   assert(type.isRef());
   auto heapType = type.getHeapType();
   if (heapType.isBasic()) {
-    switch (heapType.getBasic()) {
+    switch (heapType.getBasic(Unshared)) {
       case HeapType::i31:
         WASM_UNREACHABLE("TODO: i31");
       case HeapType::ext:
diff --git a/src/ir/type-updating.cpp b/src/ir/type-updating.cpp
index d9935ee32..ceb37300a 100644
--- a/src/ir/type-updating.cpp
+++ b/src/ir/type-updating.cpp
@@ -90,7 +90,7 @@ GlobalTypeRewriter::TypeMap GlobalTypeRewriter::rebuildTypes(
   i = 0;
   for (auto [type, _] : typeIndices) {
     typeBuilder[i].setOpen(type.isOpen());
-    typeBuilder[i].setShared(type.isShared());
+    typeBuilder[i].setShared(type.getShared());
     if (type.isSignature()) {
       auto sig = type.getSignature();
       TypeList newParams, newResults;
diff --git a/src/parser/contexts.h b/src/parser/contexts.h
index 6dabfca3d..f58275d71 100644
--- a/src/parser/contexts.h
+++ b/src/parser/contexts.h
@@ -105,24 +105,21 @@ struct NullTypeParserCtx {
   using ElemListT = Ok;
   using DataStringT = Ok;
 
-  HeapTypeT makeFuncType() { return Ok{}; }
-  HeapTypeT makeAnyType() { return Ok{}; }
-  HeapTypeT makeExternType() { return Ok{}; }
-  HeapTypeT makeEqType() { return Ok{}; }
-  HeapTypeT makeI31Type() { return Ok{}; }
-  HeapTypeT makeStructType() { return Ok{}; }
-  HeapTypeT makeArrayType() { return Ok{}; }
-  HeapTypeT makeExnType() { return Ok{}; }
-  HeapTypeT makeStringType() { return Ok{}; }
-  HeapTypeT makeStringViewWTF8Type() { return Ok{}; }
-  HeapTypeT makeStringViewWTF16Type() { return Ok{}; }
-  HeapTypeT makeStringViewIterType() { return Ok{}; }
-  HeapTypeT makeContType() { return Ok{}; }
-  HeapTypeT makeNoneType() { return Ok{}; }
-  HeapTypeT makeNoextType() { return Ok{}; }
-  HeapTypeT makeNofuncType() { return Ok{}; }
-  HeapTypeT makeNoexnType() { return Ok{}; }
-  HeapTypeT makeNocontType() { return Ok{}; }
+  HeapTypeT makeFuncType(Shareability) { return Ok{}; }
+  HeapTypeT makeAnyType(Shareability) { return Ok{}; }
+  HeapTypeT makeExternType(Shareability) { return Ok{}; }
+  HeapTypeT makeEqType(Shareability) { return Ok{}; }
+  HeapTypeT makeI31Type(Shareability) { return Ok{}; }
+  HeapTypeT makeStructType(Shareability) { return Ok{}; }
+  HeapTypeT makeArrayType(Shareability) { return Ok{}; }
+  HeapTypeT makeExnType(Shareability) { return Ok{}; }
+  HeapTypeT makeStringType(Shareability) { return Ok{}; }
+  HeapTypeT makeContType(Shareability) { return Ok{}; }
+  HeapTypeT makeNoneType(Shareability) { return Ok{}; }
+  HeapTypeT makeNoextType(Shareability) { return Ok{}; }
+  HeapTypeT makeNofuncType(Shareability) { return Ok{}; }
+  HeapTypeT makeNoexnType(Shareability) { return Ok{}; }
+  HeapTypeT makeNocontType(Shareability) { return Ok{}; }
 
   TypeT makeI32() { return Ok{}; }
   TypeT makeI64() { return Ok{}; }
@@ -208,21 +205,51 @@ template<typename Ctx> struct TypeParserCtx {
 
   Ctx& self() { return *static_cast<Ctx*>(this); }
 
-  HeapTypeT makeFuncType() { return HeapType::func; }
-  HeapTypeT makeAnyType() { return HeapType::any; }
-  HeapTypeT makeExternType() { return HeapType::ext; }
-  HeapTypeT makeEqType() { return HeapType::eq; }
-  HeapTypeT makeI31Type() { return HeapType::i31; }
-  HeapTypeT makeStructType() { return HeapType::struct_; }
-  HeapTypeT makeArrayType() { return HeapType::array; }
-  HeapTypeT makeExnType() { return HeapType::exn; }
-  HeapTypeT makeStringType() { return HeapType::string; }
-  HeapTypeT makeContType() { return HeapType::cont; }
-  HeapTypeT makeNoneType() { return HeapType::none; }
-  HeapTypeT makeNoextType() { return HeapType::noext; }
-  HeapTypeT makeNofuncType() { return HeapType::nofunc; }
-  HeapTypeT makeNoexnType() { return HeapType::noexn; }
-  HeapTypeT makeNocontType() { return HeapType::nocont; }
+  HeapTypeT makeFuncType(Shareability share) {
+    return HeapTypes::func.getBasic(share);
+  }
+  HeapTypeT makeAnyType(Shareability share) {
+    return HeapTypes::any.getBasic(share);
+  }
+  HeapTypeT makeExternType(Shareability share) {
+    return HeapTypes::ext.getBasic(share);
+  }
+  HeapTypeT makeEqType(Shareability share) {
+    return HeapTypes::eq.getBasic(share);
+  }
+  HeapTypeT makeI31Type(Shareability share) {
+    return HeapTypes::i31.getBasic(share);
+  }
+  HeapTypeT makeStructType(Shareability share) {
+    return HeapTypes::struct_.getBasic(share);
+  }
+  HeapTypeT makeArrayType(Shareability share) {
+    return HeapTypes::array.getBasic(share);
+  }
+  HeapTypeT makeExnType(Shareability share) {
+    return HeapTypes::exn.getBasic(share);
+  }
+  HeapTypeT makeStringType(Shareability share) {
+    return HeapTypes::string.getBasic(share);
+  }
+  HeapTypeT makeContType(Shareability share) {
+    return HeapTypes::cont.getBasic(share);
+  }
+  HeapTypeT makeNoneType(Shareability share) {
+    return HeapTypes::none.getBasic(share);
+  }
+  HeapTypeT makeNoextType(Shareability share) {
+    return HeapTypes::noext.getBasic(share);
+  }
+  HeapTypeT makeNofuncType(Shareability share) {
+    return HeapTypes::nofunc.getBasic(share);
+  }
+  HeapTypeT makeNoexnType(Shareability share) {
+    return HeapTypes::noexn.getBasic(share);
+  }
+  HeapTypeT makeNocontType(Shareability share) {
+    return HeapTypes::nocont.getBasic(share);
+  }
 
   TypeT makeI32() { return Type::i32; }
   TypeT makeI64() { return Type::i64; }
diff --git a/src/parser/parsers.h b/src/parser/parsers.h
index 1c329aecb..db450e3c6 100644
--- a/src/parser/parsers.h
+++ b/src/parser/parsers.h
@@ -27,6 +27,8 @@ namespace wasm::WATParser {
 using namespace std::string_view_literals;
 
 // Types
+template<typename Ctx>
+Result<typename Ctx::HeapTypeT> absheaptype(Ctx&, Shareability);
 template<typename Ctx> Result<typename Ctx::HeapTypeT> heaptype(Ctx&);
 template<typename Ctx> MaybeResult<typename Ctx::RefTypeT> maybeRefType(Ctx&);
 template<typename Ctx> Result<typename Ctx::RefTypeT> reftype(Ctx&);
@@ -358,58 +360,73 @@ template<typename Ctx> Result<> module(Ctx&);
 // Types
 // =====
 
-// heaptype ::= x:typeidx => types[x]
-//            | 'func'    => func
-//            | 'extern'  => extern
-template<typename Ctx> Result<typename Ctx::HeapTypeT> heaptype(Ctx& ctx) {
+// absheaptype ::= 'func' | 'extern' | ...
+template<typename Ctx>
+Result<typename Ctx::HeapTypeT> absheaptype(Ctx& ctx, Shareability share) {
   if (ctx.in.takeKeyword("func"sv)) {
-    return ctx.makeFuncType();
+    return ctx.makeFuncType(share);
   }
   if (ctx.in.takeKeyword("any"sv)) {
-    return ctx.makeAnyType();
+    return ctx.makeAnyType(share);
   }
   if (ctx.in.takeKeyword("extern"sv)) {
-    return ctx.makeExternType();
+    return ctx.makeExternType(share);
   }
   if (ctx.in.takeKeyword("eq"sv)) {
-    return ctx.makeEqType();
+    return ctx.makeEqType(share);
   }
   if (ctx.in.takeKeyword("i31"sv)) {
-    return ctx.makeI31Type();
+    return ctx.makeI31Type(share);
   }
   if (ctx.in.takeKeyword("struct"sv)) {
-    return ctx.makeStructType();
+    return ctx.makeStructType(share);
   }
   if (ctx.in.takeKeyword("array"sv)) {
-    return ctx.makeArrayType();
+    return ctx.makeArrayType(share);
   }
   if (ctx.in.takeKeyword("exn"sv)) {
-    return ctx.makeExnType();
+    return ctx.makeExnType(share);
   }
   if (ctx.in.takeKeyword("string"sv)) {
-    return ctx.makeStringType();
+    return ctx.makeStringType(share);
   }
   if (ctx.in.takeKeyword("cont"sv)) {
-    return ctx.makeContType();
+    return ctx.makeContType(share);
   }
   if (ctx.in.takeKeyword("none"sv)) {
-    return ctx.makeNoneType();
+    return ctx.makeNoneType(share);
   }
   if (ctx.in.takeKeyword("noextern"sv)) {
-    return ctx.makeNoextType();
+    return ctx.makeNoextType(share);
   }
   if (ctx.in.takeKeyword("nofunc"sv)) {
-    return ctx.makeNofuncType();
+    return ctx.makeNofuncType(share);
   }
   if (ctx.in.takeKeyword("noexn"sv)) {
-    return ctx.makeNoexnType();
+    return ctx.makeNoexnType(share);
   }
   if (ctx.in.takeKeyword("nocont"sv)) {
-    return ctx.makeNocontType();
+    return ctx.makeNocontType(share);
   }
-  auto type = typeidx(ctx);
-  CHECK_ERR(type);
-  return *type;
+  return ctx.in.err("expected abstract heap type");
+}
+
+// heaptype ::= x:typeidx                      => types[x]
+//            | t:absheaptype                  => unshared t
+//            | '(' 'shared' t:absheaptype ')' => shared t
+template<typename Ctx> Result<typename Ctx::HeapTypeT> heaptype(Ctx& ctx) {
+  if (auto t = maybeTypeidx(ctx)) {
+    CHECK_ERR(t);
+    return *t;
+  }
+
+  auto share = ctx.in.takeSExprStart("shared"sv) ? Shared : Unshared;
+  auto t = absheaptype(ctx, share);
+  CHECK_ERR(t);
+  if (share == Shared && !ctx.in.takeRParen()) {
+    return ctx.in.err("expected end of shared abstract heap type");
+  }
+  return *t;
 }
 
 // reftype ::= 'funcref'   => funcref
@@ -422,49 +439,49 @@ template<typename Ctx> Result<typename Ctx::HeapTypeT> heaptype(Ctx& ctx) {
 //           | '(' ref null? t:heaptype ')' => ref null? t
 template<typename Ctx> MaybeResult<typename Ctx::TypeT> maybeReftype(Ctx& ctx) {
   if (ctx.in.takeKeyword("funcref"sv)) {
-    return ctx.makeRefType(ctx.makeFuncType(), Nullable);
+    return ctx.makeRefType(ctx.makeFuncType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("externref"sv)) {
-    return ctx.makeRefType(ctx.makeExternType(), Nullable);
+    return ctx.makeRefType(ctx.makeExternType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("anyref"sv)) {
-    return ctx.makeRefType(ctx.makeAnyType(), Nullable);
+    return ctx.makeRefType(ctx.makeAnyType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("eqref"sv)) {
-    return ctx.makeRefType(ctx.makeEqType(), Nullable);
+    return ctx.makeRefType(ctx.makeEqType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("i31ref"sv)) {
-    return ctx.makeRefType(ctx.makeI31Type(), Nullable);
+    return ctx.makeRefType(ctx.makeI31Type(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("structref"sv)) {
-    return ctx.makeRefType(ctx.makeStructType(), Nullable);
+    return ctx.makeRefType(ctx.makeStructType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("arrayref"sv)) {
-    return ctx.makeRefType(ctx.makeArrayType(), Nullable);
+    return ctx.makeRefType(ctx.makeArrayType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("exnref"sv)) {
-    return ctx.makeRefType(ctx.makeExnType(), Nullable);
+    return ctx.makeRefType(ctx.makeExnType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("stringref"sv)) {
-    return ctx.makeRefType(ctx.makeStringType(), Nullable);
+    return ctx.makeRefType(ctx.makeStringType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("contref"sv)) {
-    return ctx.makeRefType(ctx.makeContType(), Nullable);
+    return ctx.makeRefType(ctx.makeContType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("nullref"sv)) {
-    return ctx.makeRefType(ctx.makeNoneType(), Nullable);
+    return ctx.makeRefType(ctx.makeNoneType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("nullexternref"sv)) {
-    return ctx.makeRefType(ctx.makeNoextType(), Nullable);
+    return ctx.makeRefType(ctx.makeNoextType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("nullfuncref"sv)) {
-    return ctx.makeRefType(ctx.makeNofuncType(), Nullable);
+    return ctx.makeRefType(ctx.makeNofuncType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("nullexnref"sv)) {
-    return ctx.makeRefType(ctx.makeNoexnType(), Nullable);
+    return ctx.makeRefType(ctx.makeNoexnType(Unshared), Nullable);
   }
   if (ctx.in.takeKeyword("nullcontref"sv)) {
-    return ctx.makeRefType(ctx.makeNocontType(), Nullable);
+    return ctx.makeRefType(ctx.makeNocontType(Unshared), Nullable);
   }
 
   if (!ctx.in.takeSExprStart("ref"sv)) {
diff --git a/src/passes/TypeGeneralizing.cpp b/src/passes/TypeGeneralizing.cpp
index 81dd0a39e..720830400 100644
--- a/src/passes/TypeGeneralizing.cpp
+++ b/src/passes/TypeGeneralizing.cpp
@@ -58,7 +58,7 @@ using TypeRequirement = Inverted<ValType>;
 
 // Record a type requirement for each local variable. Shared the requirements
 // across basic blocks.
-using LocalTypeRequirements = Shared<Vector<TypeRequirement>>;
+using LocalTypeRequirements = SharedPath<Vector<TypeRequirement>>;
 
 // The type requirements for each reference-typed value on the stack at a
 // particular location.
@@ -75,7 +75,8 @@ struct State : StateLattice {
   static constexpr int LocalsIndex = 0;
   static constexpr int StackIndex = 1;
 
-  State(Function* func) : StateLattice{Shared{initLocals(func)}, initStack()} {}
+  State(Function* func)
+    : StateLattice{SharedPath{initLocals(func)}, initStack()} {}
 
   void push(Element& elem, Type type) const noexcept {
     stackLattice().push(stack(elem), std::move(type));
@@ -109,7 +110,7 @@ struct State : StateLattice {
 
 private:
   static LocalTypeRequirements initLocals(Function* func) noexcept {
-    return Shared{Vector{Inverted{ValType{}}, func->getNumLocals()}};
+    return SharedPath{Vector{Inverted{ValType{}}, func->getNumLocals()}};
   }
 
   static ValueStackTypeRequirements initStack() noexcept {
diff --git a/src/tools/fuzzing/fuzzing.cpp b/src/tools/fuzzing/fuzzing.cpp
index 57c7ec6b0..6b54ac56d 100644
--- a/src/tools/fuzzing/fuzzing.cpp
+++ b/src/tools/fuzzing/fuzzing.cpp
@@ -2556,7 +2556,8 @@ Expression* TranslateToFuzzReader::makeBasicRef(Type type) {
   auto heapType = type.getHeapType();
   assert(heapType.isBasic());
   assert(wasm.features.hasReferenceTypes());
-  switch (heapType.getBasic()) {
+  assert(!heapType.isShared() && "TODO: handle shared types");
+  switch (heapType.getBasic(Unshared)) {
     case HeapType::ext: {
       auto null = builder.makeRefNull(HeapType::ext);
       // TODO: support actual non-nullable externrefs via imported globals or
@@ -4233,7 +4234,8 @@ HeapType TranslateToFuzzReader::getSubType(HeapType type) {
     return type;
   }
   if (type.isBasic() && oneIn(2)) {
-    switch (type.getBasic()) {
+    assert(!type.isShared() && "TODO: handle shared types");
+    switch (type.getBasic(Unshared)) {
       case HeapType::func:
         // TODO: Typed function references.
         return pick(FeatureOptions<HeapType>()
diff --git a/src/tools/fuzzing/heap-types.cpp b/src/tools/fuzzing/heap-types.cpp
index 08b4c4453..127d4f5ba 100644
--- a/src/tools/fuzzing/heap-types.cpp
+++ b/src/tools/fuzzing/heap-types.cpp
@@ -377,7 +377,8 @@ struct HeapTypeGeneratorImpl {
       if (rand.oneIn(8)) {
         return type.getBottom();
       }
-      switch (type.getBasic()) {
+      assert(!type.isShared() && "TODO: handle shared types");
+      switch (type.getBasic(Unshared)) {
         case HeapType::func:
           return pickSubFunc();
         case HeapType::cont:
@@ -438,7 +439,8 @@ struct HeapTypeGeneratorImpl {
     // This is not a constructed type, so it must be a basic type.
     assert(type.isBasic());
     candidates.push_back(type);
-    switch (type.getBasic()) {
+    assert(!type.isShared() && "TODO: handle shared types");
+    switch (type.getBasic(Unshared)) {
       case HeapType::ext:
       case HeapType::func:
       case HeapType::exn:
diff --git a/src/tools/wasm-fuzz-lattices.cpp b/src/tools/wasm-fuzz-lattices.cpp
index d74bc5148..551ddbaf1 100644
--- a/src/tools/wasm-fuzz-lattices.cpp
+++ b/src/tools/wasm-fuzz-lattices.cpp
@@ -185,7 +185,7 @@ using LatticeVariant = std::variant<RandomFullLattice,
                                     ArrayLattice,
                                     Vector<RandomLattice>,
                                     TupleLattice,
-                                    Shared<RandomLattice>>;
+                                    SharedPath<RandomLattice>>;
 
 struct RandomLattice::LatticeImpl : LatticeVariant {};
 
@@ -196,7 +196,7 @@ using LatticeElementVariant =
                typename ArrayLattice::Element,
                typename Vector<RandomLattice>::Element,
                typename TupleLattice::Element,
-               typename Shared<RandomLattice>::Element>;
+               typename SharedPath<RandomLattice>::Element>;
 
 struct RandomLattice::ElementImpl : LatticeElementVariant {};
 
@@ -271,7 +271,7 @@ RandomLattice::RandomLattice(Random& rand, size_t depth) : rand(rand) {
       return;
     case FullLatticePicks + 5:
       lattice = std::make_unique<LatticeImpl>(
-        LatticeImpl{Shared{RandomLattice{rand, depth + 1}}});
+        LatticeImpl{SharedPath{RandomLattice{rand, depth + 1}}});
       return;
   }
   WASM_UNREACHABLE("unexpected pick");
@@ -375,7 +375,7 @@ RandomLattice::Element RandomLattice::makeElement() const noexcept {
       typename TupleLattice::Element{std::get<0>(l->lattices).makeElement(),
                                      std::get<1>(l->lattices).makeElement()}};
   }
-  if (const auto* l = std::get_if<Shared<RandomLattice>>(lattice.get())) {
+  if (const auto* l = std::get_if<SharedPath<RandomLattice>>(lattice.get())) {
     auto elem = l->getBottom();
     l->join(elem, l->lattice.makeElement());
     return ElementImpl{elem};
@@ -489,8 +489,9 @@ void printElement(std::ostream& os,
     indent(os, depth);
     os << ")\n";
   } else if (const auto* e =
-               std::get_if<typename Shared<RandomLattice>::Element>(&*elem)) {
-    os << "Shared(\n";
+               std::get_if<typename SharedPath<RandomLattice>::Element>(
+                 &*elem)) {
+    os << "SharedPath(\n";
     printElement(os, **e, depth + 1);
     indent(os, depth);
     os << ")\n";
diff --git a/src/wasm-type.h b/src/wasm-type.h
index 2a74e4a60..95c3605a5 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -310,6 +310,8 @@ public:
   const Type& operator[](size_t i) const { return *Iterator{{this, i}}; }
 };
 
+enum Shareability { Shared, Unshared };
+
 class HeapType {
   // Unlike `Type`, which represents the types of values on the WebAssembly
   // stack, `HeapType` is used to describe the structures that reference types
@@ -318,24 +320,26 @@ class HeapType {
   uintptr_t id;
 
 public:
+  // Bit zero indicates whether the type is `shared`, so we need to leave it
+  // free.
   enum BasicHeapType : uint32_t {
-    ext,
-    func,
-    cont,
-    any,
-    eq,
-    i31,
-    struct_,
-    array,
-    exn,
-    string,
-    none,
-    noext,
-    nofunc,
-    nocont,
-    noexn,
+    ext = 0 << 1,
+    func = 1 << 1,
+    cont = 2 << 1,
+    any = 3 << 1,
+    eq = 4 << 1,
+    i31 = 5 << 1,
+    struct_ = 6 << 1,
+    array = 7 << 1,
+    exn = 8 << 1,
+    string = 9 << 1,
+    none = 10 << 1,
+    noext = 11 << 1,
+    nofunc = 12 << 1,
+    nocont = 13 << 1,
+    noexn = 14 << 1,
   };
-  static constexpr BasicHeapType _last_basic_type = noexn;
+  static constexpr BasicHeapType _last_basic_type = BasicHeapType(noexn + 1);
 
   // BasicHeapType can be implicitly upgraded to HeapType
   constexpr HeapType(BasicHeapType id) : id(id) {}
@@ -377,7 +381,9 @@ public:
   bool isString() const;
   bool isBottom() const;
   bool isOpen() const;
-  bool isShared() const;
+  bool isShared() const { return getShared() == Shared; }
+
+  Shareability getShared() const;
 
   Signature getSignature() const;
   Continuation getContinuation() const;
@@ -399,19 +405,27 @@ public:
   size_t getDepth() const;
 
   // Get the bottom heap type for this heap type's hierarchy.
-  BasicHeapType getBottom() const;
+  BasicHeapType getUnsharedBottom() const;
+  BasicHeapType getBottom() const {
+    return HeapType(getUnsharedBottom()).getBasic(getShared());
+  }
 
   // Get the top heap type for this heap type's hierarchy.
-  BasicHeapType getTop() const;
+  BasicHeapType getUnsharedTop() const;
+  BasicHeapType getTop() const {
+    return HeapType(getUnsharedTop()).getBasic(getShared());
+  }
 
   // Get the recursion group for this non-basic type.
   RecGroup getRecGroup() const;
   size_t getRecGroupIndex() const;
 
   constexpr TypeID getID() const { return id; }
-  constexpr BasicHeapType getBasic() const {
-    assert(isBasic() && "Basic heap type expected");
-    return static_cast<BasicHeapType>(id);
+
+  // Get the shared or unshared version of this basic heap type.
+  constexpr BasicHeapType getBasic(Shareability share) const {
+    assert(isBasic());
+    return BasicHeapType(share == Shared ? (id | 1) : (id & ~1));
   }
 
   // (In)equality must be defined for both HeapType and BasicHeapType because it
@@ -644,7 +658,7 @@ struct TypeBuilder {
   void createRecGroup(size_t i, size_t length);
 
   void setOpen(size_t i, bool open = true);
-  void setShared(size_t i, bool shared = true);
+  void setShared(size_t i, Shareability share = Shared);
 
   enum class ErrorReason {
     // There is a cycle in the supertype relation.
@@ -717,8 +731,8 @@ struct TypeBuilder {
       builder.setOpen(index, open);
       return *this;
     }
-    Entry& setShared(bool shared = true) {
-      builder.setShared(index, shared);
+    Entry& setShared(Shareability share = Shared) {
+      builder.setShared(index, share);
       return *this;
     }
   };
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) {