[GC] Add struct.new and start to test interesting execution (#3433)

With struct.new read/write support, we can start to do interesting
things! This adds a test of creating a struct and seeing that references
behave like references, that is, if we write to the value X refers to, and
if Y refers to the same thing, when reading from Y's value we see the
change as well.

The test is run through all of -O1, which uncovered a minor issue in
Precompute: We can't try to precompute a reference type, as we can't
replace a reference with a value.

Note btw that the test shows the optimizer properly running
CoalesceLocals on reference types, merging two locals.

15 files changed, 172 insertions, 34 deletions

diff --git a/src/ir/cost.h b/src/ir/cost.h
index a006146d3..0c5a13819 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -571,7 +571,17 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, Index> {
     // TODO: investigate actual RTT costs in VMs
     return 2 + visit(curr->parent);
   }
-  Index visitStructNew(StructNew* curr) { WASM_UNREACHABLE("TODO: GC"); }
+  Index visitStructNew(StructNew* curr) {
+    // While allocation itself is almost free with generational GC, there is
+    // at least some baseline cost, plus writing the fields. (If we use default
+    // values for the fields, then it is possible they are all 0 and if so, we
+    // can get that almost for free as well, so don't add anything there.)
+    Index ret = 4 + visit(curr->rtt) + curr->operands.size();
+    for (auto* child : curr->operands) {
+      ret += visit(child);
+    }
+    return ret;
+  }
   Index visitStructGet(StructGet* curr) {
     return 1 + nullCheckCost(curr->ref) + visit(curr->ref);
   }
diff --git a/src/ir/effects.h b/src/ir/effects.h
index 39d0d265a..e4907b082 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -557,7 +557,6 @@ private:
     void visitRttCanon(RttCanon* curr) {}
     void visitRttSub(RttSub* curr) {}
     void visitStructNew(StructNew* curr) {
-      WASM_UNREACHABLE("TODO (gc): struct.new");
     }
     void visitStructGet(StructGet* curr) {
       // traps when the arg is null
diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index c82a880b1..bf5924720 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -168,6 +168,11 @@ struct Precompute
     if (curr->type.isVector()) {
       return;
     }
+    // Don't try to precompute a reference. We can't replace it with a constant
+    // expression, as that would make a copy of it by value.
+    if (curr->type.isRef()) {
+      return;
+    }
     // try to evaluate this into a const
     Flow flow = precomputeExpression(curr);
     if (flow.getType().hasVector()) {
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 2edd069d9..5c2acf3f0 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -1702,7 +1702,12 @@ struct PrintExpressionContents
     printHeapTypeName(o, curr->type.getRtt().heapType);
   }
   void visitStructNew(StructNew* curr) {
-    WASM_UNREACHABLE("TODO (gc): struct.new");
+    printMedium(o, "struct.new_");
+    if (curr->isWithDefault()) {
+      o << "default_";
+    }
+    o << "with_rtt ";
+    printHeapTypeName(o, curr->rtt->type.getRtt().heapType);
   }
   void visitStructGet(StructGet* curr) {
     const auto& field =
@@ -2391,7 +2396,12 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
   void visitStructNew(StructNew* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
-    WASM_UNREACHABLE("TODO (gc): struct.new");
+    incIndent();
+    printFullLine(curr->rtt);
+    for (auto& operand : curr->operands) {
+      printFullLine(operand);
+    }
+    decIndent();
   }
   void visitStructGet(StructGet* curr) {
     o << '(';
diff --git a/src/support/small_vector.h b/src/support/small_vector.h
index 5791a0398..baf217086 100644
--- a/src/support/small_vector.h
+++ b/src/support/small_vector.h
@@ -111,6 +111,13 @@ public:
     flexible.clear();
   }
 
+  void resize(size_t newSize) {
+    usedFixed = std::min(N, newSize);
+    if (newSize > N) {
+      flexible.resize(newSize - N);
+    }
+  }
+
   bool operator==(const SmallVector<T, N>& other) const {
     if (usedFixed != other.usedFixed) {
       return false;
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 5cca8d959..213edbef5 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -727,9 +727,11 @@ public:
     ret->finalize();
     return ret;
   }
-  StructNew* makeStructNew() {
+  template<typename T>
+  StructNew* makeStructNew(Expression* rtt, const T& args) {
     auto* ret = wasm.allocator.alloc<StructNew>();
-    WASM_UNREACHABLE("TODO (gc): struct.new");
+    ret->rtt = rtt;
+    ret->operands.set(args);
     ret->finalize();
     return ret;
   }
diff --git a/src/wasm-delegations-fields.h b/src/wasm-delegations-fields.h
index 4e23a6530..fa93710ab 100644
--- a/src/wasm-delegations-fields.h
+++ b/src/wasm-delegations-fields.h
@@ -588,7 +588,8 @@ switch (DELEGATE_ID) {
   }
   case Expression::Id::StructNewId: {
     DELEGATE_START(StructNew);
-    WASM_UNREACHABLE("TODO (gc): struct.new");
+    DELEGATE_FIELD_CHILD(StructNew, rtt);
+    DELEGATE_FIELD_CHILD_VECTOR(StructNew, operands);
     DELEGATE_END(StructNew);
     break;
   }
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 65a4417c8..bf02b7987 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1398,7 +1398,26 @@ public:
   }
   Flow visitStructNew(StructNew* curr) {
     NOTE_ENTER("StructNew");
-    WASM_UNREACHABLE("TODO (gc): struct.new");
+    auto rtt = this->visit(curr->rtt);
+    if (rtt.breaking()) {
+      return rtt;
+    }
+    const auto& fields = curr->rtt->type.getHeapType().getStruct().fields;
+    Literals data;
+    data.resize(fields.size());
+    for (Index i = 0; i < fields.size(); i++) {
+      if (curr->isWithDefault()) {
+        data[i] = Literal::makeZero(fields[i].type);
+      } else {
+        auto value = this->visit(curr->operands[i]);
+        if (value.breaking()) {
+          return value;
+        }
+        data[i] = value.getSingleValue();
+      }
+    }
+    return Flow(
+      Literal(std::shared_ptr<Literals>(new Literals(data)), curr->type));
   }
   Flow visitStructGet(StructGet* curr) {
     NOTE_ENTER("StructGet");
diff --git a/src/wasm.h b/src/wasm.h
index c1936cb46..0ea3ffeb7 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -1345,9 +1345,17 @@ public:
 
 class StructNew : public SpecificExpression<Expression::StructNewId> {
 public:
-  StructNew(MixedArena& allocator) {}
+  StructNew(MixedArena& allocator) : operands(allocator) {}
 
-  void finalize() { WASM_UNREACHABLE("TODO (gc): struct.new"); }
+  Expression* rtt;
+  // A struct.new_with_default has empty operands. This does leave the case of a
+  // struct with no fields ambiguous, but it doesn't make a difference in that
+  // case, and binaryen doesn't guarantee roundtripping binaries anyhow.
+  ExpressionList operands;
+
+  bool isWithDefault() { return operands.empty(); }
+
+  void finalize();
 };
 
 class StructGet : public SpecificExpression<Expression::StructGetId> {
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 20edab3cf..314364f38 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -5612,22 +5612,29 @@ bool WasmBinaryBuilder::maybeVisitRttSub(Expression*& out, uint32_t code) {
 }
 
 bool WasmBinaryBuilder::maybeVisitStructNew(Expression*& out, uint32_t code) {
-  StructNew* curr;
-  switch (code) {
-    case BinaryConsts::StructNewWithRtt:
-      curr = allocator.alloc<StructNew>();
-      // ...
-      break;
-    case BinaryConsts::StructNewDefaultWithRtt:
-      curr = allocator.alloc<StructNew>();
-      // ...
-      break;
-    default:
-      return false;
+  if (code != BinaryConsts::StructNewWithRtt &&
+      code != BinaryConsts::StructNewDefaultWithRtt) {
+    return false;
   }
-  WASM_UNREACHABLE("TODO (gc): struct.new");
-  curr->finalize();
-  out = curr;
+  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");
+    }
+  }
+  std::vector<Expression*> operands;
+  if (code == BinaryConsts::StructNewWithRtt) {
+    auto numOperands = heapType.getStruct().fields.size();
+    operands.resize(numOperands);
+    for (Index i = 0; i < numOperands; i++) {
+      operands[numOperands - i - 1] = popNonVoidExpression();
+    }
+  }
+  out = Builder(wasm).makeStructNew(rtt, operands);
   return true;
 }
 
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 63b6e34bd..7efb2f2fb 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -2124,10 +2124,24 @@ Expression* SExpressionWasmBuilder::makeRttSub(Element& s) {
 }
 
 Expression* SExpressionWasmBuilder::makeStructNew(Element& s, bool default_) {
-  auto ret = allocator.alloc<StructNew>();
-  WASM_UNREACHABLE("TODO (gc): struct.new");
-  ret->finalize();
-  return ret;
+  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);
+    }
+  }
+  auto numOperands = s.size() - 3;
+  if (default_ && numOperands > 0) {
+    throw ParseException(
+      "arguments provided for struct.new_with_default", s.line, s.col);
+  }
+  std::vector<Expression*> operands;
+  operands.resize(numOperands);
+  for (Index i = 0; i < numOperands; i++) {
+    operands[i] = parseExpression(*s[i + 3]);
+  }
+  return Builder(wasm).makeStructNew(rtt, operands);
 }
 
 Index SExpressionWasmBuilder::getStructIndex(const HeapType& type, Element& s) {
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index cca351b6f..2e4e9d332 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -1908,7 +1908,13 @@ void BinaryInstWriter::visitRttSub(RttSub* curr) {
 }
 
 void BinaryInstWriter::visitStructNew(StructNew* curr) {
-  WASM_UNREACHABLE("TODO (gc): struct.new");
+  o << int8_t(BinaryConsts::GCPrefix);
+  if (curr->isWithDefault()) {
+    o << U32LEB(BinaryConsts::StructNewDefaultWithRtt);
+  } else {
+    o << U32LEB(BinaryConsts::StructNewWithRtt);
+  }
+  parent.writeHeapType(curr->rtt->type.getHeapType());
 }
 
 void BinaryInstWriter::visitStructGet(StructGet* curr) {
diff --git a/src/wasm/wasm-type.cpp b/src/wasm/wasm-type.cpp
index 013dadcf4..a27cbabc6 100644
--- a/src/wasm/wasm-type.cpp
+++ b/src/wasm/wasm-type.cpp
@@ -577,6 +577,12 @@ bool Type::isSubType(Type left, Type right) {
     if (left.getHeapType().isSignature() && right == Type::funcref) {
       return true;
     }
+    // A non-nullable type is a supertype of a nullable one
+    if (left.getHeapType() == right.getHeapType() && !left.isNullable()) {
+      // The only difference is the nullability.
+      assert(right.isNullable());
+      return true;
+    }
     return false;
   }
   if (left.isTuple() && right.isTuple()) {
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index c6e22899c..e97541444 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -2238,7 +2238,39 @@ void FunctionValidator::visitStructNew(StructNew* curr) {
   shouldBeTrue(getModule()->features.hasGC(),
                curr,
                "struct.new requires gc to be enabled");
-  WASM_UNREACHABLE("TODO (gc): struct.new");
+  if (curr->type == Type::unreachable) {
+    return;
+  }
+  if (!shouldBeTrue(
+        curr->rtt->type.isRtt(), curr, "struct.new rtt must be rtt")) {
+    return;
+  }
+  auto heapType = curr->rtt->type.getHeapType();
+  if (!shouldBeTrue(
+        heapType.isStruct(), curr, "struct.new heap type must be struct")) {
+    return;
+  }
+  const auto& fields = heapType.getStruct().fields;
+  if (curr->isWithDefault()) {
+    shouldBeTrue(curr->operands.empty(),
+                 curr,
+                 "struct.new_with_default should have no operands");
+    // All the fields must be defaultable.
+    for (const auto& field : fields) {
+      // TODO: add type.isDefaultable()?
+      shouldBeTrue(!field.type.isRef() || field.type.isNullable(),
+                   field,
+                   "struct.new_with_default value type must be defaultable");
+    }
+  } else {
+    // All the fields must have the proper type.
+    for (Index i = 0; i < fields.size(); i++) {
+      shouldBeSubType(curr->operands[i]->type,
+                      fields[i].type,
+                      curr,
+                      "struct.new operand must have proper type");
+    }
+  }
 }
 
 void FunctionValidator::visitStructGet(StructGet* curr) {
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index 1e8bf93ae..5954dd617 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -463,13 +463,16 @@ void Break::finalize() {
 
 void Switch::finalize() { type = Type::unreachable; }
 
-template<typename T> void handleUnreachableOperands(T* curr) {
+// Sets the type to unreachable if there is an unreachable operand. Returns true
+// if so.
+template<typename T> bool handleUnreachableOperands(T* curr) {
   for (auto* child : curr->operands) {
     if (child->type == Type::unreachable) {
       curr->type = Type::unreachable;
-      break;
+      return true;
     }
   }
+  return false;
 }
 
 void Call::finalize() {
@@ -1093,7 +1096,16 @@ void RttSub::finalize() {
   // construction.
 }
 
-// TODO (gc): struct.new
+void StructNew::finalize() {
+  if (rtt->type == Type::unreachable) {
+    type = Type::unreachable;
+    return;
+  }
+  if (handleUnreachableOperands(this)) {
+    return;
+  }
+  type = Type(rtt->type.getHeapType(), /* nullable = */ false);
+}
 
 void StructGet::finalize() {
   if (ref->type == Type::unreachable) {