Minimal Push/Pop support (#2207)

This is the first stage of adding support for stacky/multivaluey things. It adds new push/pop instructions, and so far just shows that they can be read and written, and that the optimizer doesn't do anything immediately wrong on them.

No fuzzer support, since there isn't a "correct" way to use these yet. The current test shows some "incorrect" usages of them, which is nice to see that we can parse/emit them, but we should replace them with proper usages of push/pop once we actually have those (see comments in the tests).

This should be enough to unblock exceptions (which needs a pop in try-catches). It is also a step towards multivalue (I added some docs about that), but most of multivalue is left to be done.

16 files changed, 214 insertions, 14 deletions

diff --git a/src/gen-s-parser.inc b/src/gen-s-parser.inc
index 2fd554107..5750981f5 100644
--- a/src/gen-s-parser.inc
+++ b/src/gen-s-parser.inc
@@ -200,6 +200,9 @@ switch (op[0]) {
                   default: goto parse_error;
                 }
               }
+              case 'p':
+                if (strcmp(op, "f32.pop") == 0) { return makePop(f32); }
+                goto parse_error;
               case 'r':
                 if (strcmp(op, "f32.reinterpret_i32") == 0) { return makeUnary(s, UnaryOp::ReinterpretInt32); }
                 goto parse_error;
@@ -459,9 +462,17 @@ switch (op[0]) {
                   default: goto parse_error;
                 }
               }
-              case 'p':
-                if (strcmp(op, "f64.promote_f32") == 0) { return makeUnary(s, UnaryOp::PromoteFloat32); }
-                goto parse_error;
+              case 'p': {
+                switch (op[5]) {
+                  case 'o':
+                    if (strcmp(op, "f64.pop") == 0) { return makePop(f64); }
+                    goto parse_error;
+                  case 'r':
+                    if (strcmp(op, "f64.promote_f32") == 0) { return makeUnary(s, UnaryOp::PromoteFloat32); }
+                    goto parse_error;
+                  default: goto parse_error;
+                }
+              }
               case 'r':
                 if (strcmp(op, "f64.reinterpret_i64") == 0) { return makeUnary(s, UnaryOp::ReinterpretInt64); }
                 goto parse_error;
@@ -1089,9 +1100,17 @@ switch (op[0]) {
               case 'o':
                 if (strcmp(op, "i32.or") == 0) { return makeBinary(s, BinaryOp::OrInt32); }
                 goto parse_error;
-              case 'p':
-                if (strcmp(op, "i32.popcnt") == 0) { return makeUnary(s, UnaryOp::PopcntInt32); }
-                goto parse_error;
+              case 'p': {
+                switch (op[7]) {
+                  case '\0':
+                    if (strcmp(op, "i32.pop") == 0) { return makePop(i32); }
+                    goto parse_error;
+                  case 'c':
+                    if (strcmp(op, "i32.popcnt") == 0) { return makeUnary(s, UnaryOp::PopcntInt32); }
+                    goto parse_error;
+                  default: goto parse_error;
+                }
+              }
               case 'r': {
                 switch (op[5]) {
                   case 'e': {
@@ -1757,9 +1776,17 @@ switch (op[0]) {
               case 'o':
                 if (strcmp(op, "i64.or") == 0) { return makeBinary(s, BinaryOp::OrInt64); }
                 goto parse_error;
-              case 'p':
-                if (strcmp(op, "i64.popcnt") == 0) { return makeUnary(s, UnaryOp::PopcntInt64); }
-                goto parse_error;
+              case 'p': {
+                switch (op[7]) {
+                  case '\0':
+                    if (strcmp(op, "i64.pop") == 0) { return makePop(i64); }
+                    goto parse_error;
+                  case 'c':
+                    if (strcmp(op, "i64.popcnt") == 0) { return makeUnary(s, UnaryOp::PopcntInt64); }
+                    goto parse_error;
+                  default: goto parse_error;
+                }
+              }
               case 'r': {
                 switch (op[5]) {
                   case 'e': {
@@ -2198,6 +2225,9 @@ switch (op[0]) {
   case 'n':
     if (strcmp(op, "nop") == 0) { return makeNop(); }
     goto parse_error;
+  case 'p':
+    if (strcmp(op, "push") == 0) { return makePush(s); }
+    goto parse_error;
   case 'r':
     if (strcmp(op, "return") == 0) { return makeReturn(s); }
     goto parse_error;
diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp
index 32e763a45..170202888 100644
--- a/src/ir/ExpressionAnalyzer.cpp
+++ b/src/ir/ExpressionAnalyzer.cpp
@@ -209,6 +209,8 @@ template<typename T> void visitImmediates(Expression* curr, T& visitor) {
     }
     void visitNop(Nop* curr) {}
     void visitUnreachable(Unreachable* curr) {}
+    void visitPush(Push* curr) {}
+    void visitPop(Pop* curr) {}
   } singleton(curr, visitor);
 }
 
diff --git a/src/ir/ReFinalize.cpp b/src/ir/ReFinalize.cpp
index 6723c5e4f..9e3b59c70 100644
--- a/src/ir/ReFinalize.cpp
+++ b/src/ir/ReFinalize.cpp
@@ -157,6 +157,8 @@ void ReFinalize::visitReturn(Return* curr) { curr->finalize(); }
 void ReFinalize::visitHost(Host* curr) { curr->finalize(); }
 void ReFinalize::visitNop(Nop* curr) { curr->finalize(); }
 void ReFinalize::visitUnreachable(Unreachable* curr) { curr->finalize(); }
+void ReFinalize::visitPush(Push* curr) { curr->finalize(); }
+void ReFinalize::visitPop(Pop* curr) { curr->finalize(); }
 
 void ReFinalize::visitFunction(Function* curr) {
   // we may have changed the body from unreachable to none, which might be bad
diff --git a/src/ir/effects.h b/src/ir/effects.h
index b7c420100..14cbd6217 100644
--- a/src/ir/effects.h
+++ b/src/ir/effects.h
@@ -368,6 +368,8 @@ struct EffectAnalyzer
   }
   void visitNop(Nop* curr) {}
   void visitUnreachable(Unreachable* curr) { branches = true; }
+  void visitPush(Push* curr) { calls = true; }
+  void visitPop(Pop* curr) { calls = true; }
 
   // Helpers
 
diff --git a/src/ir/utils.h b/src/ir/utils.h
index b8e8fe815..ae6368e3b 100644
--- a/src/ir/utils.h
+++ b/src/ir/utils.h
@@ -146,6 +146,8 @@ struct ReFinalize
   void visitHost(Host* curr);
   void visitNop(Nop* curr);
   void visitUnreachable(Unreachable* curr);
+  void visitPush(Push* curr);
+  void visitPop(Pop* curr);
 
   void visitFunction(Function* curr);
 
@@ -203,6 +205,8 @@ struct ReFinalizeNode : public OverriddenVisitor<ReFinalizeNode> {
   void visitHost(Host* curr) { curr->finalize(); }
   void visitNop(Nop* curr) { curr->finalize(); }
   void visitUnreachable(Unreachable* curr) { curr->finalize(); }
+  void visitPush(Push* curr) { curr->finalize(); }
+  void visitPop(Pop* curr) { curr->finalize(); }
 
   void visitFunctionType(FunctionType* curr) { WASM_UNREACHABLE(); }
   void visitExport(Export* curr) { WASM_UNREACHABLE(); }
diff --git a/src/passes/DeadCodeElimination.cpp b/src/passes/DeadCodeElimination.cpp
index da22a7f28..6e6f2c2b9 100644
--- a/src/passes/DeadCodeElimination.cpp
+++ b/src/passes/DeadCodeElimination.cpp
@@ -308,6 +308,10 @@ struct DeadCodeElimination
           DELEGATE(MemoryCopy);
         case Expression::Id::MemoryFillId:
           DELEGATE(MemoryFill);
+        case Expression::Id::PushId:
+          DELEGATE(Push);
+        case Expression::Id::PopId:
+          DELEGATE(Pop);
         case Expression::Id::InvalidId:
           WASM_UNREACHABLE();
         case Expression::Id::NumExpressionIds:
diff --git a/src/passes/Precompute.cpp b/src/passes/Precompute.cpp
index a7edb54c9..55ff9e264 100644
--- a/src/passes/Precompute.cpp
+++ b/src/passes/Precompute.cpp
@@ -130,6 +130,8 @@ public:
   Flow visitMemoryCopy(MemoryCopy* curr) { return Flow(NOTPRECOMPUTABLE_FLOW); }
   Flow visitMemoryFill(MemoryFill* curr) { return Flow(NOTPRECOMPUTABLE_FLOW); }
   Flow visitHost(Host* curr) { return Flow(NOTPRECOMPUTABLE_FLOW); }
+  Flow visitPush(Push* curr) { return Flow(NOTPRECOMPUTABLE_FLOW); }
+  Flow visitPop(Pop* curr) { return Flow(NOTPRECOMPUTABLE_FLOW); }
 
   void trap(const char* why) override { throw NonstandaloneException(); }
 };
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index 9dbf3cc1f..e1ed788c4 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -57,7 +57,8 @@ static Name printableLocal(Index index, Function* func) {
 
 // Prints the internal contents of an expression: everything but
 // the children.
-struct PrintExpressionContents : public Visitor<PrintExpressionContents> {
+struct PrintExpressionContents
+  : public OverriddenVisitor<PrintExpressionContents> {
   Function* currFunction = nullptr;
   std::ostream& o;
 
@@ -1150,11 +1151,17 @@ struct PrintExpressionContents : public Visitor<PrintExpressionContents> {
   }
   void visitNop(Nop* curr) { printMinor(o, "nop"); }
   void visitUnreachable(Unreachable* curr) { printMinor(o, "unreachable"); }
+  void visitPush(Push* curr) { prepareColor(o) << "push"; }
+  void visitPop(Pop* curr) {
+    prepareColor(o) << printType(curr->type);
+    o << ".pop";
+    restoreNormalColor(o);
+  }
 };
 
 // Prints an expression in s-expr format, including both the
 // internal contents and the nested children.
-struct PrintSExpression : public Visitor<PrintSExpression> {
+struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
   std::ostream& o;
   unsigned indent = 0;
 
@@ -1205,7 +1212,7 @@ struct PrintSExpression : public Visitor<PrintSExpression> {
 
   void visit(Expression* curr) {
     printDebugLocation(curr);
-    Visitor<PrintSExpression>::visit(curr);
+    OverriddenVisitor<PrintSExpression>::visit(curr);
   }
 
   void setMinify(bool minify_) {
@@ -1621,6 +1628,18 @@ struct PrintSExpression : public Visitor<PrintSExpression> {
     PrintExpressionContents(currFunction, o).visit(curr);
     o << ')';
   }
+  void visitPush(Push* curr) {
+    o << '(';
+    PrintExpressionContents(currFunction, o).visit(curr);
+    incIndent();
+    printFullLine(curr->value);
+    decIndent();
+  }
+  void visitPop(Pop* curr) {
+    o << '(';
+    PrintExpressionContents(currFunction, o).visit(curr);
+    o << ')';
+  }
   // Module-level visitors
   void visitFunctionType(FunctionType* curr, Name* internalName = nullptr) {
     o << "(func";
diff --git a/src/wasm-builder.h b/src/wasm-builder.h
index 7d839357e..8bf60e59c 100644
--- a/src/wasm-builder.h
+++ b/src/wasm-builder.h
@@ -492,6 +492,18 @@ public:
     return ret;
   }
   Unreachable* makeUnreachable() { return allocator.alloc<Unreachable>(); }
+  Push* makePush(Expression* value) {
+    auto* ret = allocator.alloc<Push>();
+    ret->value = value;
+    ret->finalize();
+    return ret;
+  }
+  Pop* makePop(Type type) {
+    auto* ret = allocator.alloc<Pop>();
+    ret->type = type;
+    ret->finalize();
+    return ret;
+  }
 
   // Additional helpers
 
diff --git a/src/wasm-interpreter.h b/src/wasm-interpreter.h
index 560051917..890e1a844 100644
--- a/src/wasm-interpreter.h
+++ b/src/wasm-interpreter.h
@@ -1046,6 +1046,8 @@ public:
   Flow visitAtomicCmpxchg(AtomicCmpxchg*) { WASM_UNREACHABLE(); }
   Flow visitAtomicWait(AtomicWait*) { WASM_UNREACHABLE(); }
   Flow visitAtomicNotify(AtomicNotify*) { WASM_UNREACHABLE(); }
+  Flow visitPush(Push*) { WASM_UNREACHABLE(); }
+  Flow visitPop(Pop*) { WASM_UNREACHABLE(); }
 
   virtual void trap(const char* why) { WASM_UNREACHABLE(); }
 };
@@ -1227,6 +1229,9 @@ public:
   // Values of globals
   GlobalManager globals;
 
+  // Multivalue ABI support (see push/pop).
+  std::vector<Literal> multiValues;
+
   ModuleInstanceBase(Module& wasm, ExternalInterface* externalInterface)
     : wasm(wasm), externalInterface(externalInterface) {
     // import globals from the outside
@@ -1776,6 +1781,22 @@ private:
       }
       return {};
     }
+    Flow visitPush(Push* curr) {
+      NOTE_ENTER("Push");
+      Flow value = this->visit(curr->value);
+      if (value.breaking()) {
+        return value;
+      }
+      instance.multiValues.push_back(value.value);
+      return Flow();
+    }
+    Flow visitPop(Pop* curr) {
+      NOTE_ENTER("Pop");
+      assert(!instance.multiValues.empty());
+      auto ret = instance.multiValues.back();
+      instance.multiValues.pop_back();
+      return ret;
+    }
 
     void trap(const char* why) override {
       instance.externalInterface->trap(why);
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index 71249748e..e87eaae4e 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -203,6 +203,8 @@ private:
   Expression* makeDataDrop(Element& s);
   Expression* makeMemoryCopy(Element& s);
   Expression* makeMemoryFill(Element& s);
+  Expression* makePush(Element& s);
+  Expression* makePop(Type type);
   Expression* makeIf(Element& s);
   Expression* makeMaybeBlock(Element& s, size_t i, Type type);
   Expression* makeLoop(Element& s);
diff --git a/src/wasm-stack.h b/src/wasm-stack.h
index 9a71681a2..7003b7b95 100644
--- a/src/wasm-stack.h
+++ b/src/wasm-stack.h
@@ -94,7 +94,7 @@ public:
 enum class StackWriterMode { Binaryen2Binary, Binaryen2Stack, Stack2Binary };
 
 template<StackWriterMode Mode, typename Parent>
-class StackWriter : public Visitor<StackWriter<Mode, Parent>> {
+class StackWriter : public OverriddenVisitor<StackWriter<Mode, Parent>> {
 public:
   StackWriter(Parent& parent,
               BufferWithRandomAccess& o,
@@ -159,6 +159,8 @@ public:
   void visitNop(Nop* curr);
   void visitUnreachable(Unreachable* curr);
   void visitDrop(Drop* curr);
+  void visitPush(Push* curr);
+  void visitPop(Pop* curr);
 
   // We need to emit extra unreachable opcodes in some cases
   void emitExtraUnreachable();
@@ -358,7 +360,7 @@ void StackWriter<Mode, Parent>::visit(Expression* curr) {
   if (Mode == StackWriterMode::Binaryen2Binary && sourceMap) {
     parent.writeDebugLocation(curr, func);
   }
-  Visitor<StackWriter>::visit(curr);
+  OverriddenVisitor<StackWriter>::visit(curr);
 }
 
 // emits a node, but if it is a block with no name, emit a list of its contents
@@ -2224,6 +2226,19 @@ void StackWriter<Mode, Parent>::visitDrop(Drop* curr) {
 }
 
 template<StackWriterMode Mode, typename Parent>
+void StackWriter<Mode, Parent>::visitPush(Push* curr) {
+  // Turns into nothing in the binary format: leave the child on the
+  // stack for others to use.
+  visitChild(curr->value);
+}
+
+template<StackWriterMode Mode, typename Parent>
+void StackWriter<Mode, Parent>::visitPop(Pop* curr) {
+  // Turns into nothing in the binary format: just get a value that is
+  // already on the stack.
+}
+
+template<StackWriterMode Mode, typename Parent>
 int32_t StackWriter<Mode, Parent>::getBreakIndex(Name name) { // -1 if not found
   for (int i = breakStack.size() - 1; i >= 0; i--) {
     if (breakStack[i] == name) {
diff --git a/src/wasm-traversal.h b/src/wasm-traversal.h
index f1306721e..04ab5f04a 100644
--- a/src/wasm-traversal.h
+++ b/src/wasm-traversal.h
@@ -72,6 +72,8 @@ template<typename SubType, typename ReturnType = void> struct Visitor {
   ReturnType visitHost(Host* curr) { return ReturnType(); }
   ReturnType visitNop(Nop* curr) { return ReturnType(); }
   ReturnType visitUnreachable(Unreachable* curr) { return ReturnType(); }
+  ReturnType visitPush(Push* curr) { return ReturnType(); }
+  ReturnType visitPop(Pop* curr) { return ReturnType(); }
   // Module-level visitors
   ReturnType visitFunctionType(FunctionType* curr) { return ReturnType(); }
   ReturnType visitExport(Export* curr) { return ReturnType(); }
@@ -160,6 +162,10 @@ template<typename SubType, typename ReturnType = void> struct Visitor {
         DELEGATE(Nop);
       case Expression::Id::UnreachableId:
         DELEGATE(Unreachable);
+      case Expression::Id::PushId:
+        DELEGATE(Push);
+      case Expression::Id::PopId:
+        DELEGATE(Pop);
       case Expression::Id::InvalidId:
       default:
         WASM_UNREACHABLE();
@@ -218,6 +224,8 @@ struct OverriddenVisitor {
   UNIMPLEMENTED(Host);
   UNIMPLEMENTED(Nop);
   UNIMPLEMENTED(Unreachable);
+  UNIMPLEMENTED(Push);
+  UNIMPLEMENTED(Pop);
   UNIMPLEMENTED(FunctionType);
   UNIMPLEMENTED(Export);
   UNIMPLEMENTED(Global);
@@ -307,6 +315,10 @@ struct OverriddenVisitor {
         DELEGATE(Nop);
       case Expression::Id::UnreachableId:
         DELEGATE(Unreachable);
+      case Expression::Id::PushId:
+        DELEGATE(Push);
+      case Expression::Id::PopId:
+        DELEGATE(Pop);
       case Expression::Id::InvalidId:
       default:
         WASM_UNREACHABLE();
@@ -430,6 +442,12 @@ struct UnifiedExpressionVisitor : public Visitor<SubType, ReturnType> {
   ReturnType visitUnreachable(Unreachable* curr) {
     return static_cast<SubType*>(this)->visitExpression(curr);
   }
+  ReturnType visitPush(Push* curr) {
+    return static_cast<SubType*>(this)->visitExpression(curr);
+  }
+  ReturnType visitPop(Pop* curr) {
+    return static_cast<SubType*>(this)->visitExpression(curr);
+  }
 };
 
 //
@@ -711,6 +729,12 @@ struct Walker : public VisitorType {
   static void doVisitUnreachable(SubType* self, Expression** currp) {
     self->visitUnreachable((*currp)->cast<Unreachable>());
   }
+  static void doVisitPush(SubType* self, Expression** currp) {
+    self->visitPush((*currp)->cast<Push>());
+  }
+  static void doVisitPop(SubType* self, Expression** currp) {
+    self->visitPop((*currp)->cast<Pop>());
+  }
 
   void setModule(Module* module) { currModule = module; }
 
@@ -945,6 +969,14 @@ struct PostWalker : public Walker<SubType, VisitorType> {
         self->pushTask(SubType::doVisitUnreachable, currp);
         break;
       }
+      case Expression::Id::PushId: {
+        self->pushTask(SubType::doVisitPush, currp);
+        break;
+      }
+      case Expression::Id::PopId: {
+        self->pushTask(SubType::doVisitPop, currp);
+        break;
+      }
       case Expression::Id::NumExpressionIds:
         WASM_UNREACHABLE();
     }
diff --git a/src/wasm.h b/src/wasm.h
index de3289289..0c4576f23 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -477,6 +477,8 @@ public:
     DataDropId,
     MemoryCopyId,
     MemoryFillId,
+    PushId,
+    PopId,
     NumExpressionIds
   };
   Id _id;
@@ -974,6 +976,31 @@ public:
   Unreachable(MixedArena& allocator) : Unreachable() {}
 };
 
+// A multivalue push. This represents a push of a value, which will be
+// used in the next return. That is, a multivalue return is done by
+// pushing some values, then doing a return (with a value as well).
+// For more on this design, see the readme.
+class Push : public SpecificExpression<Expression::PushId> {
+public:
+  Push() = default;
+  Push(MixedArena& allocator) {}
+
+  Expression* value;
+
+  void finalize();
+};
+
+// A multivalue pop. This represents a pop of a value, which arrived
+// from a multivalue call or other situation where there are things on
+// the stack. That is, a multivalue-returning call is done by doing
+// the call, receiving the first value normally, and receiving the others
+// via calls to pop.
+class Pop : public SpecificExpression<Expression::PopId> {
+public:
+  Pop() = default;
+  Pop(MixedArena& allocator) {}
+};
+
 // Globals
 
 struct Importable {
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index 8ead42608..04c31815f 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -1519,6 +1519,20 @@ Expression* SExpressionWasmBuilder::makeMemoryFill(Element& s) {
   return ret;
 }
 
+Expression* SExpressionWasmBuilder::makePush(Element& s) {
+  auto ret = allocator.alloc<Push>();
+  ret->value = parseExpression(s[1]);
+  ret->finalize();
+  return ret;
+}
+
+Expression* SExpressionWasmBuilder::makePop(Type type) {
+  auto ret = allocator.alloc<Pop>();
+  ret->type = type;
+  ret->finalize();
+  return ret;
+}
+
 Expression* SExpressionWasmBuilder::makeIf(Element& s) {
   auto ret = allocator.alloc<If>();
   Index i = 1;
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index c543686ed..56eb83fbc 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -161,6 +161,10 @@ const char* getExpressionName(Expression* curr) {
       return "memory_copy";
     case Expression::Id::MemoryFillId:
       return "memory_fill";
+    case Expression::Id::PushId:
+      return "push";
+    case Expression::Id::PopId:
+      return "pop";
     case Expression::Id::NumExpressionIds:
       WASM_UNREACHABLE();
   }
@@ -821,6 +825,14 @@ void Host::finalize() {
   }
 }
 
+void Push::finalize() {
+  if (value->type == unreachable) {
+    type = unreachable;
+  } else {
+    type = none;
+  }
+}
+
 size_t Function::getNumParams() { return params.size(); }
 
 size_t Function::getNumVars() { return vars.size(); }