[GC] Add Array operations (#3436)

array.new/get/set/len - pretty straightforward after structs and all the
infrastructure for them.

Also fixes validation of the unnecessary heapType param in the
text and binary formats in structs as well as arrays.

Fixes printing of packed types in type names, which emitted i32
for them. That broke when we emitted the same name for an array
of i8 and i32 as in the new testing here.

Also fix a bug in Field::operator< which was wrong for packed
types; again, this was easy to notice with the new testing.

17 files changed, 469 insertions, 174 deletions

diff --git a/src/ir/cost.h b/src/ir/cost.h
index 0c5a13819..b71e1ea0e 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -586,12 +586,21 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, Index> {
     return 1 + nullCheckCost(curr->ref) + visit(curr->ref);
   }
   Index visitStructSet(StructSet* curr) {
-    return 1 + nullCheckCost(curr->ref) + visit(curr->ref) + visit(curr->value);
+    return 2 + nullCheckCost(curr->ref) + visit(curr->ref) + visit(curr->value);
+  }
+  Index visitArrayNew(ArrayNew* curr) {
+    return 4 + visit(curr->rtt) + visit(curr->size) + visit(curr->init);
+  }
+  Index visitArrayGet(ArrayGet* curr) {
+    return 1 + nullCheckCost(curr->ref) + visit(curr->ref) + visit(curr->index);
+  }
+  Index visitArraySet(ArraySet* curr) {
+    return 2 + nullCheckCost(curr->ref) + visit(curr->ref) +
+           visit(curr->index) + visit(curr->value);
+  }
+  Index visitArrayLen(ArrayLen* curr) {
+    return 1 + nullCheckCost(curr->ref) + visit(curr->ref);
   }
-  Index visitArrayNew(ArrayNew* curr) { WASM_UNREACHABLE("TODO: GC"); }
-  Index visitArrayGet(ArrayGet* curr) { WASM_UNREACHABLE("TODO: GC"); }
-  Index visitArraySet(ArraySet* curr) { WASM_UNREACHABLE("TODO: GC"); }
-  Index visitArrayLen(ArrayLen* curr) { WASM_UNREACHABLE("TODO: GC"); }
 
 private:
   Index nullCheckCost(Expression* ref) {
diff --git a/src/ir/effects.h b/src/ir/effects.h
index e4907b082..94387c2cf 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -556,8 +556,7 @@ private:
     }
     void visitRttCanon(RttCanon* curr) {}
     void visitRttSub(RttSub* curr) {}
-    void visitStructNew(StructNew* curr) {
-    }
+    void visitStructNew(StructNew* curr) {}
     void visitStructGet(StructGet* curr) {
       // traps when the arg is null
       if (curr->ref->type.isNullable()) {
@@ -570,17 +569,20 @@ private:
         parent.implicitTrap = true;
       }
     }
-    void visitArrayNew(ArrayNew* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.new");
-    }
+    void visitArrayNew(ArrayNew* curr) {}
     void visitArrayGet(ArrayGet* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.get");
+      // traps when the arg is null or the index out of bounds
+      parent.implicitTrap = true;
     }
     void visitArraySet(ArraySet* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.set");
+      // traps when the arg is null or the index out of bounds
+      parent.implicitTrap = true;
     }
     void visitArrayLen(ArrayLen* curr) {
-      WASM_UNREACHABLE("TODO (gc): array.len");
+      // traps when the arg is null
+      if (curr->ref->type.isNullable()) {
+        parent.implicitTrap = true;
+      }
     }
   };
 
diff --git a/src/literal.h b/src/literal.h
index 72224613d..80a7cea7a 100644
--- a/src/literal.h
+++ b/src/literal.h
@@ -654,7 +654,9 @@ public:
       assert(lit.isConcrete());
     }
 #endif
-  };
+  }
+  Literals(size_t initialSize) : SmallVector(initialSize) {}
+
   Type getType() {
     std::vector<Type> types;
     for (auto& val : *this) {
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 0577c7c02..694b1b118 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -104,6 +104,23 @@ static void printTypeName(std::ostream& os, Type type) {
   WASM_UNREACHABLE("unsupported print type");
 }
 
+static void printFieldName(std::ostream& os, const Field& field) {
+  if (field.mutable_) {
+    os << "mut:";
+  }
+  if (field.type == Type::i32 && field.packedType != Field::not_packed) {
+    if (field.packedType == Field::i8) {
+      os << "i8";
+    } else if (field.packedType == Field::i16) {
+      os << "i16";
+    } else {
+      WASM_UNREACHABLE("invalid packed type");
+    }
+  } else {
+    printTypeName(os, field.type);
+  }
+}
+
 static void printHeapTypeName(std::ostream& os, HeapType type, bool first) {
   if (type.isBasic()) {
     os << type;
@@ -128,19 +145,12 @@ static void printHeapTypeName(std::ostream& os, HeapType type, bool first) {
     for (auto& field : struct_.fields) {
       os << sep;
       sep = "_";
-      if (field.mutable_) {
-        os << "mut:";
-      }
-      printTypeName(os, field.type);
+      printFieldName(os, field);
     }
     os << "}";
   } else if (type.isArray()) {
     os << "[";
-    auto element = type.getArray().element;
-    if (element.mutable_) {
-      os << "mut:";
-    }
-    printTypeName(os, element.type);
+    printFieldName(os, type.getArray().element);
     os << "]";
   } else {
     os << type;
@@ -1732,18 +1742,33 @@ struct PrintExpressionContents
     o << curr->index;
   }
   void visitArrayNew(ArrayNew* curr) {
-    WASM_UNREACHABLE("TODO (gc): array.new");
+    printMedium(o, "array.new_");
+    if (curr->isWithDefault()) {
+      o << "default_";
+    }
+    o << "with_rtt ";
+    printHeapTypeName(o, curr->rtt->type.getRtt().heapType);
   }
   void visitArrayGet(ArrayGet* curr) {
-    WASM_UNREACHABLE("TODO (gc): array.get");
+    const auto& element = curr->ref->type.getHeapType().getArray().element;
+    if (element.type == Type::i32 && element.packedType != Field::not_packed) {
+      if (curr->signed_) {
+        printMedium(o, "array.get_s ");
+      } else {
+        printMedium(o, "array.get_u ");
+      }
+    } else {
+      printMedium(o, "array.get ");
+    }
+    printHeapTypeName(o, curr->ref->type.getHeapType());
   }
   void visitArraySet(ArraySet* curr) {
-    printMedium(o, "array.set");
-    WASM_UNREACHABLE("TODO (gc): array.set");
+    printMedium(o, "array.set ");
+    printHeapTypeName(o, curr->ref->type.getHeapType());
   }
   void visitArrayLen(ArrayLen* curr) {
-    printMedium(o, "array.len");
-    WASM_UNREACHABLE("TODO (gc): array.len");
+    printMedium(o, "array.len ");
+    printHeapTypeName(o, curr->ref->type.getHeapType());
   }
 };
 
@@ -2421,22 +2446,37 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
   void visitArrayNew(ArrayNew* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
-    WASM_UNREACHABLE("TODO (gc): array.new");
+    incIndent();
+    printFullLine(curr->rtt);
+    printFullLine(curr->size);
+    if (curr->init) {
+      printFullLine(curr->init);
+    }
+    decIndent();
   }
   void visitArrayGet(ArrayGet* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
-    WASM_UNREACHABLE("TODO (gc): array.get");
+    incIndent();
+    printFullLine(curr->ref);
+    printFullLine(curr->index);
+    decIndent();
   }
   void visitArraySet(ArraySet* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
-    WASM_UNREACHABLE("TODO (gc): array.set");
+    incIndent();
+    printFullLine(curr->ref);
+    printFullLine(curr->index);
+    printFullLine(curr->value);
+    decIndent();
   }
   void visitArrayLen(ArrayLen* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
-    WASM_UNREACHABLE("TODO (gc): array.len");
+    incIndent();
+    printFullLine(curr->ref);
+    decIndent();
   }
   // Module-level visitors
   void handleSignature(Signature curr, Name name = Name()) {
diff --git a/src/support/small_vector.h b/src/support/small_vector.h
index baf217086..2e65eda41 100644
--- a/src/support/small_vector.h
+++ b/src/support/small_vector.h
@@ -46,6 +46,7 @@ public:
       push_back(item);
     }
   }
+  SmallVector(size_t initialSize) { resize(initialSize); }
 
   T& operator[](size_t i) {
     if (i < N) {
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 8b5988602..dffc1507c 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1503,6 +1503,13 @@ public:
 
   void throwError(std::string text);
 
+  // Struct/Array instructions have an unnecessary heap type that is just for
+  // validation (except for the case of unreachability, but that's not a problem
+  // anyhow, we can ignore it there). That is, we also have a reference / rtt
+  // child from which we can infer the type anyhow, and we just need to check
+  // that type is the same.
+  void validateHeapTypeUsingChild(Expression* child, HeapType heapType);
+
 private:
   bool hasDWARFSections();
 };
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 213edbef5..73c8f9823 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -753,27 +753,36 @@ public:
     ret->finalize();
     return ret;
   }
-  ArrayNew* makeArrayNew() {
+  ArrayNew*
+  makeArrayNew(Expression* rtt, Expression* size, Expression* init = nullptr) {
     auto* ret = wasm.allocator.alloc<ArrayNew>();
-    WASM_UNREACHABLE("TODO (gc): array.new");
+    ret->rtt = rtt;
+    ret->size = size;
+    ret->init = init;
     ret->finalize();
     return ret;
   }
-  ArrayGet* makeArrayGet() {
+  ArrayGet*
+  makeArrayGet(Expression* ref, Expression* index, bool signed_ = false) {
     auto* ret = wasm.allocator.alloc<ArrayGet>();
-    WASM_UNREACHABLE("TODO (gc): array.get");
+    ret->ref = ref;
+    ret->index = index;
+    ret->signed_ = signed_;
     ret->finalize();
     return ret;
   }
-  ArraySet* makeArraySet() {
+  ArraySet*
+  makeArraySet(Expression* ref, Expression* index, Expression* value) {
     auto* ret = wasm.allocator.alloc<ArraySet>();
-    WASM_UNREACHABLE("TODO (gc): array.set");
+    ret->ref = ref;
+    ret->index = index;
+    ret->value = value;
     ret->finalize();
     return ret;
   }
-  ArrayLen* makeArrayLen() {
+  ArrayLen* makeArrayLen(Expression* ref) {
     auto* ret = wasm.allocator.alloc<ArrayLen>();
-    WASM_UNREACHABLE("TODO (gc): array.len");
+    ret->ref = ref;
     ret->finalize();
     return ret;
   }
diff --git a/src/wasm-delegations-fields.h b/src/wasm-delegations-fields.h
index fa93710ab..b90bf720b 100644
--- a/src/wasm-delegations-fields.h
+++ b/src/wasm-delegations-fields.h
@@ -597,7 +597,7 @@ switch (DELEGATE_ID) {
     DELEGATE_START(StructGet);
     DELEGATE_FIELD_INT(StructGet, index);
     DELEGATE_FIELD_CHILD(StructGet, ref);
-    DELEGATE_FIELD_INT(Load, signed_);
+    DELEGATE_FIELD_INT(StructGet, signed_);
     DELEGATE_END(StructGet);
     break;
   }
@@ -611,25 +611,31 @@ switch (DELEGATE_ID) {
   }
   case Expression::Id::ArrayNewId: {
     DELEGATE_START(ArrayNew);
-    WASM_UNREACHABLE("TODO (gc): array.new");
+    DELEGATE_FIELD_CHILD(ArrayNew, rtt);
+    DELEGATE_FIELD_CHILD(ArrayNew, size);
+    DELEGATE_FIELD_OPTIONAL_CHILD(ArrayNew, init);
     DELEGATE_END(ArrayNew);
     break;
   }
   case Expression::Id::ArrayGetId: {
     DELEGATE_START(ArrayGet);
-    WASM_UNREACHABLE("TODO (gc): array.get");
+    DELEGATE_FIELD_CHILD(ArrayGet, ref);
+    DELEGATE_FIELD_CHILD(ArrayGet, index);
+    DELEGATE_FIELD_INT(ArrayGet, signed_);
     DELEGATE_END(ArrayGet);
     break;
   }
   case Expression::Id::ArraySetId: {
     DELEGATE_START(ArraySet);
-    WASM_UNREACHABLE("TODO (gc): array.set");
+    DELEGATE_FIELD_CHILD(ArrayGet, ref);
+    DELEGATE_FIELD_CHILD(ArrayGet, index);
+    DELEGATE_FIELD_CHILD(ArrayGet, value);
     DELEGATE_END(ArraySet);
     break;
   }
   case Expression::Id::ArrayLenId: {
     DELEGATE_START(ArrayLen);
-    WASM_UNREACHABLE("TODO (gc): array.len");
+    DELEGATE_FIELD_CHILD(ArrayLen, ref);
     DELEGATE_END(ArrayLen);
     break;
   }
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index bf02b7987..d701aaf15 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1403,8 +1403,7 @@ public:
       return rtt;
     }
     const auto& fields = curr->rtt->type.getHeapType().getStruct().fields;
-    Literals data;
-    data.resize(fields.size());
+    Literals data(fields.size());
     for (Index i = 0; i < fields.size(); i++) {
       if (curr->isWithDefault()) {
         data[i] = Literal::makeZero(fields[i].type);
@@ -1416,8 +1415,7 @@ public:
         data[i] = value.getSingleValue();
       }
     }
-    return Flow(
-      Literal(std::shared_ptr<Literals>(new Literals(data)), curr->type));
+    return Flow(Literal(std::make_shared<Literals>(data), curr->type));
   }
   Flow visitStructGet(StructGet* curr) {
     NOTE_ENTER("StructGet");
@@ -1445,40 +1443,115 @@ public:
     if (!data) {
       trap("null ref");
     }
-    // Truncate the value if we need to. The storage is just a list of Literals,
-    // so we can't just write the value like we would to a C struct field.
     auto field = curr->ref->type.getHeapType().getStruct().fields[curr->index];
-    auto setValue = value.getSingleValue();
-    if (field.type == Type::i32) {
-      if (field.packedType == Field::i8) {
-        setValue = setValue.and_(Literal(int32_t(0xff)));
-      } else if (field.packedType == Field::i16) {
-        setValue = setValue.and_(Literal(int32_t(0xffff)));
-      }
-    }
-    (*data)[curr->index] = setValue;
+    (*data)[curr->index] = getMaybePackedValue(value.getSingleValue(), field);
     return Flow();
   }
   Flow visitArrayNew(ArrayNew* curr) {
     NOTE_ENTER("ArrayNew");
-    WASM_UNREACHABLE("TODO (gc): array.new");
+    auto rtt = this->visit(curr->rtt);
+    if (rtt.breaking()) {
+      return rtt;
+    }
+    auto size = this->visit(curr->size);
+    if (size.breaking()) {
+      return size;
+    }
+    const auto& element = curr->rtt->type.getHeapType().getArray().element;
+    Index num = size.getSingleValue().geti32();
+    Literals data(num);
+    if (curr->isWithDefault()) {
+      for (Index i = 0; i < num; i++) {
+        data[i] = Literal::makeZero(element.type);
+      }
+    } else {
+      auto init = this->visit(curr->init);
+      if (init.breaking()) {
+        return init;
+      }
+      auto value = init.getSingleValue();
+      for (Index i = 0; i < num; i++) {
+        data[i] = value;
+      }
+    }
+    return Flow(Literal(std::make_shared<Literals>(data), curr->type));
   }
   Flow visitArrayGet(ArrayGet* curr) {
     NOTE_ENTER("ArrayGet");
-    WASM_UNREACHABLE("TODO (gc): array.get");
+    Flow ref = this->visit(curr->ref);
+    if (ref.breaking()) {
+      return ref;
+    }
+    Flow index = this->visit(curr->index);
+    if (index.breaking()) {
+      return index;
+    }
+    auto data = ref.getSingleValue().getGCData();
+    if (!data) {
+      trap("null ref");
+    }
+    Index i = index.getSingleValue().geti32();
+    if (i >= data->size()) {
+      trap("array oob");
+    }
+    return (*data)[i];
   }
   Flow visitArraySet(ArraySet* curr) {
     NOTE_ENTER("ArraySet");
-    WASM_UNREACHABLE("TODO (gc): array.set");
+    Flow ref = this->visit(curr->ref);
+    if (ref.breaking()) {
+      return ref;
+    }
+    Flow index = this->visit(curr->index);
+    if (index.breaking()) {
+      return index;
+    }
+    Flow value = this->visit(curr->value);
+    if (value.breaking()) {
+      return value;
+    }
+    auto data = ref.getSingleValue().getGCData();
+    if (!data) {
+      trap("null ref");
+    }
+    Index i = index.getSingleValue().geti32();
+    if (i >= data->size()) {
+      trap("array oob");
+    }
+    auto field = curr->ref->type.getHeapType().getArray().element;
+    (*data)[i] = getMaybePackedValue(value.getSingleValue(), field);
+    return Flow();
   }
   Flow visitArrayLen(ArrayLen* curr) {
     NOTE_ENTER("ArrayLen");
-    WASM_UNREACHABLE("TODO (gc): array.len");
+    Flow ref = this->visit(curr->ref);
+    if (ref.breaking()) {
+      return ref;
+    }
+    auto data = ref.getSingleValue().getGCData();
+    if (!data) {
+      trap("null ref");
+    }
+    return Literal(int32_t(data->size()));
   }
 
   virtual void trap(const char* why) { WASM_UNREACHABLE("unimp"); }
 
   virtual void throwException(Literal exn) { WASM_UNREACHABLE("unimp"); }
+
+private:
+  // Truncate the value if we need to. The storage is just a list of Literals,
+  // so we can't just write the value like we would to a C struct field.
+  Literal getMaybePackedValue(Literal value, const Field& field) {
+    if (field.type == Type::i32) {
+      if (field.packedType == Field::i8) {
+        value = value.and_(Literal(int32_t(0xff)));
+      } else if (field.packedType == Field::i16) {
+        value = value.and_(Literal(int32_t(0xffff)));
+      }
+    }
+    return value;
+  }
 };
 
 // Execute a suspected constant expression (precompute and C-API).
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index 2c70445cf..452906ab4 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -266,8 +266,7 @@ private:
   Expression* makeStructGet(Element& s, bool signed_ = false);
   Expression* makeStructSet(Element& s);
   Expression* makeArrayNew(Element& s, bool default_);
-  Expression* makeArrayGet(Element& s);
-  Expression* makeArrayGet(Element& s, bool signed_);
+  Expression* makeArrayGet(Element& s, bool signed_ = false);
   Expression* makeArraySet(Element& s);
   Expression* makeArrayLen(Element& s);
 
@@ -304,6 +303,14 @@ private:
   void parseEvent(Element& s, bool preParseImport = false);
 
   Function::DebugLocation getDebugLocation(const SourceLocation& loc);
+
+  // Struct/Array instructions have an unnecessary heap type that is just for
+  // validation (except for the case of unreachability, but that's not a problem
+  // anyhow, we can ignore it there). That is, we also have a reference / rtt
+  // child from which we can infer the type anyhow, and we just need to check
+  // that type is the same.
+  void
+  validateHeapTypeUsingChild(Expression* child, HeapType heapType, Element& s);
 };
 
 } // namespace wasm
diff --git a/src/wasm.h b/src/wasm.h
index c23819d51..0cc2f430c 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -1385,28 +1385,48 @@ class ArrayNew : public SpecificExpression<Expression::ArrayNewId> {
 public:
   ArrayNew(MixedArena& allocator) {}
 
-  void finalize() { WASM_UNREACHABLE("TODO (gc): array.new"); }
+  Expression* rtt;
+  Expression* size;
+  // If set, then the initial value is assigned to all entries in the array. If
+  // not set, this is array.new_with_default and the default of the type is
+  // used.
+  Expression* init = nullptr;
+
+  bool isWithDefault() { return !init; }
+
+  void finalize();
 };
 
 class ArrayGet : public SpecificExpression<Expression::ArrayGetId> {
 public:
   ArrayGet(MixedArena& allocator) {}
 
-  void finalize() { WASM_UNREACHABLE("TODO (gc): array.get"); }
+  Expression* ref;
+  Expression* index;
+  // Packed fields have a sign.
+  bool signed_ = false;
+
+  void finalize();
 };
 
 class ArraySet : public SpecificExpression<Expression::ArraySetId> {
 public:
   ArraySet(MixedArena& allocator) {}
 
-  void finalize() { WASM_UNREACHABLE("TODO (gc): array.set"); }
+  Expression* ref;
+  Expression* index;
+  Expression* value;
+
+  void finalize();
 };
 
 class ArrayLen : public SpecificExpression<Expression::ArrayLenId> {
 public:
   ArrayLen(MixedArena& allocator) {}
 
-  void finalize() { WASM_UNREACHABLE("TODO (gc): array.len"); }
+  Expression* ref;
+
+  void finalize();
 };
 
 // Globals
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 6d4689056..0c68264a3 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -5655,15 +5655,8 @@ bool WasmBinaryBuilder::maybeVisitStructNew(Expression*& out, uint32_t code) {
     return false;
   }
   auto heapType = getHeapType();
-  if (!heapType.isStruct()) {
-    throwError("Non-heap type for struct.new");
-  }
   auto* rtt = popNonVoidExpression();
-  if (rtt->type != Type::unreachable) {
-    if (!rtt->type.isRtt() || rtt->type.getHeapType() != heapType) {
-      throwError("Bad heap type for struct.new");
-    }
-  }
+  validateHeapTypeUsingChild(rtt, heapType);
   std::vector<Expression*> operands;
   if (code == BinaryConsts::StructNewWithRtt) {
     auto numOperands = heapType.getStruct().fields.size();
@@ -5693,10 +5686,10 @@ bool WasmBinaryBuilder::maybeVisitStructGet(Expression*& out, uint32_t code) {
     default:
       return false;
   }
-  // This type annotation is unused. Beware it needing to be used in the future!
-  getHeapType();
+  auto heapType = getHeapType();
   curr->index = getU32LEB();
   curr->ref = popNonVoidExpression();
+  validateHeapTypeUsingChild(curr->ref, heapType);
   curr->finalize();
   out = curr;
   return true;
@@ -5707,10 +5700,10 @@ bool WasmBinaryBuilder::maybeVisitStructSet(Expression*& out, uint32_t code) {
     return false;
   }
   auto* curr = allocator.alloc<StructSet>();
-  // This type annotation is unused. Beware it needing to be used in the future!
-  getHeapType();
+  auto heapType = getHeapType();
   curr->index = getU32LEB();
   curr->ref = popNonVoidExpression();
+  validateHeapTypeUsingChild(curr->ref, heapType);
   curr->value = popNonVoidExpression();
   curr->finalize();
   out = curr;
@@ -5718,46 +5711,39 @@ bool WasmBinaryBuilder::maybeVisitStructSet(Expression*& out, uint32_t code) {
 }
 
 bool WasmBinaryBuilder::maybeVisitArrayNew(Expression*& out, uint32_t code) {
-  ArrayNew* curr;
-  switch (code) {
-    case BinaryConsts::ArrayNewWithRtt:
-      curr = allocator.alloc<ArrayNew>();
-      // ...
-      break;
-    case BinaryConsts::ArrayNewDefaultWithRtt:
-      curr = allocator.alloc<ArrayNew>();
-      // ...
-      break;
-    default:
-      return false;
+  if (code != BinaryConsts::ArrayNewWithRtt &&
+      code != BinaryConsts::ArrayNewDefaultWithRtt) {
+    return false;
   }
-  WASM_UNREACHABLE("TODO (gc): array.new");
-  curr->finalize();
-  out = curr;
+  auto heapType = getHeapType();
+  auto* rtt = popNonVoidExpression();
+  validateHeapTypeUsingChild(rtt, heapType);
+  auto* size = popNonVoidExpression();
+  Expression* init = nullptr;
+  if (code == BinaryConsts::ArrayNewWithRtt) {
+    init = popNonVoidExpression();
+  }
+  out = Builder(wasm).makeArrayNew(rtt, size, init);
   return true;
 }
 
 bool WasmBinaryBuilder::maybeVisitArrayGet(Expression*& out, uint32_t code) {
-  ArrayGet* curr;
+  bool signed_ = false;
   switch (code) {
     case BinaryConsts::ArrayGet:
-      curr = allocator.alloc<ArrayGet>();
-      // ...
+    case BinaryConsts::ArrayGetU:
       break;
     case BinaryConsts::ArrayGetS:
-      curr = allocator.alloc<ArrayGet>();
-      // ...
-      break;
-    case BinaryConsts::ArrayGetU:
-      curr = allocator.alloc<ArrayGet>();
-      // ...
+      signed_ = true;
       break;
     default:
       return false;
   }
-  WASM_UNREACHABLE("TODO (gc): array.get");
-  curr->finalize();
-  out = curr;
+  auto heapType = getHeapType();
+  auto* ref = popNonVoidExpression();
+  validateHeapTypeUsingChild(ref, heapType);
+  auto* index = popNonVoidExpression();
+  out = Builder(wasm).makeArrayGet(ref, index, signed_);
   return true;
 }
 
@@ -5765,10 +5751,12 @@ bool WasmBinaryBuilder::maybeVisitArraySet(Expression*& out, uint32_t code) {
   if (code != BinaryConsts::ArraySet) {
     return false;
   }
-  auto* curr = allocator.alloc<ArraySet>();
-  WASM_UNREACHABLE("TODO (gc): array.set");
-  curr->finalize();
-  out = curr;
+  auto heapType = getHeapType();
+  auto* ref = popNonVoidExpression();
+  validateHeapTypeUsingChild(ref, heapType);
+  auto* index = popNonVoidExpression();
+  auto* value = popNonVoidExpression();
+  out = Builder(wasm).makeArraySet(ref, index, value);
   return true;
 }
 
@@ -5776,10 +5764,10 @@ bool WasmBinaryBuilder::maybeVisitArrayLen(Expression*& out, uint32_t code) {
   if (code != BinaryConsts::ArrayLen) {
     return false;
   }
-  auto* curr = allocator.alloc<ArrayLen>();
-  WASM_UNREACHABLE("TODO (gc): array.len");
-  curr->finalize();
-  out = curr;
+  auto heapType = getHeapType();
+  auto* ref = popNonVoidExpression();
+  validateHeapTypeUsingChild(ref, heapType);
+  out = Builder(wasm).makeArrayLen(ref);
   return true;
 }
 
@@ -5787,4 +5775,16 @@ void WasmBinaryBuilder::throwError(std::string text) {
   throw ParseException(text, 0, pos);
 }
 
+void WasmBinaryBuilder::validateHeapTypeUsingChild(Expression* child,
+                                                   HeapType heapType) {
+  if (child->type == Type::unreachable) {
+    return;
+  }
+  if ((!child->type.isRef() && !child->type.isRtt()) ||
+      child->type.getHeapType() != heapType) {
+    throwError("bad heap type: expected " + heapType.toString() +
+               " but found " + child->type.toString());
+  }
+}
+
 } // namespace wasm
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 3bb54f0c8..b9f321b14 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -2126,11 +2126,7 @@ Expression* SExpressionWasmBuilder::makeRttSub(Element& s) {
 Expression* SExpressionWasmBuilder::makeStructNew(Element& s, bool default_) {
   auto heapType = parseHeapType(*s[1]);
   auto* rtt = parseExpression(*s[2]);
-  if (rtt->type != Type::unreachable) {
-    if (!rtt->type.isRtt() || rtt->type.getHeapType() != heapType) {
-      throw ParseException("bad struct.new heap type", s.line, s.col);
-    }
-  }
+  validateHeapTypeUsingChild(rtt, heapType, s);
   auto numOperands = s.size() - 3;
   if (default_ && numOperands > 0) {
     throw ParseException(
@@ -2161,54 +2157,57 @@ Index SExpressionWasmBuilder::getStructIndex(const HeapType& type, Element& s) {
 }
 
 Expression* SExpressionWasmBuilder::makeStructGet(Element& s, bool signed_) {
-  auto structType = parseHeapType(*s[1]);
-  auto index = getStructIndex(structType, *s[2]);
-  auto type = structType.getStruct().fields[index].type;
+  auto heapType = parseHeapType(*s[1]);
+  auto index = getStructIndex(heapType, *s[2]);
+  auto type = heapType.getStruct().fields[index].type;
   auto ref = parseExpression(*s[3]);
+  validateHeapTypeUsingChild(ref, heapType, s);
   return Builder(wasm).makeStructGet(index, ref, type, signed_);
 }
 
 Expression* SExpressionWasmBuilder::makeStructSet(Element& s) {
-  auto structType = parseHeapType(*s[1]);
-  auto index = getStructIndex(structType, *s[2]);
+  auto heapType = parseHeapType(*s[1]);
+  auto index = getStructIndex(heapType, *s[2]);
   auto ref = parseExpression(*s[3]);
+  validateHeapTypeUsingChild(ref, heapType, s);
   auto value = parseExpression(*s[4]);
   return Builder(wasm).makeStructSet(index, ref, value);
 }
 
 Expression* SExpressionWasmBuilder::makeArrayNew(Element& s, bool default_) {
-  auto ret = allocator.alloc<ArrayNew>();
-  WASM_UNREACHABLE("TODO (gc): array.new");
-  ret->finalize();
-  return ret;
-}
-
-Expression* SExpressionWasmBuilder::makeArrayGet(Element& s) {
-  auto ret = allocator.alloc<ArrayGet>();
-  WASM_UNREACHABLE("TODO (gc): array.get");
-  ret->finalize();
-  return ret;
+  auto heapType = parseHeapType(*s[1]);
+  auto* rtt = parseExpression(*s[2]);
+  validateHeapTypeUsingChild(rtt, heapType, s);
+  auto* size = parseExpression(*s[3]);
+  Expression* init = nullptr;
+  if (!default_) {
+    init = parseExpression(*s[4]);
+  }
+  return Builder(wasm).makeArrayNew(rtt, size, init);
 }
 
 Expression* SExpressionWasmBuilder::makeArrayGet(Element& s, bool signed_) {
-  auto ret = allocator.alloc<ArrayGet>();
-  WASM_UNREACHABLE("TODO (gc): array.get_s/u");
-  ret->finalize();
-  return ret;
+  auto heapType = parseHeapType(*s[1]);
+  auto ref = parseExpression(*s[2]);
+  validateHeapTypeUsingChild(ref, heapType, s);
+  auto index = parseExpression(*s[3]);
+  return Builder(wasm).makeArrayGet(ref, index, signed_);
 }
 
 Expression* SExpressionWasmBuilder::makeArraySet(Element& s) {
-  auto ret = allocator.alloc<ArraySet>();
-  WASM_UNREACHABLE("TODO (gc): array.set");
-  ret->finalize();
-  return ret;
+  auto heapType = parseHeapType(*s[1]);
+  auto ref = parseExpression(*s[2]);
+  validateHeapTypeUsingChild(ref, heapType, s);
+  auto index = parseExpression(*s[3]);
+  auto value = parseExpression(*s[4]);
+  return Builder(wasm).makeArraySet(ref, index, value);
 }
 
 Expression* SExpressionWasmBuilder::makeArrayLen(Element& s) {
-  auto ret = allocator.alloc<ArrayLen>();
-  WASM_UNREACHABLE("TODO (gc): array.len");
-  ret->finalize();
-  return ret;
+  auto heapType = parseHeapType(*s[1]);
+  auto ref = parseExpression(*s[2]);
+  validateHeapTypeUsingChild(ref, heapType, s);
+  return Builder(wasm).makeArrayLen(ref);
 }
 
 // converts an s-expression string representing binary data into an output
@@ -2969,4 +2968,19 @@ void SExpressionWasmBuilder::parseEvent(Element& s, bool preParseImport) {
   wasm.addEvent(event.release());
 }
 
+void SExpressionWasmBuilder::validateHeapTypeUsingChild(Expression* child,
+                                                        HeapType heapType,
+                                                        Element& s) {
+  if (child->type == Type::unreachable) {
+    return;
+  }
+  if ((!child->type.isRef() && !child->type.isRtt()) ||
+      child->type.getHeapType() != heapType) {
+    throw ParseException("bad heap type: expected " + heapType.toString() +
+                           " but found " + child->type.toString(),
+                         s.line,
+                         s.col);
+  }
+}
+
 } // namespace wasm
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index 2e4e9d332..60c352c5d 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -1928,33 +1928,50 @@ void BinaryInstWriter::visitStructGet(StructGet* curr) {
   } else {
     op = BinaryConsts::StructGetU;
   }
-  o << int8_t(BinaryConsts::GCPrefix) << int8_t(op);
+  o << int8_t(BinaryConsts::GCPrefix) << U32LEB(op);
   parent.writeHeapType(heapType);
   o << U32LEB(curr->index);
 }
 
 void BinaryInstWriter::visitStructSet(StructSet* curr) {
-  o << int8_t(BinaryConsts::GCPrefix) << int8_t(BinaryConsts::StructSet);
+  o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::StructSet);
   parent.writeHeapType(curr->ref->type.getHeapType());
   o << U32LEB(curr->index);
 }
 
 void BinaryInstWriter::visitArrayNew(ArrayNew* curr) {
-  WASM_UNREACHABLE("TODO (gc): array.new");
+  o << int8_t(BinaryConsts::GCPrefix);
+  if (curr->isWithDefault()) {
+    o << U32LEB(BinaryConsts::ArrayNewDefaultWithRtt);
+  } else {
+    o << U32LEB(BinaryConsts::ArrayNewWithRtt);
+  }
+  parent.writeHeapType(curr->rtt->type.getHeapType());
 }
 
 void BinaryInstWriter::visitArrayGet(ArrayGet* curr) {
-  WASM_UNREACHABLE("TODO (gc): array.get");
+  auto heapType = curr->ref->type.getHeapType();
+  const auto& field = heapType.getArray().element;
+  int8_t op;
+  if (field.type != Type::i32 || field.packedType == Field::not_packed) {
+    op = BinaryConsts::ArrayGet;
+  } else if (curr->signed_) {
+    op = BinaryConsts::ArrayGetS;
+  } else {
+    op = BinaryConsts::ArrayGetU;
+  }
+  o << int8_t(BinaryConsts::GCPrefix) << U32LEB(op);
+  parent.writeHeapType(heapType);
 }
 
 void BinaryInstWriter::visitArraySet(ArraySet* curr) {
   o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::ArraySet);
-  WASM_UNREACHABLE("TODO (gc): array.set");
+  parent.writeHeapType(curr->ref->type.getHeapType());
 }
 
 void BinaryInstWriter::visitArrayLen(ArrayLen* curr) {
   o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::ArrayLen);
-  WASM_UNREACHABLE("TODO (gc): array.len");
+  parent.writeHeapType(curr->ref->type.getHeapType());
 }
 
 void BinaryInstWriter::emitScopeEnd(Expression* curr) {
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 043796ff0..33a7e5b19 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -759,7 +759,7 @@ bool Field::operator<(const Field& other) const {
   if (mutable_ != other.mutable_) {
     return mutable_ < other.mutable_;
   }
-  if (type == Type::i32) {
+  if (type == Type::i32 && other.type == Type::i32) {
     return packedType < other.packedType;
   }
   return type < other.type;
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index e97541444..cf92cf4d3 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -2277,14 +2277,19 @@ void FunctionValidator::visitStructGet(StructGet* curr) {
   shouldBeTrue(getModule()->features.hasGC(),
                curr,
                "struct.get requires gc to be enabled");
-  if (curr->ref->type != Type::unreachable) {
-    const auto& fields = curr->ref->type.getHeapType().getStruct().fields;
-    shouldBeTrue(curr->index < fields.size(), curr, "bad struct.get field");
-    shouldBeEqual(curr->type,
-                  fields[curr->index].type,
-                  curr,
-                  "struct.get must have the proper type");
+  const auto& fields = curr->ref->type.getHeapType().getStruct().fields;
+  shouldBeTrue(curr->index < fields.size(), curr, "bad struct.get field");
+  auto field = fields[curr->index];
+  // If the type is not packed, it must be marked internally as unsigned, by
+  // convention.
+  if (field.type != Type::i32 || field.packedType == Field::not_packed) {
+    shouldBeFalse(curr->signed_, curr, "non-packed get cannot be signed");
+  }
+  if (curr->ref->type == Type::unreachable) {
+    return;
   }
+  shouldBeEqual(
+    curr->type, field.type, curr, "struct.get must have the proper type");
 }
 
 void FunctionValidator::visitStructSet(StructSet* curr) {
@@ -2304,25 +2309,77 @@ void FunctionValidator::visitStructSet(StructSet* curr) {
 void FunctionValidator::visitArrayNew(ArrayNew* curr) {
   shouldBeTrue(
     getModule()->features.hasGC(), curr, "array.new requires gc to be enabled");
-  WASM_UNREACHABLE("TODO (gc): array.new");
+  shouldBeEqualOrFirstIsUnreachable(
+    curr->size->type, Type(Type::i32), curr, "array.new size must be an i32");
+  if (curr->type == Type::unreachable) {
+    return;
+  }
+  if (!shouldBeTrue(
+        curr->rtt->type.isRtt(), curr, "array.new rtt must be rtt")) {
+    return;
+  }
+  auto heapType = curr->rtt->type.getHeapType();
+  if (!shouldBeTrue(
+        heapType.isArray(), curr, "array.new heap type must be array")) {
+    return;
+  }
+  const auto& element = heapType.getArray().element;
+  if (curr->isWithDefault()) {
+    shouldBeTrue(
+      !curr->init, curr, "array.new_with_default should have no init");
+    // The element must be defaultable.
+    // TODO: add type.isDefaultable()?
+    shouldBeTrue(!element.type.isRef() || element.type.isNullable(),
+                 element,
+                 "array.new_with_default value type must be defaultable");
+  } else {
+    shouldBeTrue(!!curr->init, curr, "array.new should have an init");
+    // The inits must have the proper type.
+    shouldBeSubType(curr->init->type,
+                    element.type,
+                    curr,
+                    "array.new init must have proper type");
+  }
 }
 
 void FunctionValidator::visitArrayGet(ArrayGet* curr) {
   shouldBeTrue(
     getModule()->features.hasGC(), curr, "array.get requires gc to be enabled");
-  WASM_UNREACHABLE("TODO (gc): array.get");
+  shouldBeEqualOrFirstIsUnreachable(
+    curr->index->type, Type(Type::i32), curr, "array.get index must be an i32");
+  const auto& element = curr->ref->type.getHeapType().getArray().element;
+  // If the type is not packed, it must be marked internally as unsigned, by
+  // convention.
+  if (element.type != Type::i32 || element.packedType == Field::not_packed) {
+    shouldBeFalse(curr->signed_, curr, "non-packed get cannot be signed");
+  }
+  if (curr->type == Type::unreachable) {
+    return;
+  }
+  shouldBeEqual(
+    curr->type, element.type, curr, "array.get must have the proper type");
 }
 
 void FunctionValidator::visitArraySet(ArraySet* curr) {
   shouldBeTrue(
     getModule()->features.hasGC(), curr, "array.set requires gc to be enabled");
-  WASM_UNREACHABLE("TODO (gc): array.set");
+  shouldBeEqualOrFirstIsUnreachable(
+    curr->index->type, Type(Type::i32), curr, "array.set index must be an i32");
+  if (curr->type == Type::unreachable) {
+    return;
+  }
+  const auto& element = curr->ref->type.getHeapType().getArray().element;
+  shouldBeEqual(curr->value->type,
+                element.type,
+                curr,
+                "array.set must have the proper type");
 }
 
 void FunctionValidator::visitArrayLen(ArrayLen* curr) {
   shouldBeTrue(
     getModule()->features.hasGC(), curr, "array.len requires gc to be enabled");
-  WASM_UNREACHABLE("TODO (gc): array.len");
+  shouldBeEqualOrFirstIsUnreachable(
+    curr->type, Type(Type::i32), curr, "array.len result must be an i32");
 }
 
 void FunctionValidator::visitFunction(Function* curr) {
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index 5954dd617..2eed06981 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -1104,7 +1104,8 @@ void StructNew::finalize() {
   if (handleUnreachableOperands(this)) {
     return;
   }
-  type = Type(rtt->type.getHeapType(), /* nullable = */ false);
+  // TODO: make non-nullable when we support that
+  type = Type(rtt->type.getHeapType(), /* nullable = */ true);
 }
 
 void StructGet::finalize() {
@@ -1123,10 +1124,40 @@ void StructSet::finalize() {
   }
 }
 
-// TODO (gc): array.new
-// TODO (gc): array.get
-// TODO (gc): array.set
-// TODO (gc): array.len
+void ArrayNew::finalize() {
+  if (rtt->type == Type::unreachable || size->type == Type::unreachable ||
+      (init && init->type == Type::unreachable)) {
+    type = Type::unreachable;
+    return;
+  }
+  // TODO: make non-nullable when we support that
+  type = Type(rtt->type.getHeapType(), /* nullable = */ true);
+}
+
+void ArrayGet::finalize() {
+  if (ref->type == Type::unreachable || index->type == Type::unreachable) {
+    type = Type::unreachable;
+  } else {
+    type = ref->type.getHeapType().getArray().element.type;
+  }
+}
+
+void ArraySet::finalize() {
+  if (ref->type == Type::unreachable || index->type == Type::unreachable ||
+      value->type == Type::unreachable) {
+    type = Type::unreachable;
+  } else {
+    type = Type::none;
+  }
+}
+
+void ArrayLen::finalize() {
+  if (ref->type == Type::unreachable) {
+    type = Type::unreachable;
+  } else {
+    type = Type::i32;
+  }
+}
 
 size_t Function::getNumParams() { return sig.params.size(); }