Implement table.fill (#5949)

This instruction was standardized as part of the bulk memory proposal, but we
never implemented it until now. Leave similar instructions like table.copy as
future work.

Fixes #5939.

21 files changed, 175 insertions, 0 deletions

diff --git a/src/gen-s-parser.inc b/src/gen-s-parser.inc
index 506ec62ad..416349032 100644
--- a/src/gen-s-parser.inc
+++ b/src/gen-s-parser.inc
@@ -3357,6 +3357,9 @@ switch (buf[0]) {
     switch (buf[1]) {
       case 'a': {
         switch (buf[6]) {
+          case 'f':
+            if (op == "table.fill"sv) { return makeTableFill(s); }
+            goto parse_error;
           case 'g': {
             switch (buf[7]) {
               case 'e':
@@ -9190,6 +9193,13 @@ switch (buf[0]) {
     switch (buf[1]) {
       case 'a': {
         switch (buf[6]) {
+          case 'f':
+            if (op == "table.fill"sv) {
+              auto ret = makeTableFill(ctx, pos);
+              CHECK_ERR(ret);
+              return *ret;
+            }
+            goto parse_error;
           case 'g': {
             switch (buf[7]) {
               case 'e':
diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index b0dea7627..bfdcfe7a6 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -124,6 +124,7 @@ void ReFinalize::visitTableGet(TableGet* curr) { curr->finalize(); }
 void ReFinalize::visitTableSet(TableSet* curr) { curr->finalize(); }
 void ReFinalize::visitTableSize(TableSize* curr) { curr->finalize(); }
 void ReFinalize::visitTableGrow(TableGrow* curr) { curr->finalize(); }
+void ReFinalize::visitTableFill(TableFill* curr) { curr->finalize(); }
 void ReFinalize::visitTry(Try* curr) { curr->finalize(); }
 void ReFinalize::visitThrow(Throw* curr) { curr->finalize(); }
 void ReFinalize::visitRethrow(Rethrow* curr) { curr->finalize(); }
diff --git a/src/ir/cost.h b/src/ir/cost.h
index e7287de77..73d027788 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -574,6 +574,9 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, CostType> {
   CostType visitTableGrow(TableGrow* curr) {
     return Unacceptable + visit(curr->value) + visit(curr->delta);
   }
+  CostType visitTableFill(TableFill* curr) {
+    return 6 + visit(curr->dest) + visit(curr->value) + visit(curr->size);
+  }
   CostType visitTry(Try* curr) {
     // We assume no exception will be thrown in most cases
     return visit(curr->body);
diff --git a/src/ir/effects.h b/src/ir/effects.h
index 171a17803..9bdf08c74 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -692,6 +692,10 @@ private:
       parent.readsTable = true;
       parent.writesTable = true;
     }
+    void visitTableFill(TableFill* curr) {
+      parent.writesTable = true;
+      parent.implicitTrap = true;
+    }
     void visitTry(Try* curr) {
       if (curr->delegateTarget.is()) {
         parent.delegateTargets.insert(curr->delegateTarget);
diff --git a/src/ir/possible-contents.cpp b/src/ir/possible-contents.cpp
index b23d8220a..27ba8c759 100644
--- a/src/ir/possible-contents.cpp
+++ b/src/ir/possible-contents.cpp
@@ -661,6 +661,7 @@ struct InfoCollector
   void visitTableSet(TableSet* curr) {}
   void visitTableSize(TableSize* curr) { addRoot(curr); }
   void visitTableGrow(TableGrow* curr) { addRoot(curr); }
+  void visitTableFill(TableFill* curr) { addRoot(curr); }
 
   void visitNop(Nop* curr) {}
   void visitUnreachable(Unreachable* curr) {}
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index c47f33944..a21fd79dc 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -1925,6 +1925,10 @@ struct PrintExpressionContents
     printMedium(o, "table.grow ");
     printName(curr->table, o);
   }
+  void visitTableFill(TableFill* curr) {
+    printMedium(o, "table.fill ");
+    printName(curr->table, o);
+  }
   void visitTry(Try* curr) {
     printMedium(o, "try");
     if (curr->name.is()) {
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index 8c8ae70e6..72b61223f 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1129,6 +1129,7 @@ enum ASTNodes {
 
   TableGrow = 0x0f,
   TableSize = 0x10,
+  TableFill = 0x11,
   RefNull = 0xd0,
   RefIsNull = 0xd1,
   RefFunc = 0xd2,
@@ -1838,6 +1839,7 @@ public:
   bool maybeVisitMemoryFill(Expression*& out, uint32_t code);
   bool maybeVisitTableSize(Expression*& out, uint32_t code);
   bool maybeVisitTableGrow(Expression*& out, uint32_t code);
+  bool maybeVisitTableFill(Expression*& out, uint32_t code);
   bool maybeVisitRefI31(Expression*& out, uint32_t code);
   bool maybeVisitI31Get(Expression*& out, uint32_t code);
   bool maybeVisitRefTest(Expression*& out, uint32_t code);
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index b9db66983..9a59b4015 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -759,6 +759,18 @@ public:
     ret->finalize();
     return ret;
   }
+  TableFill* makeTableFill(Name table,
+                           Expression* dest,
+                           Expression* value,
+                           Expression* size) {
+    auto* ret = wasm.allocator.alloc<TableFill>();
+    ret->table = table;
+    ret->dest = dest;
+    ret->value = value;
+    ret->size = size;
+    ret->finalize();
+    return ret;
+  }
 
 private:
   Try* makeTry(Name name,
diff --git a/src/wasm-delegations-fields.def b/src/wasm-delegations-fields.def
index 43cb28325..3ab112bdd 100644
--- a/src/wasm-delegations-fields.def
+++ b/src/wasm-delegations-fields.def
@@ -567,6 +567,15 @@ switch (DELEGATE_ID) {
     DELEGATE_END(TableGrow);
     break;
   }
+  case Expression::Id::TableFillId: {
+    DELEGATE_START(TableFill);
+    DELEGATE_FIELD_CHILD(TableFill, size);
+    DELEGATE_FIELD_CHILD(TableFill, value);
+    DELEGATE_FIELD_CHILD(TableFill, dest);
+    DELEGATE_FIELD_NAME_KIND(TableFill, table, ModuleItemKind::Table);
+    DELEGATE_END(TableFill);
+    break;
+  }
   case Expression::Id::TryId: {
     DELEGATE_START(Try);
     DELEGATE_FIELD_SCOPE_NAME_USE(Try, delegateTarget);
diff --git a/src/wasm-delegations.def b/src/wasm-delegations.def
index e6aa865ec..a9c9c3f75 100644
--- a/src/wasm-delegations.def
+++ b/src/wasm-delegations.def
@@ -62,6 +62,7 @@ DELEGATE(TableGet);
 DELEGATE(TableSet);
 DELEGATE(TableSize);
 DELEGATE(TableGrow);
+DELEGATE(TableFill);
 DELEGATE(Try);
 DELEGATE(Throw);
 DELEGATE(Rethrow);
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 1d8c60883..3b451a787 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1391,6 +1391,7 @@ public:
   Flow visitTableSet(TableSet* curr) { WASM_UNREACHABLE("unimp"); }
   Flow visitTableSize(TableSize* curr) { WASM_UNREACHABLE("unimp"); }
   Flow visitTableGrow(TableGrow* curr) { WASM_UNREACHABLE("unimp"); }
+  Flow visitTableFill(TableFill* curr) { WASM_UNREACHABLE("unimp"); }
   Flow visitTry(Try* curr) { WASM_UNREACHABLE("unimp"); }
   Flow visitThrow(Throw* curr) {
     NOTE_ENTER("Throw");
@@ -2205,6 +2206,10 @@ public:
     NOTE_ENTER("TableGrow");
     return Flow(NONCONSTANT_FLOW);
   }
+  Flow visitTableFill(TableFill* curr) {
+    NOTE_ENTER("TableFill");
+    return Flow(NONCONSTANT_FLOW);
+  }
   Flow visitLoad(Load* curr) {
     NOTE_ENTER("Load");
     return Flow(NONCONSTANT_FLOW);
@@ -2989,6 +2994,38 @@ public:
     return ret;
   }
 
+  Flow visitTableFill(TableFill* curr) {
+    NOTE_ENTER("TableFill");
+    Flow destFlow = self()->visit(curr->dest);
+    if (destFlow.breaking()) {
+      return destFlow;
+    }
+    Flow valueFlow = self()->visit(curr->value);
+    if (valueFlow.breaking()) {
+      return valueFlow;
+    }
+    Flow sizeFlow = self()->visit(curr->size);
+    if (sizeFlow.breaking()) {
+      return sizeFlow;
+    }
+    Name tableName = curr->table;
+    auto info = getTableInterfaceInfo(tableName);
+
+    Index dest = destFlow.getSingleValue().geti32();
+    Literal value = valueFlow.getSingleValue();
+    Index size = sizeFlow.getSingleValue().geti32();
+
+    Index tableSize = info.interface->tableSize(tableName);
+    if (dest + size > tableSize) {
+      trap("out of bounds table access");
+    }
+
+    for (Index i = 0; i < size; ++i) {
+      info.interface->tableStore(info.name, dest + i, value);
+    }
+    return Flow();
+  }
+
   Flow visitLocalGet(LocalGet* curr) {
     NOTE_ENTER("LocalGet");
     auto index = curr->index;
diff --git a/src/wasm-ir-builder.h b/src/wasm-ir-builder.h
index 6c85a2f37..50c034897 100644
--- a/src/wasm-ir-builder.h
+++ b/src/wasm-ir-builder.h
@@ -125,6 +125,7 @@ public:
   // [[nodiscard]] Result<> makeTableSet();
   // [[nodiscard]] Result<> makeTableSize();
   // [[nodiscard]] Result<> makeTableGrow();
+  // [[nodiscard]] Result<> makeTableFill();
   // [[nodiscard]] Result<> makeTry();
   // [[nodiscard]] Result<> makeThrow();
   // [[nodiscard]] Result<> makeRethrow();
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index ad2d83e64..4c49a7773 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -278,6 +278,7 @@ private:
   Expression* makeTableSet(Element& s);
   Expression* makeTableSize(Element& s);
   Expression* makeTableGrow(Element& s);
+  Expression* makeTableFill(Element& s);
   Expression* makeTry(Element& s);
   Expression* makeTryOrCatchBody(Element& s, Type type, bool isTry);
   Expression* makeThrow(Element& s);
diff --git a/src/wasm.h b/src/wasm.h
index ab40d5330..1792b1538 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -698,6 +698,7 @@ public:
     TableSetId,
     TableSizeId,
     TableGrowId,
+    TableFillId,
     TryId,
     ThrowId,
     RethrowId,
@@ -1421,6 +1422,19 @@ public:
   void finalize();
 };
 
+class TableFill : public SpecificExpression<Expression::TableFillId> {
+public:
+  TableFill() = default;
+  TableFill(MixedArena& allocator) : TableFill() {}
+
+  Name table;
+  Expression* dest;
+  Expression* value;
+  Expression* size;
+
+  void finalize();
+};
+
 class Try : public SpecificExpression<Expression::TryId> {
 public:
   Try(MixedArena& allocator) : catchTags(allocator), catchBodies(allocator) {}
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index 969c15aaa..0c78442a7 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -4012,6 +4012,9 @@ BinaryConsts::ASTNodes WasmBinaryReader::readExpression(Expression*& curr) {
       if (maybeVisitTableGrow(curr, opcode)) {
         break;
       }
+      if (maybeVisitTableFill(curr, opcode)) {
+        break;
+      }
       throwError("invalid code after misc prefix: " + std::to_string(opcode));
       break;
     }
@@ -5369,6 +5372,23 @@ bool WasmBinaryReader::maybeVisitTableGrow(Expression*& out, uint32_t code) {
   return true;
 }
 
+bool WasmBinaryReader::maybeVisitTableFill(Expression*& out, uint32_t code) {
+  if (code != BinaryConsts::TableFill) {
+    return false;
+  }
+  Index tableIdx = getU32LEB();
+  if (tableIdx >= wasm.tables.size()) {
+    throwError("bad table index");
+  }
+  auto* size = popNonVoidExpression();
+  auto* value = popNonVoidExpression();
+  auto* dest = popNonVoidExpression();
+  auto* ret = Builder(wasm).makeTableFill(Name(), dest, value, size);
+  tableRefs[tableIdx].push_back(&ret->table);
+  out = ret;
+  return true;
+}
+
 bool WasmBinaryReader::maybeVisitBinary(Expression*& out, uint8_t code) {
   Binary* curr;
 #define INT_TYPED_CODE(code)                                                   \
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 7da6ae0a5..dec9249c3 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -2641,6 +2641,18 @@ Expression* SExpressionWasmBuilder::makeTableGrow(Element& s) {
   return Builder(wasm).makeTableGrow(tableName, value, delta);
 }
 
+Expression* SExpressionWasmBuilder::makeTableFill(Element& s) {
+  auto tableName = s[1]->str();
+  auto* table = wasm.getTableOrNull(tableName);
+  if (!table) {
+    throw ParseException("invalid table name in table.fill", s.line, s.col);
+  }
+  auto* dest = parseExpression(s[2]);
+  auto* value = parseExpression(s[3]);
+  auto* size = parseExpression(s[4]);
+  return Builder(wasm).makeTableFill(tableName, dest, value, size);
+}
+
 // try can be either in the form of try-catch or try-delegate.
 // try-catch is written in the folded wast format as
 // (try
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index 1ddf69d41..2042189fd 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -1909,6 +1909,11 @@ void BinaryInstWriter::visitTableGrow(TableGrow* curr) {
   o << U32LEB(parent.getTableIndex(curr->table));
 }
 
+void BinaryInstWriter::visitTableFill(TableFill* curr) {
+  o << int8_t(BinaryConsts::MiscPrefix) << U32LEB(BinaryConsts::TableFill);
+  o << U32LEB(parent.getTableIndex(curr->table));
+}
+
 void BinaryInstWriter::visitTry(Try* curr) {
   breakStack.push_back(curr->name);
   o << int8_t(BinaryConsts::Try);
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index c1836a7ff..41ddd00f5 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -440,6 +440,7 @@ public:
   void visitTableSet(TableSet* curr);
   void visitTableSize(TableSize* curr);
   void visitTableGrow(TableGrow* curr);
+  void visitTableFill(TableFill* curr);
   void noteDelegate(Name name, Expression* curr);
   void noteRethrow(Name name, Expression* curr);
   void visitTry(Try* curr);
@@ -2294,6 +2295,24 @@ void FunctionValidator::visitTableGrow(TableGrow* curr) {
   }
 }
 
+void FunctionValidator::visitTableFill(TableFill* curr) {
+  shouldBeTrue(
+    getModule()->features.hasBulkMemory(),
+    curr,
+    "table.fill requires reference types [--enable-reference-types]");
+  auto* table = getModule()->getTableOrNull(curr->table);
+  if (shouldBeTrue(!!table, curr, "table.fill table must exist")) {
+    shouldBeSubType(curr->value->type,
+                    table->type,
+                    curr,
+                    "table.fill value must have right type");
+  }
+  shouldBeEqualOrFirstIsUnreachable(
+    curr->dest->type, Type(Type::i32), curr, "table.fill dest must be i32");
+  shouldBeEqualOrFirstIsUnreachable(
+    curr->size->type, Type(Type::i32), curr, "table.fill size must be i32");
+}
+
 void FunctionValidator::noteDelegate(Name name, Expression* curr) {
   if (name != DELEGATE_CALLER_TARGET) {
     shouldBeTrue(delegateTargetNames.count(name) != 0,
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index ca7e265f8..52a09e90c 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -855,6 +855,15 @@ void TableGrow::finalize() {
   }
 }
 
+void TableFill::finalize() {
+  if (dest->type == Type::unreachable || value->type == Type::unreachable ||
+      size->type == Type::unreachable) {
+    type = Type::unreachable;
+  } else {
+    type = Type::none;
+  }
+}
+
 void Try::finalize() {
   // If none of the component bodies' type is a supertype of the others, assume
   // the current type is already correct. TODO: Calculate a proper LUB.
diff --git a/src/wasm/wat-parser.cpp b/src/wasm/wat-parser.cpp
index 6a18b2f87..b31019811 100644
--- a/src/wasm/wat-parser.cpp
+++ b/src/wasm/wat-parser.cpp
@@ -1936,6 +1936,7 @@ template<typename Ctx> Result<typename Ctx::InstrT> makeTableGet(Ctx&, Index);
 template<typename Ctx> Result<typename Ctx::InstrT> makeTableSet(Ctx&, Index);
 template<typename Ctx> Result<typename Ctx::InstrT> makeTableSize(Ctx&, Index);
 template<typename Ctx> Result<typename Ctx::InstrT> makeTableGrow(Ctx&, Index);
+template<typename Ctx> Result<typename Ctx::InstrT> makeTableFill(Ctx&, Index);
 template<typename Ctx> Result<typename Ctx::InstrT> makeTry(Ctx&, Index);
 template<typename Ctx>
 Result<typename Ctx::InstrT>
@@ -3006,6 +3007,11 @@ Result<typename Ctx::InstrT> makeTableGrow(Ctx& ctx, Index pos) {
 }
 
 template<typename Ctx>
+Result<typename Ctx::InstrT> makeTableFill(Ctx& ctx, Index pos) {
+  return ctx.in.err("unimplemented instruction");
+}
+
+template<typename Ctx>
 Result<typename Ctx::InstrT> makeTry(Ctx& ctx, Index pos) {
   return ctx.in.err("unimplemented instruction");
 }
diff --git a/src/wasm2js.h b/src/wasm2js.h
index 2fbde5b65..e9090d756 100644
--- a/src/wasm2js.h
+++ b/src/wasm2js.h
@@ -2251,6 +2251,10 @@ Ref Wasm2JSBuilder::processFunctionBody(Module* m,
       unimplemented(curr);
       WASM_UNREACHABLE("unimp");
     }
+    Ref visitTableFill(TableFill* curr) {
+      unimplemented(curr);
+      WASM_UNREACHABLE("unimp");
+    }
     Ref visitTry(Try* curr) {
       unimplemented(curr);
       WASM_UNREACHABLE("unimp");