Prototype prefetch instructions (#3467)

As proposed in https://github.com/WebAssembly/simd/pull/352, using the opcodes
used in the LLVM and V8 implementations.

17 files changed, 152 insertions, 3 deletions

diff --git a/src/gen-s-parser.inc b/src/gen-s-parser.inc
index c564f3974..bb07d81ca 100644
--- a/src/gen-s-parser.inc
+++ b/src/gen-s-parser.inc
@@ -2759,9 +2759,25 @@ switch (op[0]) {
   case 'n':
     if (strcmp(op, "nop") == 0) { return makeNop(); }
     goto parse_error;
-  case 'p':
-    if (strcmp(op, "pop") == 0) { return makePop(s); }
-    goto parse_error;
+  case 'p': {
+    switch (op[1]) {
+      case 'o':
+        if (strcmp(op, "pop") == 0) { return makePop(s); }
+        goto parse_error;
+      case 'r': {
+        switch (op[9]) {
+          case 'n':
+            if (strcmp(op, "prefetch.nt") == 0) { return makePrefetch(s, PrefetchOp::PrefetchNontemporal); }
+            goto parse_error;
+          case 't':
+            if (strcmp(op, "prefetch.t") == 0) { return makePrefetch(s, PrefetchOp::PrefetchTemporal); }
+            goto parse_error;
+          default: goto parse_error;
+        }
+      }
+      default: goto parse_error;
+    }
+  }
   case 'r': {
     switch (op[1]) {
       case 'e': {
diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index b3639ba00..32b38325d 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -112,6 +112,7 @@ void ReFinalize::visitSIMDLoad(SIMDLoad* curr) { curr->finalize(); }
 void ReFinalize::visitSIMDLoadStoreLane(SIMDLoadStoreLane* curr) {
   curr->finalize();
 }
+void ReFinalize::visitPrefetch(Prefetch* curr) { curr->finalize(); }
 void ReFinalize::visitMemoryInit(MemoryInit* curr) { curr->finalize(); }
 void ReFinalize::visitDataDrop(DataDrop* curr) { curr->finalize(); }
 void ReFinalize::visitMemoryCopy(MemoryCopy* curr) { curr->finalize(); }
diff --git a/src/ir/cost.h b/src/ir/cost.h
index ef0a2bde1..fbb4e83ad 100644
--- a/src/ir/cost.h
+++ b/src/ir/cost.h
@@ -537,6 +537,7 @@ struct CostAnalyzer : public OverriddenVisitor<CostAnalyzer, Index> {
   Index visitSIMDShuffle(SIMDShuffle* curr) {
     return 1 + visit(curr->left) + visit(curr->right);
   }
+  Index visitPrefetch(Prefetch* curr) { return 0 + visit(curr->ptr); }
   Index visitRefNull(RefNull* curr) { return 1; }
   Index visitRefIsNull(RefIsNull* curr) { return 1 + visit(curr->value); }
   Index visitRefFunc(RefFunc* curr) { return 1; }
diff --git a/src/ir/effects.h b/src/ir/effects.h
index 5483242b5..71957d1f8 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -415,6 +415,11 @@ private:
       }
       parent.implicitTrap = true;
     }
+    void visitPrefetch(Prefetch* curr) {
+      // Do not reorder with respect to other memory ops
+      parent.writesMemory = true;
+      parent.readsMemory = true;
+    }
     void visitMemoryInit(MemoryInit* curr) {
       parent.writesMemory = true;
       parent.implicitTrap = true;
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index f9d469faf..8b028c25f 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -683,6 +683,24 @@ struct PrintExpressionContents
     }
     o << " " << int(curr->index);
   }
+  void visitPrefetch(Prefetch* curr) {
+    prepareColor(o);
+    switch (curr->op) {
+      case PrefetchTemporal:
+        o << "prefetch.t";
+        break;
+      case PrefetchNontemporal:
+        o << "prefetch.nt";
+        break;
+    }
+    restoreNormalColor(o);
+    if (curr->offset) {
+      o << " offset=" << curr->offset;
+    }
+    if (curr->align != 1) {
+      o << " align=" << curr->align;
+    }
+  }
   void visitMemoryInit(MemoryInit* curr) {
     prepareColor(o);
     o << "memory.init " << curr->segment;
@@ -2212,6 +2230,13 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
     printFullLine(curr->vec);
     decIndent();
   }
+  void visitPrefetch(Prefetch* curr) {
+    o << '(';
+    PrintExpressionContents(currFunction, o).visit(curr);
+    incIndent();
+    printFullLine(curr->ptr);
+    decIndent();
+  }
   void visitMemoryInit(MemoryInit* curr) {
     o << '(';
     PrintExpressionContents(currFunction, o).visit(curr);
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index b2c922dc2..beee4cead 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -973,6 +973,11 @@ enum ASTNodes {
   I64x2ExtMulLowUI32x4 = 0xd6,
   I64x2ExtMulHighUI32x4 = 0xd7,
 
+  // prefetch opcodes
+
+  PrefetchT = 0xc5,
+  PrefetchNT = 0xc6,
+
   // bulk memory opcodes
 
   MemoryInit = 0x08,
@@ -1481,6 +1486,7 @@ public:
   bool maybeVisitSIMDShift(Expression*& out, uint32_t code);
   bool maybeVisitSIMDLoad(Expression*& out, uint32_t code);
   bool maybeVisitSIMDLoadStoreLane(Expression*& out, uint32_t code);
+  bool maybeVisitPrefetch(Expression*& out, uint32_t code);
   bool maybeVisitMemoryInit(Expression*& out, uint32_t code);
   bool maybeVisitDataDrop(Expression*& out, uint32_t code);
   bool maybeVisitMemoryCopy(Expression*& out, uint32_t code);
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 1ae018e13..a2aa2d505 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -486,6 +486,16 @@ public:
     ret->finalize();
     return ret;
   }
+  Prefetch*
+  makePrefetch(PrefetchOp op, Address offset, Address align, Expression* ptr) {
+    auto* ret = wasm.allocator.alloc<Prefetch>();
+    ret->op = op;
+    ret->offset = offset;
+    ret->align = align;
+    ret->ptr = ptr;
+    ret->finalize();
+    return ret;
+  }
   MemoryInit* makeMemoryInit(uint32_t segment,
                              Expression* dest,
                              Expression* offset,
diff --git a/src/wasm-delegations-fields.h b/src/wasm-delegations-fields.h
index ca8b0bbe6..8322fdeed 100644
--- a/src/wasm-delegations-fields.h
+++ b/src/wasm-delegations-fields.h
@@ -371,6 +371,15 @@ switch (DELEGATE_ID) {
     DELEGATE_END(SIMDLoadStoreLane);
     break;
   }
+  case Expression::Id::PrefetchId: {
+    DELEGATE_START(Prefetch);
+    DELEGATE_FIELD_CHILD(Prefetch, ptr);
+    DELEGATE_FIELD_INT(Prefetch, op);
+    DELEGATE_FIELD_ADDRESS(Prefetch, offset);
+    DELEGATE_FIELD_ADDRESS(Prefetch, align);
+    DELEGATE_END(Prefetch);
+    break;
+  }
   case Expression::Id::MemoryInitId: {
     DELEGATE_START(MemoryInit);
     DELEGATE_FIELD_CHILD(MemoryInit, size);
diff --git a/src/wasm-delegations.h b/src/wasm-delegations.h
index 50ee8247b..f46f5cbb2 100644
--- a/src/wasm-delegations.h
+++ b/src/wasm-delegations.h
@@ -40,6 +40,7 @@ DELEGATE(SIMDTernary);
 DELEGATE(SIMDShift);
 DELEGATE(SIMDLoad);
 DELEGATE(SIMDLoadStoreLane);
+DELEGATE(Prefetch);
 DELEGATE(MemoryInit);
 DELEGATE(DataDrop);
 DELEGATE(MemoryCopy);
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 3d963269d..392b0c2bc 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1167,6 +1167,14 @@ public:
     NOTE_ENTER("Nop");
     return Flow();
   }
+  Flow visitPrefetch(Prefetch* curr) {
+    NOTE_ENTER("Prefetch");
+    Flow flow = visit(curr->ptr);
+    if (flow.breaking()) {
+      return flow;
+    }
+    return Flow();
+  }
   Flow visitUnreachable(Unreachable* curr) {
     NOTE_ENTER("Unreachable");
     trap("unreachable");
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index 43841b873..074e9dbe7 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -220,6 +220,7 @@ private:
   Expression* makeSIMDShift(Element& s, SIMDShiftOp op);
   Expression* makeSIMDLoad(Element& s, SIMDLoadOp op);
   Expression* makeSIMDLoadStoreLane(Element& s, SIMDLoadStoreLaneOp op);
+  Expression* makePrefetch(Element& s, PrefetchOp op);
   Expression* makeMemoryInit(Element& s);
   Expression* makeDataDrop(Element& s);
   Expression* makeMemoryCopy(Element& s);
diff --git a/src/wasm.h b/src/wasm.h
index 12aacd2ed..29d2e9b5d 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -530,6 +530,11 @@ enum SIMDTernaryOp {
   SignSelectVec64x2
 };
 
+enum PrefetchOp {
+  PrefetchTemporal,
+  PrefetchNontemporal,
+};
+
 //
 // Expressions
 //
@@ -577,6 +582,7 @@ public:
     MemorySizeId,
     MemoryGrowId,
     NopId,
+    PrefetchId,
     UnreachableId,
     AtomicRMWId,
     AtomicCmpxchgId,
@@ -1037,6 +1043,18 @@ public:
   void finalize();
 };
 
+class Prefetch : public SpecificExpression<Expression::PrefetchId> {
+public:
+  Prefetch() = default;
+  Prefetch(MixedArena& allocator) : Prefetch() {}
+
+  PrefetchOp op;
+  Address offset;
+  Address align;
+  Expression* ptr;
+  void finalize();
+};
+
 class MemoryInit : public SpecificExpression<Expression::MemoryInitId> {
 public:
   MemoryInit() = default;
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index e616493af..f3160c461 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -2967,6 +2967,9 @@ BinaryConsts::ASTNodes WasmBinaryBuilder::readExpression(Expression*& curr) {
       if (maybeVisitSIMDLoadStoreLane(curr, opcode)) {
         break;
       }
+      if (maybeVisitPrefetch(curr, opcode)) {
+        break;
+      }
       throwError("invalid code after SIMD prefix: " + std::to_string(opcode));
       break;
     }
@@ -5372,6 +5375,24 @@ bool WasmBinaryBuilder::maybeVisitSIMDLoadStoreLane(Expression*& out,
   return true;
 }
 
+bool WasmBinaryBuilder::maybeVisitPrefetch(Expression*& out, uint32_t code) {
+  PrefetchOp op;
+  switch (code) {
+    case BinaryConsts::PrefetchT:
+      op = PrefetchTemporal;
+      break;
+    case BinaryConsts::PrefetchNT:
+      op = PrefetchNontemporal;
+      break;
+    default:
+      return false;
+  }
+  Address align, offset;
+  readMemoryAccess(align, offset);
+  out = Builder(wasm).makePrefetch(op, offset, align, popNonVoidExpression());
+  return true;
+}
+
 void WasmBinaryBuilder::visitSelect(Select* curr, uint8_t code) {
   BYN_TRACE("zz node: Select, code " << int32_t(code) << std::endl);
   if (code == BinaryConsts::SelectWithType) {
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 20e99436a..20ab4f3d2 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -1662,6 +1662,12 @@ SExpressionWasmBuilder::makeSIMDLoadStoreLane(Element& s,
   return ret;
 }
 
+Expression* SExpressionWasmBuilder::makePrefetch(Element& s, PrefetchOp op) {
+  Address offset, align;
+  size_t i = parseMemAttributes(s, offset, align, /*defaultAlign*/ 1);
+  return Builder(wasm).makePrefetch(op, offset, align, parseExpression(s[i]));
+}
+
 Expression* SExpressionWasmBuilder::makeMemoryInit(Element& s) {
   auto ret = allocator.alloc<MemoryInit>();
   ret->segment = atoi(s[1]->str().c_str());
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index 776928b88..b31aaf4d4 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -694,6 +694,20 @@ void BinaryInstWriter::visitSIMDLoadStoreLane(SIMDLoadStoreLane* curr) {
   o << curr->index;
 }
 
+void BinaryInstWriter::visitPrefetch(Prefetch* curr) {
+  o << int8_t(BinaryConsts::SIMDPrefix);
+  switch (curr->op) {
+    case PrefetchTemporal:
+      o << U32LEB(BinaryConsts::PrefetchT);
+      break;
+    case PrefetchNontemporal:
+      o << U32LEB(BinaryConsts::PrefetchNT);
+      break;
+  }
+  assert(curr->align);
+  emitMemoryAccess(curr->align, /*(unused) bytes=*/0, curr->offset);
+}
+
 void BinaryInstWriter::visitMemoryInit(MemoryInit* curr) {
   o << int8_t(BinaryConsts::MiscPrefix);
   o << U32LEB(BinaryConsts::MemoryInit);
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index 264f2bf83..fb523e254 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -174,6 +174,8 @@ const char* getExpressionName(Expression* curr) {
       return "simd_load";
     case Expression::Id::SIMDLoadStoreLaneId:
       return "simd_load_store_lane";
+    case Expression::Id::PrefetchId:
+      return "prefetch";
     case Expression::Id::MemoryInitId:
       return "memory.init";
     case Expression::Id::DataDropId:
@@ -656,6 +658,10 @@ bool SIMDLoadStoreLane::isStore() {
   WASM_UNREACHABLE("unexpected op");
 }
 
+void Prefetch::finalize() {
+  type = ptr->type == Type::unreachable ? Type::unreachable : Type::none;
+}
+
 Const* Const::set(Literal value_) {
   value = value_;
   type = value.type;
diff --git a/src/wasm2js.h b/src/wasm2js.h
index 5257e3456..a9b57b185 100644
--- a/src/wasm2js.h
+++ b/src/wasm2js.h
@@ -1984,6 +1984,7 @@ Ref Wasm2JSBuilder::processFunctionBody(Module* m,
     }
 
     Ref visitNop(Nop* curr) { return ValueBuilder::makeToplevel(); }
+    Ref visitPrefetch(Prefetch* curr) { return ValueBuilder::makeToplevel(); }
 
     Ref visitUnreachable(Unreachable* curr) {
       return ValueBuilder::makeCall(ABORT_FUNC);