Finish bulk memory support (#2030)

Implement interpretation of remaining bulk memory ops, add bulk memory
spec tests with light modifications, fix bugs preventing the fuzzer
from running correctly with bulk memory, and fix bugs found by the
fuzzer.

6 files changed, 96 insertions, 25 deletions

diff --git a/src/passes/RemoveUnusedModuleElements.cpp b/src/passes/RemoveUnusedModuleElements.cpp
index 777d2dacc..e91fafcba 100644
--- a/src/passes/RemoveUnusedModuleElements.cpp
+++ b/src/passes/RemoveUnusedModuleElements.cpp
@@ -39,6 +39,7 @@ enum class ModuleElementKind {
 typedef std::pair<ModuleElementKind, Name> ModuleElement;
 
 // Finds reachabilities
+// TODO: use Effects to determine if a memory is used
 
 struct ReachabilityAnalyzer : public PostWalker<ReachabilityAnalyzer> {
   Module* module;
@@ -119,6 +120,18 @@ struct ReachabilityAnalyzer : public PostWalker<ReachabilityAnalyzer> {
   void visitAtomicNotify(AtomicNotify* curr) {
     usesMemory = true;
   }
+  void visitMemoryInit(MemoryInit* curr) {
+    usesMemory = true;
+  }
+  void visitDataDrop(DataDrop* curr) {
+    usesMemory = true;
+  }
+  void visitMemoryCopy(MemoryCopy* curr) {
+    usesMemory = true;
+  }
+  void visitMemoryFill(MemoryFill* curr) {
+    usesMemory = true;
+  }
   void visitHost(Host* curr) {
     if (curr->op == CurrentMemory || curr->op == GrowMemory) {
       usesMemory = true;
diff --git a/src/tools/wasm-opt.cpp b/src/tools/wasm-opt.cpp
index 6fce0f89b..519713298 100644
--- a/src/tools/wasm-opt.cpp
+++ b/src/tools/wasm-opt.cpp
@@ -240,6 +240,7 @@ int main(int argc, const char* argv[]) {
     auto input = buffer.getAsChars();
     WasmBinaryBuilder parser(other, input, false);
     parser.read();
+    options.applyFeatures(other);
     if (options.passOptions.validate) {
       bool valid = WasmValidator().validate(other);
       if (!valid) {
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index fcdb44c42..23121a849 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -928,10 +928,6 @@ private:
   }
 
   void initializeMemoryContents() {
-    // no way to create a Block without an ArenaAllocator, so use a builder
-    // instead of creating it locally.
-    Builder builder(wasm);
-
     Const offset;
     offset.value = Literal(uint32_t(0));
     offset.finalize();
@@ -955,15 +951,16 @@ private:
       init.finalize();
 
       DataDrop drop;
-      drop.segment = segment.index;
+      drop.segment = i;
       drop.finalize();
 
-      Function initializer;
-      initializer.body = builder.blockify(&init, &drop);
-
-      FunctionScope scope(&initializer, {});
-
-      RuntimeExpressionRunner(*this, scope).visit(&init);
+      // we don't actually have a function, but we need one in order to visit
+      // the memory.init and data.drop instructions.
+      Function dummyFunc;
+      FunctionScope dummyScope(&dummyFunc, {});
+      RuntimeExpressionRunner runner(*this, dummyScope);
+      runner.visit(&init);
+      runner.visit(&drop);
     }
   }
 
@@ -1228,14 +1225,20 @@ private:
         trap("memory.init of dropped segment");
       }
 
-      size_t destVal(dest.value.geti32());
-      size_t offsetVal(offset.value.geti32());
-      size_t sizeVal(size.value.geti32());
+      Address destVal(uint32_t(dest.value.geti32()));
+      Address offsetVal(uint32_t(offset.value.geti32()));
+      Address sizeVal(uint32_t(size.value.geti32()));
+
+      instance.checkLoadAddress(destVal, 0);
+      if (offsetVal > segment.data.size()) {
+        trap("segment offset out of bounds");
+      }
+
       for (size_t i = 0; i < sizeVal; ++i) {
         if (offsetVal + i >= segment.data.size()) {
           trap("out of bounds segment access in memory.init");
         }
-        Literal addr = Literal(uint32_t(destVal + i));
+        Literal addr(uint32_t(destVal + i));
         instance.externalInterface->store8(
           instance.getFinalAddress(addr, 1),
           segment.data[offsetVal + i]
@@ -1253,12 +1256,64 @@ private:
     }
     Flow visitMemoryCopy(MemoryCopy *curr) {
       NOTE_ENTER("MemoryCopy");
-      // TODO(tlively): implement me
+      Flow dest = this->visit(curr->dest);
+      if (dest.breaking()) return dest;
+      Flow source = this->visit(curr->source);
+      if (source.breaking()) return source;
+      Flow size = this->visit(curr->size);
+      if (size.breaking()) return size;
+      NOTE_EVAL1(dest);
+      NOTE_EVAL1(source);
+      NOTE_EVAL1(size);
+      Address destVal(uint32_t(dest.value.geti32()));
+      Address sourceVal(uint32_t(source.value.geti32()));
+      Address sizeVal(uint32_t(size.value.geti32()));
+
+      instance.checkLoadAddress(destVal, 0);
+      instance.checkLoadAddress(sourceVal, 0);
+
+      size_t start = 0;
+      size_t end = sizeVal;
+      int step = 1;
+      // Reverse direction if source is below dest and they overlap
+      if (sourceVal < destVal &&
+          (sourceVal + sizeVal > destVal || sourceVal + sizeVal < sourceVal)) {
+        start = sizeVal - 1;
+        end = -1;
+        step = -1;
+      }
+      for (size_t i = start; i != end; i += step) {
+        if (i + destVal >= std::numeric_limits<uint32_t>::max()) {
+          trap("Out of bounds memory access");
+        }
+        instance.externalInterface->store8(
+          instance.getFinalAddress(Literal(uint32_t(destVal + i)), 1),
+          instance.externalInterface->load8s(
+            instance.getFinalAddress(Literal(uint32_t(sourceVal + i)), 1)));
+      }
       return {};
     }
     Flow visitMemoryFill(MemoryFill *curr) {
       NOTE_ENTER("MemoryFill");
-      // TODO(tlively): implement me
+      Flow dest = this->visit(curr->dest);
+      if (dest.breaking()) return dest;
+      Flow value = this->visit(curr->value);
+      if (value.breaking()) return value;
+      Flow size = this->visit(curr->size);
+      if (size.breaking()) return size;
+      NOTE_EVAL1(dest);
+      NOTE_EVAL1(value);
+      NOTE_EVAL1(size);
+      Address destVal(uint32_t(dest.value.geti32()));
+      Address sizeVal(uint32_t(size.value.geti32()));
+
+      instance.checkLoadAddress(destVal, 0);
+
+      uint8_t val(value.value.geti32());
+      for (size_t i = 0; i < sizeVal; ++i) {
+        instance.externalInterface->store8(
+          instance.getFinalAddress(Literal(uint32_t(destVal + i)), 1), val);
+      }
       return {};
     }
 
diff --git a/src/wasm-traversal.h b/src/wasm-traversal.h
index 8aa203fa7..38fcdb990 100644
--- a/src/wasm-traversal.h
+++ b/src/wasm-traversal.h
@@ -657,9 +657,9 @@ struct PostWalker : public Walker<SubType, VisitorType> {
       }
       case Expression::Id::MemoryInitId: {
         self->pushTask(SubType::doVisitMemoryInit, currp);
-        self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->dest);
-        self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->offset);
         self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->size);
+        self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->offset);
+        self->pushTask(SubType::scan, &curr->cast<MemoryInit>()->dest);
         break;
         }
       case Expression::Id::DataDropId: {
@@ -668,16 +668,16 @@ struct PostWalker : public Walker<SubType, VisitorType> {
         }
       case Expression::Id::MemoryCopyId: {
         self->pushTask(SubType::doVisitMemoryCopy, currp);
-        self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->dest);
-        self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->source);
         self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->size);
+        self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->source);
+        self->pushTask(SubType::scan, &curr->cast<MemoryCopy>()->dest);
         break;
         }
       case Expression::Id::MemoryFillId: {
         self->pushTask(SubType::doVisitMemoryFill, currp);
-        self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->dest);
-        self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->value);
         self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->size);
+        self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->value);
+        self->pushTask(SubType::scan, &curr->cast<MemoryFill>()->dest);
         break;
         }
       case Expression::Id::ConstId: {
diff --git a/src/wasm.h b/src/wasm.h
index f4180f7a0..83809243c 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -859,7 +859,6 @@ public:
 
   struct Segment {
     bool isPassive = false;
-    Index index = 0;
     Expression* offset = nullptr;
     std::vector<char> data; // TODO: optimize
     Segment() = default;
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index f3642203d..b8c3f1049 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1540,7 +1540,10 @@ void WasmBinaryBuilder::readDataSegments() {
     }
     curr.isPassive = flags & BinaryConsts::IsPassive;
     if (flags & BinaryConsts::HasMemIndex) {
-      curr.index = getU32LEB();
+      auto memIndex = getU32LEB();
+      if (memIndex != 0) {
+        throwError("nonzero memory index");
+      }
     }
     if (!curr.isPassive) {
       curr.offset = readExpression();