[Wasm GC] Add experimental array.copy (#3911)

Spec for it is here:

https://docs.google.com/document/d/1DklC3qVuOdLHSXB5UXghM_syCh-4cMinQ50ICiXnK3Q/edit#

Also reorder some things in wasm.h that were not in the canonical order (that has
no effect, but it is confusing to read).

20 files changed, 218 insertions, 7 deletions

diff --git a/src/gen-s-parser.inc b/src/gen-s-parser.inc
index 73e3cf861..7aba3faf1 100644
--- a/src/gen-s-parser.inc
+++ b/src/gen-s-parser.inc
@@ -11,6 +11,9 @@ switch (op[0]) {
     switch (op[1]) {
       case 'r': {
         switch (op[6]) {
+          case 'c':
+            if (strcmp(op, "array.copy") == 0) { return makeArrayCopy(s); }
+            goto parse_error;
           case 'g': {
             switch (op[9]) {
               case '\0':
diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index 5582172c3..1dcb55f61 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -165,6 +165,7 @@ void ReFinalize::visitArrayNew(ArrayNew* curr) { curr->finalize(); }
 void ReFinalize::visitArrayGet(ArrayGet* curr) { curr->finalize(); }
 void ReFinalize::visitArraySet(ArraySet* curr) { curr->finalize(); }
 void ReFinalize::visitArrayLen(ArrayLen* curr) { curr->finalize(); }
+void ReFinalize::visitArrayCopy(ArrayCopy* curr) { curr->finalize(); }
 void ReFinalize::visitRefAs(RefAs* curr) { curr->finalize(); }
 
 void ReFinalize::visitFunction(Function* curr) {
diff --git a/src/ir/cost.h b/src/ir/cost.h
index 5d01d2611..434d88d60 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -501,6 +501,7 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, Index> {
     return 6 + visit(curr->dest) + visit(curr->offset) + visit(curr->size);
   }
   Index visitMemoryCopy(MemoryCopy* curr) {
+    // TODO when the size is a constant, estimate the time based on that
     return 6 + visit(curr->dest) + visit(curr->source) + visit(curr->size);
   }
   Index visitMemoryFill(MemoryFill* curr) {
@@ -611,6 +612,11 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, Index> {
   Index visitArrayLen(ArrayLen* curr) {
     return 1 + nullCheckCost(curr->ref) + visit(curr->ref);
   }
+  Index visitArrayCopy(ArrayCopy* curr) {
+    // Similar to MemoryCopy.
+    return 6 + visit(curr->destRef) + visit(curr->destIndex) +
+           visit(curr->srcRef) + visit(curr->srcIndex) + visit(curr->length);
+  }
   Index visitRefAs(RefAs* curr) { return 1 + visit(curr->value); }
 
 private:
diff --git a/src/ir/effects.h b/src/ir/effects.h
index f9b6ca6fc..2de5c54f6 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -618,6 +618,10 @@ private:
         parent.implicitTrap = true;
       }
     }
+    void visitArrayCopy(ArrayCopy* curr) {
+      // traps when a ref is null, or when out of bounds.
+      parent.implicitTrap = true;
+    }
     void visitRefAs(RefAs* curr) {
       // traps when the arg is not valid
       if (curr->value->type.isNullable()) {
diff --git a/src/passes/OptimizeInstructions.cpp b/src/passes/OptimizeInstructions.cpp
index 310924327..d3c3f26f6 100644
--- a/src/passes/OptimizeInstructions.cpp
+++ b/src/passes/OptimizeInstructions.cpp
@@ -1064,6 +1064,11 @@ struct OptimizeInstructions
 
   void visitArrayLen(ArrayLen* curr) { skipNonNullCast(curr->ref); }
 
+  void visitArrayCopy(ArrayCopy* curr) {
+    skipNonNullCast(curr->destRef);
+    skipNonNullCast(curr->srcRef);
+  }
+
   void visitRefCast(RefCast* curr) {
     if (curr->type == Type::unreachable) {
       return;
diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index 3e2e7a64f..a832c9e85 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -96,6 +96,7 @@ public:
   Flow visitArrayNew(ArrayNew* curr) { return Flow(NONCONSTANT_FLOW); }
   Flow visitArrayGet(ArrayGet* curr) { return Flow(NONCONSTANT_FLOW); }
   Flow visitArrayLen(ArrayLen* curr) { return Flow(NONCONSTANT_FLOW); }
+  Flow visitArrayCopy(ArrayCopy* curr) { return Flow(NONCONSTANT_FLOW); }
 };
 
 struct Precompute
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 9f283ddcc..df408fdf3 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -2005,6 +2005,17 @@ struct PrintExpressionContents
     printMedium(o, "array.len ");
     TypeNamePrinter(o, wasm).print(curr->ref->type.getHeapType());
   }
+  void visitArrayCopy(ArrayCopy* curr) {
+    if (curr->srcRef->type == Type::unreachable ||
+        curr->destRef->type == Type::unreachable) {
+      printUnreachableReplacement();
+      return;
+    }
+    printMedium(o, "array.copy ");
+    TypeNamePrinter(o, wasm).print(curr->destRef->type.getHeapType());
+    o << ' ';
+    TypeNamePrinter(o, wasm).print(curr->srcRef->type.getHeapType());
+  }
   void visitRefAs(RefAs* curr) {
     switch (curr->op) {
       case RefAsNonNull:
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 6852c42ab..00c45ef60 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1051,6 +1051,7 @@ enum ASTNodes {
   ArrayGetU = 0x15,
   ArraySet = 0x16,
   ArrayLen = 0x17,
+  ArrayCopy = 0x18,
   I31New = 0x20,
   I31GetS = 0x21,
   I31GetU = 0x22,
@@ -1620,6 +1621,7 @@ public:
   bool maybeVisitArrayGet(Expression*& out, uint32_t code);
   bool maybeVisitArraySet(Expression*& out, uint32_t code);
   bool maybeVisitArrayLen(Expression*& out, uint32_t code);
+  bool maybeVisitArrayCopy(Expression*& out, uint32_t code);
   void visitSelect(Select* curr, uint8_t code);
   void visitReturn(Return* curr);
   void visitMemorySize(MemorySize* curr);
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index fabaac22a..a193dd8d5 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -854,6 +854,20 @@ public:
     ret->finalize();
     return ret;
   }
+  ArrayCopy* makeArrayCopy(Expression* destRef,
+                           Expression* destIndex,
+                           Expression* srcRef,
+                           Expression* srcIndex,
+                           Expression* length) {
+    auto* ret = wasm.allocator.alloc<ArrayCopy>();
+    ret->destRef = destRef;
+    ret->destIndex = destIndex;
+    ret->srcRef = srcRef;
+    ret->srcIndex = srcIndex;
+    ret->length = length;
+    ret->finalize();
+    return ret;
+  }
   RefAs* makeRefAs(RefAsOp op, Expression* value) {
     auto* ret = wasm.allocator.alloc<RefAs>();
     ret->op = op;
diff --git a/src/wasm-delegations-fields.h b/src/wasm-delegations-fields.h
index 16ef11193..e4b6c92e3 100644
--- a/src/wasm-delegations-fields.h
+++ b/src/wasm-delegations-fields.h
@@ -655,6 +655,16 @@ switch (DELEGATE_ID) {
     DELEGATE_END(ArrayLen);
     break;
   }
+  case Expression::Id::ArrayCopyId: {
+    DELEGATE_START(ArrayCopy);
+    DELEGATE_FIELD_CHILD(ArrayCopy, length);
+    DELEGATE_FIELD_CHILD(ArrayCopy, srcIndex);
+    DELEGATE_FIELD_CHILD(ArrayCopy, srcRef);
+    DELEGATE_FIELD_CHILD(ArrayCopy, destIndex);
+    DELEGATE_FIELD_CHILD(ArrayCopy, destRef);
+    DELEGATE_END(ArrayCopy);
+    break;
+  }
   case Expression::Id::RefAsId: {
     DELEGATE_START(RefAs);
     DELEGATE_FIELD_INT(RefAs, op);
diff --git a/src/wasm-delegations.h b/src/wasm-delegations.h
index b063c81be..358a04dcd 100644
--- a/src/wasm-delegations.h
+++ b/src/wasm-delegations.h
@@ -78,6 +78,7 @@ DELEGATE(ArrayNew);
 DELEGATE(ArrayGet);
 DELEGATE(ArraySet);
 DELEGATE(ArrayLen);
+DELEGATE(ArrayCopy);
 DELEGATE(RefAs);
 
 #undef DELEGATE
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index b38272acd..86d868ac8 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1618,6 +1618,13 @@ public:
       truncateForPacking(value.getSingleValue(), field);
     return Flow();
   }
+
+  // Arbitrary deterministic limit on size. If we need to allocate a Literals
+  // vector that takes around 1-2GB of memory then we are likely to hit memory
+  // limits on 32-bit machines, and in particular on wasm32 VMs that do not
+  // have 4GB support, so give up there.
+  static const Index ArrayLimit = (1 << 30) / sizeof(Literal);
+
   Flow visitArrayNew(ArrayNew* curr) {
     NOTE_ENTER("ArrayNew");
     auto rtt = this->visit(curr->rtt);
@@ -1630,11 +1637,7 @@ public:
     }
     const auto& element = curr->rtt->type.getHeapType().getArray().element;
     Index num = size.getSingleValue().geti32();
-    // Arbitrary deterministic limit on size. If we need to allocate a Literals
-    // vector that takes around 1-2GB of memory then we are likely to hit memory
-    // limits on 32-bit machines, and in particular on wasm32 VMs that do not
-    // have 4GB support, so give up there.
-    if (num >= (1 << 30) / sizeof(Literal)) {
+    if (num >= ArrayLimit) {
       hostLimit("allocation failure");
     }
     Literals data(num);
@@ -1715,6 +1718,58 @@ public:
     }
     return Literal(int32_t(data->values.size()));
   }
+  Flow visitArrayCopy(ArrayCopy* curr) {
+    NOTE_ENTER("ArrayCopy");
+    Flow destRef = this->visit(curr->destRef);
+    if (destRef.breaking()) {
+      return destRef;
+    }
+    Flow destIndex = this->visit(curr->destIndex);
+    if (destIndex.breaking()) {
+      return destIndex;
+    }
+    Flow srcRef = this->visit(curr->srcRef);
+    if (srcRef.breaking()) {
+      return srcRef;
+    }
+    Flow srcIndex = this->visit(curr->srcIndex);
+    if (srcIndex.breaking()) {
+      return srcIndex;
+    }
+    Flow length = this->visit(curr->length);
+    if (length.breaking()) {
+      return length;
+    }
+    auto destData = destRef.getSingleValue().getGCData();
+    if (!destData) {
+      trap("null ref");
+    }
+    auto srcData = srcRef.getSingleValue().getGCData();
+    if (!srcData) {
+      trap("null ref");
+    }
+    size_t destVal = destIndex.getSingleValue().getUnsigned();
+    size_t srcVal = srcIndex.getSingleValue().getUnsigned();
+    size_t lengthVal = length.getSingleValue().getUnsigned();
+    if (lengthVal >= ArrayLimit) {
+      hostLimit("allocation failure");
+    }
+    std::vector<Literal> copied;
+    copied.resize(lengthVal);
+    for (size_t i = 0; i < lengthVal; i++) {
+      if (srcVal + i >= srcData->values.size()) {
+        trap("oob");
+      }
+      copied[i] = srcData->values[srcVal + i];
+    }
+    for (size_t i = 0; i < lengthVal; i++) {
+      if (destVal + i >= destData->values.size()) {
+        trap("oob");
+      }
+      destData->values[destVal + i] = copied[i];
+    }
+    return Flow();
+  }
   Flow visitRefAs(RefAs* curr) {
     NOTE_ENTER("RefAs");
     Flow flow = visit(curr->value);
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index c65043d4c..d7d557da2 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -286,6 +286,7 @@ private:
   Expression* makeArrayGet(Element& s, bool signed_ = false);
   Expression* makeArraySet(Element& s);
   Expression* makeArrayLen(Element& s);
+  Expression* makeArrayCopy(Element& s);
   Expression* makeRefAs(Element& s, RefAsOp op);
 
   // Helper functions
diff --git a/src/wasm.h b/src/wasm.h
index 7e692bb96..baea1fabe 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -640,6 +640,7 @@ public:
     ArrayGetId,
     ArraySetId,
     ArrayLenId,
+    ArrayCopyId,
     RefAsId,
     NumExpressionIds
   };
@@ -1445,12 +1446,12 @@ class ArrayNew : public SpecificExpression<Expression::ArrayNewId> {
 public:
   ArrayNew(MixedArena& allocator) {}
 
-  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;
+  Expression* size;
+  Expression* rtt;
 
   bool isWithDefault() { return !init; }
 
@@ -1489,6 +1490,19 @@ public:
   void finalize();
 };
 
+class ArrayCopy : public SpecificExpression<Expression::ArrayCopyId> {
+public:
+  ArrayCopy(MixedArena& allocator) {}
+
+  Expression* destRef;
+  Expression* destIndex;
+  Expression* srcRef;
+  Expression* srcIndex;
+  Expression* length;
+
+  void finalize();
+};
+
 class RefAs : public SpecificExpression<Expression::RefAsId> {
 public:
   RefAs(MixedArena& allocator) {}
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 97dad88bb..12aa5f214 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -3547,6 +3547,9 @@ BinaryConsts::ASTNodes WasmBinaryBuilder::readExpression(Expression*& curr) {
       if (maybeVisitArrayLen(curr, opcode)) {
         break;
       }
+      if (maybeVisitArrayCopy(curr, opcode)) {
+        break;
+      }
       if (opcode == BinaryConsts::RefIsFunc ||
           opcode == BinaryConsts::RefIsData ||
           opcode == BinaryConsts::RefIsI31) {
@@ -6496,6 +6499,24 @@ bool WasmBinaryBuilder::maybeVisitArrayLen(Expression*& out, uint32_t code) {
   return true;
 }
 
+bool WasmBinaryBuilder::maybeVisitArrayCopy(Expression*& out, uint32_t code) {
+  if (code != BinaryConsts::ArrayCopy) {
+    return false;
+  }
+  auto destHeapType = getIndexedHeapType();
+  auto srcHeapType = getIndexedHeapType();
+  auto* length = popNonVoidExpression();
+  auto* srcIndex = popNonVoidExpression();
+  auto* srcRef = popNonVoidExpression();
+  auto* destIndex = popNonVoidExpression();
+  auto* destRef = popNonVoidExpression();
+  validateHeapTypeUsingChild(destRef, destHeapType);
+  validateHeapTypeUsingChild(srcRef, srcHeapType);
+  out =
+    Builder(wasm).makeArrayCopy(destRef, destIndex, srcRef, srcIndex, length);
+  return true;
+}
+
 void WasmBinaryBuilder::visitRefAs(RefAs* curr, uint8_t code) {
   BYN_TRACE("zz node: RefAs\n");
   switch (code) {
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 016858395..25db9a993 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -2687,6 +2687,20 @@ Expression* SExpressionWasmBuilder::makeArrayLen(Element& s) {
   return Builder(wasm).makeArrayLen(ref);
 }
 
+Expression* SExpressionWasmBuilder::makeArrayCopy(Element& s) {
+  auto destHeapType = parseHeapType(*s[1]);
+  auto srcHeapType = parseHeapType(*s[2]);
+  auto destRef = parseExpression(*s[3]);
+  validateHeapTypeUsingChild(destRef, destHeapType, s);
+  auto destIndex = parseExpression(*s[4]);
+  auto srcRef = parseExpression(*s[5]);
+  validateHeapTypeUsingChild(srcRef, srcHeapType, s);
+  auto srcIndex = parseExpression(*s[6]);
+  auto length = parseExpression(*s[7]);
+  return Builder(wasm).makeArrayCopy(
+    destRef, destIndex, srcRef, srcIndex, length);
+}
+
 Expression* SExpressionWasmBuilder::makeRefAs(Element& s, RefAsOp op) {
   return Builder(wasm).makeRefAs(op, parseExpression(s[1]));
 }
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index ab38d5275..12c999c0d 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -2049,6 +2049,12 @@ void BinaryInstWriter::visitArrayLen(ArrayLen* curr) {
   parent.writeIndexedHeapType(curr->ref->type.getHeapType());
 }
 
+void BinaryInstWriter::visitArrayCopy(ArrayCopy* curr) {
+  o << int8_t(BinaryConsts::GCPrefix) << U32LEB(BinaryConsts::ArrayCopy);
+  parent.writeIndexedHeapType(curr->destRef->type.getHeapType());
+  parent.writeIndexedHeapType(curr->srcRef->type.getHeapType());
+}
+
 void BinaryInstWriter::visitRefAs(RefAs* curr) {
   switch (curr->op) {
     case RefAsNonNull:
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index d82542668..10b60e0a7 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -385,6 +385,7 @@ public:
   void visitArrayGet(ArrayGet* curr);
   void visitArraySet(ArraySet* curr);
   void visitArrayLen(ArrayLen* curr);
+  void visitArrayCopy(ArrayCopy* curr);
   void visitFunction(Function* curr);
 
   // helpers
@@ -2457,6 +2458,31 @@ void FunctionValidator::visitArrayLen(ArrayLen* curr) {
     curr->type, Type(Type::i32), curr, "array.len result must be an i32");
 }
 
+void FunctionValidator::visitArrayCopy(ArrayCopy* curr) {
+  shouldBeTrue(getModule()->features.hasGC(),
+               curr,
+               "array.copy requires gc to be enabled");
+  shouldBeEqualOrFirstIsUnreachable(curr->srcIndex->type,
+                                    Type(Type::i32),
+                                    curr,
+                                    "array.copy src index must be an i32");
+  shouldBeEqualOrFirstIsUnreachable(curr->destIndex->type,
+                                    Type(Type::i32),
+                                    curr,
+                                    "array.copy dest index must be an i32");
+  if (curr->type == Type::unreachable) {
+    return;
+  }
+  const auto& srcElement = curr->srcRef->type.getHeapType().getArray().element;
+  const auto& destElement =
+    curr->destRef->type.getHeapType().getArray().element;
+  shouldBeSubType(srcElement.type,
+                  destElement.type,
+                  curr,
+                  "array.copy must have the proper types");
+  shouldBeTrue(destElement.mutable_, curr, "array.copy type must be mutable");
+}
+
 void FunctionValidator::visitFunction(Function* curr) {
   if (curr->sig.results.isTuple()) {
     shouldBeTrue(getModule()->features.hasMultivalue(),
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index 69464e73f..f0d130d6b 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -1018,6 +1018,18 @@ void ArrayLen::finalize() {
   }
 }
 
+void ArrayCopy::finalize() {
+  if (srcRef->type == Type::unreachable ||
+      srcIndex->type == Type::unreachable ||
+      destRef->type == Type::unreachable ||
+      destIndex->type == Type::unreachable ||
+      length->type == Type::unreachable) {
+    type = Type::unreachable;
+  } else {
+    type = Type::none;
+  }
+}
+
 void RefAs::finalize() {
   if (value->type == Type::unreachable) {
     type = Type::unreachable;
diff --git a/src/wasm2js.h b/src/wasm2js.h
index add543b47..268f3424f 100644
--- a/src/wasm2js.h
+++ b/src/wasm2js.h
@@ -2253,6 +2253,10 @@ Ref Wasm2JSBuilder::processFunctionBody(Module* m,
       unimplemented(curr);
       WASM_UNREACHABLE("unimp");
     }
+    Ref visitArrayCopy(ArrayCopy* curr) {
+      unimplemented(curr);
+      WASM_UNREACHABLE("unimp");
+    }
     Ref visitRefAs(RefAs* curr) {
       unimplemented(curr);
       WASM_UNREACHABLE("unimp");