[EH] Support reading/writing of delegate (#3561)

This adds support for reading/writing of the new `delegate` instruction
in the folded wast format, the stack IR format, the poppy IR format, and
the binary format in Binaryen. We don't have a formal spec written down
yet, but please refer to WebAssembly/exception-handling#137 and
WebAssembly/exception-handling#146 for the informal semantics. In the
current version of spec `delegate` is basically a rethrow, but with
branch-like immediate argument so that it can bypass other
catches/delegates in between.

`delegate` is not represented as a new `Expression`, but it is rather
an option within a `Try` class, like `catch`/`catch_all`.

One special thing about `delegate` is, even though it is written
_within_ a `try` in the folded wat format, like
```wasm
(try
  (do
    ...
  )
  (delegate $l)
)
```
In the unfolded wat format or in the binary format, `delegate` serves as
a scope end instruction so there is no separate `end`:
```wasm
try
  ...
delegate $l
```

`delegate` semantically targets an outer `catch` or `delegate`, but we
write `delegate` target as a `try` label because we only give labels to
block-like scoping expressions. So far we have not given `Try` a label
and used inner blocks or a wrapping block in case a branch targets the
`try`. But in case of `delegate`, it can syntactically only target `try`
and if it targets blocks or loops it is a validation failure.

So after discussions in #3497, we give `Try` a label but this label can
only be targeted by `delegate`s. Unfortunately this makes parsing and
writing of `Try` expression somewhat complicated. Also there is one
special case; if the immediate argument of `try` is the same as the
depth of control flow stack, this means the 'delegate' delegates to the
caller. To handle this case this adds a fake label
`DELEGATE_CALLER_TARGET`, and when writing it back to the wast format
writes it as an immediate value, unlike other cases in which we write
labels.

This uses `DELEGATE_FIELD_SCOPE_NAME_DEF/USE` to represent `try`'s label
and `delegate`'s target. There are many cases that `try` and
`delegate`'s labels need to be treated in the same way as block and
branch labels, such as for hashing or comparing. But there are routines
in which we automatically assume all label uses are branches. I thought
about adding a new kind of defines such as
`DELEGATE_FIELD_TRY_NAME_DEF/USE`, but I think it will also involve some
duplication of existing routines or classes. So at the moment this PR
chooses to use the existing `DELEGATE_FIELD_SCOPE_NAME_DEF/USE` for
`try` and `delegate` labels and makes only necessary amount of changes
in branch-utils. We can revisit this decision later if necessary.

Many of changes to the existing test cases are because now all `try`s
are automatically assigned a label. They will be removed in
`RemoveUnusedNames` pass in the same way as block labels if not targeted
by any delegates.

This only supports reading and writing and has not been tested against
any optimization passes yet.

---

Original unfolded wat file to generate test/try-delegate.wasm:
```wasm
(module
  (event $e)
  (func
    try
      try
      delegate 0
    catch $e
    end)

  (func
    try
      try
      catch $e
        i32.const 0
        drop
        try
        delegate 1
      end
    catch $e
    end
  )
)
```

19 files changed, 422 insertions, 91 deletions

diff --git a/src/ir/ExpressionAnalyzer.cpp b/src/ir/ExpressionAnalyzer.cpp
index 04ef52026..0b0adae9e 100644
--- a/src/ir/ExpressionAnalyzer.cpp
+++ b/src/ir/ExpressionAnalyzer.cpp
@@ -17,6 +17,7 @@
 #include "ir/iteration.h"
 #include "ir/load-utils.h"
 #include "ir/utils.h"
+#include "shared-constants.h"
 #include "support/hash.h"
 #include "support/small_vector.h"
 #include "wasm-traversal.h"
@@ -261,6 +262,9 @@ size_t ExpressionAnalyzer::hash(Expression* curr) {
 
     Hasher(Expression* curr) {
       stack.push_back(curr);
+      // DELEGATE_CALLER_TARGET is a fake target used to denote delegating to
+      // the caller. Add it here to prevent the unknown name error.
+      noteScopeName(DELEGATE_CALLER_TARGET);
 
       while (stack.size() > 0) {
         curr = stack.back();
@@ -327,13 +331,15 @@ size_t ExpressionAnalyzer::hash(Expression* curr) {
       }
     }
     void visitScopeName(Name curr) {
-      // Names are relative, we give the same hash for
-      // (block $x (br $x))
-      // (block $y (br $y))
-      static_assert(sizeof(Index) == sizeof(int32_t),
-                    "wasm64 will need changes here");
-      assert(internalNames.find(curr) != internalNames.end());
-      rehash(digest, internalNames[curr]);
+      if (curr.is()) { // try's delegate target can be null
+        // Names are relative, we give the same hash for
+        // (block $x (br $x))
+        // (block $y (br $y))
+        static_assert(sizeof(Index) == sizeof(int32_t),
+                      "wasm64 will need changes here");
+        assert(internalNames.find(curr) != internalNames.end());
+        rehash(digest, internalNames[curr]);
+      }
     }
     void visitNonScopeName(Name curr) { rehash(digest, uint64_t(curr.str)); }
     void visitType(Type curr) { rehash(digest, curr.getID()); }
diff --git a/src/ir/branch-utils.h b/src/ir/branch-utils.h
index a9561ef07..8a4f02a58 100644
--- a/src/ir/branch-utils.h
+++ b/src/ir/branch-utils.h
@@ -40,9 +40,9 @@ inline bool isBranchReachable(Expression* expr) {
   return true;
 }
 
-// Perform a generic operation on uses of scope names (branch targets) in an
-// expression. The provided function receives a Name& which it can modify if it
-// needs to.
+// Perform a generic operation on uses of scope names (branch + delegate
+// targets) in an expression. The provided function receives a Name& which it
+// can modify if it needs to.
 template<typename T> void operateOnScopeNameUses(Expression* expr, T func) {
 #define DELEGATE_ID expr->_id
 
@@ -83,7 +83,7 @@ void operateOnScopeNameUsesAndSentTypes(Expression* expr, T func) {
     } else if (auto* br = expr->dynCast<BrOn>()) {
       func(name, br->getCastType());
     } else {
-      WASM_UNREACHABLE("bad br type");
+      assert(expr->is<Try>()); // delegate
     }
   });
 }
@@ -135,6 +135,46 @@ inline bool replacePossibleTarget(Expression* branch, Name from, Name to) {
   return worked;
 }
 
+// Replace all delegate targets within the given AST.
+inline void replaceDelegateTargets(Expression* ast, Name from, Name to) {
+  struct Replacer
+    : public PostWalker<Replacer, UnifiedExpressionVisitor<Replacer>> {
+    Name from, to;
+    Replacer(Name from, Name to) : from(from), to(to) {}
+    void visitExpression(Expression* curr) {
+      if (curr->is<Try>()) {
+        operateOnScopeNameUses(curr, [&](Name& name) {
+          if (name == from) {
+            name = to;
+          }
+        });
+      }
+    }
+  };
+  Replacer replacer(from, to);
+  replacer.walk(ast);
+}
+
+// Replace all branch targets within the given AST.
+inline void replaceBranchTargets(Expression* ast, Name from, Name to) {
+  struct Replacer
+    : public PostWalker<Replacer, UnifiedExpressionVisitor<Replacer>> {
+    Name from, to;
+    Replacer(Name from, Name to) : from(from), to(to) {}
+    void visitExpression(Expression* curr) {
+      if (Properties::isBranch(curr)) {
+        operateOnScopeNameUses(curr, [&](Name& name) {
+          if (name == from) {
+            name = to;
+          }
+        });
+      }
+    }
+  };
+  Replacer replacer(from, to);
+  replacer.walk(ast);
+}
+
 // Returns the set of targets to which we branch that are
 // outside of an expression.
 inline NameSet getExitingBranches(Expression* ast) {
diff --git a/src/ir/properties.h b/src/ir/properties.h
index b60c74d98..8ae7befba 100644
--- a/src/ir/properties.h
+++ b/src/ir/properties.h
@@ -69,13 +69,15 @@ inline bool isControlFlowStructure(Expression* curr) {
          curr->is<Try>();
 }
 
-// Check if an expression is a control flow construct with a name,
-// which implies it may have breaks to it.
+// Check if an expression is a control flow construct with a name, which implies
+// it may have breaks or delegates to it.
 inline bool isNamedControlFlow(Expression* curr) {
   if (auto* block = curr->dynCast<Block>()) {
     return block->name.is();
   } else if (auto* loop = curr->dynCast<Loop>()) {
     return loop->name.is();
+  } else if (auto* try_ = curr->dynCast<Try>()) {
+    return try_->name.is();
   }
   return false;
 }
@@ -104,6 +106,10 @@ inline bool isConstantExpression(const Expression* curr) {
   return false;
 }
 
+inline bool isBranch(const Expression* curr) {
+  return curr->is<Break>() || curr->is<Switch>() || curr->is<BrOn>();
+}
+
 inline Literal getLiteral(const Expression* curr) {
   if (auto* c = curr->dynCast<Const>()) {
     return c->value;
diff --git a/src/passes/Poppify.cpp b/src/passes/Poppify.cpp
index b0d07e60c..2ab222697 100644
--- a/src/passes/Poppify.cpp
+++ b/src/passes/Poppify.cpp
@@ -128,6 +128,7 @@ struct Poppifier : BinaryenIRWriter<Poppifier> {
   void emitIfElse(If* curr);
   void emitCatch(Try* curr, Index i);
   void emitCatchAll(Try* curr);
+  void emitDelegate(Try* curr);
   void emitScopeEnd(Expression* curr);
   void emitFunctionEnd();
   void emitUnreachable();
@@ -272,6 +273,13 @@ void Poppifier::emitCatchAll(Try* curr) {
   scopeStack.emplace_back(Scope::Catch);
 }
 
+void Poppifier::emitDelegate(Try* curr) {
+  auto& scope = scopeStack.back();
+  assert(scope.kind == Scope::Try);
+  patchScope(curr->body);
+  scopeStack.back().instrs.push_back(curr);
+}
+
 void Poppifier::emitScopeEnd(Expression* curr) {
   switch (scopeStack.back().kind) {
     case Scope::Block:
diff --git a/src/passes/Print.cpp b/src/passes/Print.cpp
index e49735af0..9b59de444 100644
--- a/src/passes/Print.cpp
+++ b/src/passes/Print.cpp
@@ -1764,6 +1764,10 @@ struct PrintExpressionContents
   void visitRefEq(RefEq* curr) { printMedium(o, "ref.eq"); }
   void visitTry(Try* curr) {
     printMedium(o, "try");
+    if (curr->name.is()) {
+      o << ' ';
+      printName(curr->name, o);
+    }
     if (curr->type.isConcrete()) {
       o << ' ' << ResultType(curr->type);
     }
@@ -1955,6 +1959,9 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
   Function::DebugLocation lastPrintedLocation;
   bool debugInfo;
 
+  // Used to print delegate's depth argument when it throws to the caller
+  int controlFlowDepth = 0;
+
   PrintSExpression(std::ostream& o) : o(o) {
     setMinify(false);
     if (!full) {
@@ -2100,6 +2107,9 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
         break; // that's all we can recurse, start to unwind
       }
     }
+
+    int startControlFlowDepth = controlFlowDepth;
+    controlFlowDepth += stack.size();
     auto* top = stack.back();
     while (stack.size() > 0) {
       curr = stack.back();
@@ -2129,8 +2139,10 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
         o << ' ' << curr->name;
       }
     }
+    controlFlowDepth = startControlFlowDepth;
   }
   void visitIf(If* curr) {
+    controlFlowDepth++;
     o << '(';
     printExpressionContents(curr);
     incIndent();
@@ -2147,8 +2159,10 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
     if (full) {
       o << " ;; end if";
     }
+    controlFlowDepth--;
   }
   void visitLoop(Loop* curr) {
+    controlFlowDepth++;
     o << '(';
     printExpressionContents(curr);
     incIndent();
@@ -2160,6 +2174,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
         o << ' ' << curr->name;
       }
     }
+    controlFlowDepth--;
   }
   void visitBreak(Break* curr) {
     o << '(';
@@ -2490,13 +2505,28 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
   //  (do
   //   ...
   //  )
-  //  (catch
-  //   ...
+  //  (catch $e
+  //    ...
+  //  )
+  //  ...
+  //  (catch_all
+  //    ...
   //  )
   // )
-  // The parenthesis wrapping 'catch' is just a syntax and does not affect
-  // nested depths of instructions within.
+  // The parenthesis wrapping do/catch/catch_all is just a syntax and does not
+  // affect nested depths of instructions within.
+  //
+  // try-delegate is written in the forded format as
+  // (try
+  //  (do
+  //    ...
+  //  )
+  //  (delegate $label)
+  // )
+  // When the 'delegate' delegates to the caller, we write the argument as an
+  // immediate.
   void visitTry(Try* curr) {
+    controlFlowDepth++;
     o << '(';
     printExpressionContents(curr);
     incIndent();
@@ -2521,12 +2551,26 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
     if (curr->hasCatchAll()) {
       doIndent(o, indent);
       printDebugDelimiterLocation(curr, curr->catchEvents.size());
-      o << "(catch_all";
+      o << '(';
+      printMedium(o, "catch_all");
       incIndent();
       maybePrintImplicitBlock(curr->catchBodies.back(), true);
       decIndent();
       o << "\n";
     }
+    controlFlowDepth--;
+
+    if (curr->isDelegate()) {
+      doIndent(o, indent);
+      o << '(';
+      printMedium(o, "delegate ");
+      if (curr->delegateTarget == DELEGATE_CALLER_TARGET) {
+        o << controlFlowDepth;
+      } else {
+        printName(curr->delegateTarget, o);
+      }
+      o << ")\n";
+    }
     decIndent();
     if (full) {
       o << " ;; end try";
@@ -2913,6 +2957,7 @@ struct PrintSExpression : public OverriddenVisitor<PrintSExpression> {
       } else {
         printFullLine(curr->body);
       }
+      assert(controlFlowDepth == 0);
     } else {
       // Print the stack IR.
       printStackIR(curr->stackIR.get(), o, curr);
@@ -3324,6 +3369,11 @@ printStackInst(StackInst* inst, std::ostream& o, Function* func) {
       printMedium(o, "catch_all");
       break;
     }
+    case StackInst::Delegate: {
+      printMedium(o, "delegate ");
+      printName(inst->origin->cast<Try>()->delegateTarget, o);
+      break;
+    }
     default:
       WASM_UNREACHABLE("unexpeted op");
   }
@@ -3339,6 +3389,7 @@ printStackIR(StackIR* ir, std::ostream& o, Function* func) {
     }
   };
 
+  int controlFlowDepth = 0;
   // Stack to track indices of catches within a try
   SmallVector<Index, 4> catchIndexStack;
   for (Index i = 0; i < (*ir).size(); i++) {
@@ -3364,6 +3415,7 @@ printStackIR(StackIR* ir, std::ostream& o, Function* func) {
       case StackInst::BlockBegin:
       case StackInst::IfBegin:
       case StackInst::LoopBegin: {
+        controlFlowDepth++;
         doIndent();
         PrintExpressionContents(func, o).visit(inst->origin);
         indent++;
@@ -3375,6 +3427,7 @@ printStackIR(StackIR* ir, std::ostream& o, Function* func) {
       case StackInst::BlockEnd:
       case StackInst::IfEnd:
       case StackInst::LoopEnd: {
+        controlFlowDepth--;
         indent--;
         doIndent();
         printMedium(o, "end");
@@ -3403,11 +3456,25 @@ printStackIR(StackIR* ir, std::ostream& o, Function* func) {
         indent++;
         break;
       }
+      case StackInst::Delegate: {
+        controlFlowDepth--;
+        indent--;
+        doIndent();
+        printMedium(o, "delegate ");
+        Try* curr = inst->origin->cast<Try>();
+        if (curr->delegateTarget == DELEGATE_CALLER_TARGET) {
+          o << controlFlowDepth;
+        } else {
+          printName(curr->delegateTarget, o);
+        }
+        break;
+      }
       default:
         WASM_UNREACHABLE("unexpeted op");
     }
     std::cout << '\n';
   }
+  assert(controlFlowDepth == 0);
   return o;
 }
 
diff --git a/src/passes/RemoveUnusedNames.cpp b/src/passes/RemoveUnusedNames.cpp
index 64640aefe..53da00733 100644
--- a/src/passes/RemoveUnusedNames.cpp
+++ b/src/passes/RemoveUnusedNames.cpp
@@ -83,6 +83,8 @@ struct RemoveUnusedNames
     }
   }
 
+  void visitTry(Try* curr) { handleBreakTarget(curr->name); }
+
   void visitFunction(Function* curr) { assert(branchesSeen.empty()); }
 };
 
diff --git a/src/passes/StackIR.cpp b/src/passes/StackIR.cpp
index 0732a6499..6d163d897 100644
--- a/src/passes/StackIR.cpp
+++ b/src/passes/StackIR.cpp
@@ -258,6 +258,7 @@ private:
       case StackInst::LoopEnd:
       case StackInst::Catch:
       case StackInst::CatchAll:
+      case StackInst::Delegate:
       case StackInst::TryEnd: {
         return true;
       }
@@ -284,7 +285,8 @@ private:
       case StackInst::BlockEnd:
       case StackInst::IfEnd:
       case StackInst::LoopEnd:
-      case StackInst::TryEnd: {
+      case StackInst::TryEnd:
+      case StackInst::Delegate: {
         return true;
       }
       default: { return false; }
diff --git a/src/shared-constants.h b/src/shared-constants.h
index 569fd792d..5520f15ac 100644
--- a/src/shared-constants.h
+++ b/src/shared-constants.h
@@ -60,6 +60,7 @@ extern Name CASE;
 extern Name BR;
 extern Name FUNCREF;
 extern Name FAKE_RETURN;
+extern Name DELEGATE_CALLER_TARGET;
 extern Name MUT;
 extern Name SPECTEST;
 extern Name PRINT;
diff --git a/src/wasm-binary.h b/src/wasm-binary.h
index a4d41530e..c2a771a7d 100644
--- a/src/wasm-binary.h
+++ b/src/wasm-binary.h
@@ -1027,6 +1027,7 @@ enum ASTNodes {
   Try = 0x06,
   Catch = 0x07,
   CatchAll = 0x05,
+  Delegate = 0x18,
   Throw = 0x08,
   Rethrow = 0x09,
 
@@ -1417,6 +1418,8 @@ public:
   // the names that breaks target. this lets us know if a block has breaks to it
   // or not.
   std::unordered_set<Name> breakTargetNames;
+  // the names that delegates target.
+  std::unordered_set<Name> delegateTargetNames;
 
   std::vector<Expression*> expressionStack;
 
@@ -1521,6 +1524,7 @@ public:
   Expression* getBlockOrSingleton(Type type);
 
   BreakTarget getBreakTarget(int32_t offset);
+  Name getDelegateTargetName(int32_t offset);
 
   void readMemoryAccess(Address& alignment, Address& offset);
 
diff --git a/src/wasm-delegations-fields.h b/src/wasm-delegations-fields.h
index 033da6314..9677aa4de 100644
--- a/src/wasm-delegations-fields.h
+++ b/src/wasm-delegations-fields.h
@@ -515,8 +515,10 @@ switch (DELEGATE_ID) {
   }
   case Expression::Id::TryId: {
     DELEGATE_START(Try);
+    DELEGATE_FIELD_SCOPE_NAME_USE(Try, delegateTarget);
     DELEGATE_FIELD_CHILD_VECTOR(Try, catchBodies);
     DELEGATE_FIELD_NAME_VECTOR(Try, catchEvents);
+    DELEGATE_FIELD_SCOPE_NAME_DEF(Try, name);
     DELEGATE_FIELD_CHILD(Try, body);
     DELEGATE_END(Try);
     break;
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index 8a92c0935..92bc55d0a 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -242,7 +242,8 @@ private:
       i++;
     }
   }
-  Name getLabel(Element& s);
+  enum class LabelType { Break, Delegate };
+  Name getLabel(Element& s, LabelType labelType = LabelType::Break);
   Expression* makeBreak(Element& s);
   Expression* makeBreakTable(Element& s);
   Expression* makeReturn(Element& s);
diff --git a/src/wasm-stack.h b/src/wasm-stack.h
index bd44ed72e..7f94573fa 100644
--- a/src/wasm-stack.h
+++ b/src/wasm-stack.h
@@ -71,6 +71,7 @@ public:
     TryBegin,   // the beginning of a try
     Catch,      // the catch within a try
     CatchAll,   // the catch_all within a try
+    Delegate,   // the delegate within a try
     TryEnd      // the ending of a try
   } op;
 
@@ -109,6 +110,7 @@ public:
   void emitIfElse(If* curr);
   void emitCatch(Try* curr, Index i);
   void emitCatchAll(Try* curr);
+  void emitDelegate(Try* curr);
   // emit an end at the end of a block/loop/if/try
   void emitScopeEnd(Expression* curr);
   // emit an end at the end of a function
@@ -169,6 +171,9 @@ private:
   void emitCatchAll(Try* curr) {
     static_cast<SubType*>(this)->emitCatchAll(curr);
   }
+  void emitDelegate(Try* curr) {
+    static_cast<SubType*>(this)->emitDelegate(curr);
+  }
   void emitScopeEnd(Expression* curr) {
     static_cast<SubType*>(this)->emitScopeEnd(curr);
   }
@@ -343,7 +348,11 @@ template<typename SubType> void BinaryenIRWriter<SubType>::visitTry(Try* curr) {
     emitCatchAll(curr);
     visitPossibleBlockContents(curr->catchBodies.back());
   }
-  emitScopeEnd(curr);
+  if (curr->isDelegate()) {
+    emitDelegate(curr);
+  } else {
+    emitScopeEnd(curr);
+  }
   if (curr->type == Type::unreachable) {
     emitUnreachable();
   }
@@ -375,6 +384,7 @@ public:
   void emitIfElse(If* curr) { writer.emitIfElse(curr); }
   void emitCatch(Try* curr, Index i) { writer.emitCatch(curr, i); }
   void emitCatchAll(Try* curr) { writer.emitCatchAll(curr); }
+  void emitDelegate(Try* curr) { writer.emitDelegate(curr); }
   void emitScopeEnd(Expression* curr) { writer.emitScopeEnd(curr); }
   void emitFunctionEnd() {
     if (func->epilogLocation.size()) {
@@ -414,6 +424,9 @@ public:
   void emitCatchAll(Try* curr) {
     stackIR.push_back(makeStackInst(StackInst::CatchAll, curr));
   }
+  void emitDelegate(Try* curr) {
+    stackIR.push_back(makeStackInst(StackInst::Delegate, curr));
+  }
   void emitFunctionEnd() {}
   void emitUnreachable() {
     stackIR.push_back(makeStackInst(Builder(module).makeUnreachable()));
diff --git a/src/wasm-type.h b/src/wasm-type.h
index fe1b832bc..4188c438d 100644
--- a/src/wasm-type.h
+++ b/src/wasm-type.h
@@ -137,7 +137,6 @@ public:
   bool isRef() const;
   bool isFunction() const;
   bool isData() const;
-  bool isException() const;
   bool isNullable() const;
   bool isRtt() const;
   bool isStruct() const;
diff --git a/src/wasm.h b/src/wasm.h
index 7fd284756..876a9bfa7 100644
--- a/src/wasm.h
+++ b/src/wasm.h
@@ -1306,13 +1306,17 @@ class Try : public SpecificExpression<Expression::TryId> {
 public:
   Try(MixedArena& allocator) : catchEvents(allocator), catchBodies(allocator) {}
 
+  Name name; // label that can only be targeted by 'delegate's
   Expression* body;
   ArenaVector<Name> catchEvents;
   ExpressionList catchBodies;
+  Name delegateTarget; // target try's label
 
   bool hasCatchAll() const {
     return catchBodies.size() - catchEvents.size() == 1;
   }
+  bool isCatch() const { return !catchBodies.empty(); }
+  bool isDelegate() const { return delegateTarget.is(); }
   void finalize();
   void finalize(Type type_);
 };
diff --git a/src/wasm/wasm-binary.cpp b/src/wasm/wasm-binary.cpp
index f3ec376d1..878293caa 100644
--- a/src/wasm/wasm-binary.cpp
+++ b/src/wasm/wasm-binary.cpp
@@ -1918,7 +1918,9 @@ void WasmBinaryBuilder::readFunctions() {
       debugLocation.clear();
       willBeIgnored = false;
       // process body
-      assert(breakTargetNames.size() == 0);
+      assert(breakStack.empty());
+      assert(breakTargetNames.empty());
+      assert(delegateTargetNames.empty());
       assert(breakStack.empty());
       assert(expressionStack.empty());
       assert(controlFlowStack.empty());
@@ -1926,8 +1928,9 @@ void WasmBinaryBuilder::readFunctions() {
       assert(depth == 0);
       func->body = getBlockOrSingleton(func->sig.results);
       assert(depth == 0);
-      assert(breakStack.size() == 0);
-      assert(breakTargetNames.size() == 0);
+      assert(breakStack.empty());
+      assert(breakTargetNames.empty());
+      assert(delegateTargetNames.empty());
       if (!expressionStack.empty()) {
         throwError("stack not empty on function exit");
       }
@@ -2210,7 +2213,8 @@ void WasmBinaryBuilder::processExpressions() {
       }
       auto peek = input[pos];
       if (peek == BinaryConsts::End || peek == BinaryConsts::Else ||
-          peek == BinaryConsts::Catch || peek == BinaryConsts::CatchAll) {
+          peek == BinaryConsts::Catch || peek == BinaryConsts::CatchAll ||
+          peek == BinaryConsts::Delegate) {
         BYN_TRACE("== processExpressions finished with unreachable"
                   << std::endl);
         lastSeparator = BinaryConsts::ASTNodes(peek);
@@ -2987,6 +2991,14 @@ BinaryConsts::ASTNodes WasmBinaryBuilder::readExpression(Expression*& curr) {
       }
       break;
     }
+    case BinaryConsts::Delegate: {
+      curr = nullptr;
+      if (DWARF && currFunction) {
+        assert(!controlFlowStack.empty());
+        controlFlowStack.pop_back();
+      }
+      break;
+    }
     case BinaryConsts::RefNull:
       visitRefNull((curr = allocator.alloc<RefNull>())->cast<RefNull>());
       break;
@@ -3376,7 +3388,8 @@ Expression* WasmBinaryBuilder::getBlockOrSingleton(Type type) {
   block->name = label;
   block->finalize(type);
   // maybe we don't need a block here?
-  if (breakTargetNames.find(block->name) == breakTargetNames.end()) {
+  if (breakTargetNames.find(block->name) == breakTargetNames.end() &&
+      delegateTargetNames.find(block->name) == delegateTargetNames.end()) {
     block->name = Name();
     if (block->list.size() == 1) {
       return block->list[0];
@@ -3452,6 +3465,28 @@ WasmBinaryBuilder::getBreakTarget(int32_t offset) {
   return ret;
 }
 
+Name WasmBinaryBuilder::getDelegateTargetName(int32_t offset) {
+  BYN_TRACE("getDelegateTarget " << offset << std::endl);
+  // We always start parsing a function by creating a block label and pushing it
+  // in breakStack in getBlockOrSingleton, so if a 'delegate''s target is that
+  // block, it does not mean it targets that block; it throws to the caller.
+  if (breakStack.size() - 1 == size_t(offset)) {
+    return DELEGATE_CALLER_TARGET;
+  }
+  size_t index = breakStack.size() - 1 - offset;
+  if (index > breakStack.size()) {
+    throwError("bad delegate index (high)");
+  }
+  BYN_TRACE("delegate target " << breakStack[index].name << std::endl);
+  auto& ret = breakStack[index];
+  // if the delegate is in literally unreachable code, then we will not emit it
+  // anyhow, so do not note that the target has delegate to it
+  if (!willBeIgnored) {
+    delegateTargetNames.insert(ret.name);
+  }
+  return ret.name;
+}
+
 void WasmBinaryBuilder::visitBreak(Break* curr, uint8_t code) {
   BYN_TRACE("zz node: Break, code " << int32_t(code) << std::endl);
   BreakTarget target = getBreakTarget(getU32LEB());
@@ -5746,58 +5781,13 @@ void WasmBinaryBuilder::visitTryOrTryInBlock(Expression*& out) {
   curr->type = getType();
   curr->body = getBlockOrSingleton(curr->type);
   if (lastSeparator != BinaryConsts::Catch &&
-      lastSeparator != BinaryConsts::CatchAll) {
+      lastSeparator != BinaryConsts::CatchAll &&
+      lastSeparator != BinaryConsts::Delegate) {
     throwError("No catch instruction within a try scope");
   }
 
-  // For simplicity, we create an inner block within the catch body too, but the
-  // one within the 'catch' *must* be omitted when we write out the binary back
-  // later, because the 'catch' instruction pushes a value onto the stack and
-  // the inner block does not support block input parameters without multivalue
-  // support.
-  // try
-  //   ...
-  // catch    ;; Pushes a value onto the stack
-  //   block  ;; Inner block. Should be deleted when writing binary!
-  //     use the pushed value
-  //   end
-  // end
-  //
-  // But when input binary code is like
-  // try
-  //   ...
-  // catch
-  //   br 0
-  // end
-  //
-  // 'br 0' accidentally happens to target the inner block, creating code like
-  // this in Binaryen IR, making the inner block not deletable, resulting in a
-  // validation error:
-  // (try
-  //   ...
-  //   (catch
-  //     (block $label0 ;; Cannot be deleted, because there's a branch to this
-  //       ...
-  //       (br $label0)
-  //     )
-  //   )
-  // )
-  //
-  // When this happens, we fix this by creating a block that wraps the whole
-  // try-catch, and making the branches target that block instead, like this:
-  // (block $label  ;; New enclosing block, new target for the branch
-  //   (try
-  //     ...
-  //     (catch
-  //       (block   ;; Now this can be deleted when writing binary
-  //         ...
-  //         (br $label0)
-  //       )
-  //     )
-  //   )
-  // )
-
   Builder builder(wasm);
+  // A nameless label shared by all catch body blocks
   Name catchLabel = getNextLabel();
   breakStack.push_back({catchLabel, curr->type});
 
@@ -5839,8 +5829,84 @@ void WasmBinaryBuilder::visitTryOrTryInBlock(Expression*& out) {
       readCatchBody(Type::none);
     }
   }
+  breakStack.pop_back();
+
+  if (lastSeparator == BinaryConsts::Delegate) {
+    curr->delegateTarget = getDelegateTargetName(getU32LEB());
+  }
+
+  // For simplicity, we make try's labels only can be targeted by delegates, and
+  // delegates can only target try's labels. (If they target blocks or loops, it
+  // is a validation failure.) Because we create an inner block within each try
+  // and catch body, if any delegate targets those inner blocks, we should make
+  // them target the try's label instead.
+  curr->name = getNextLabel();
+  if (auto* block = curr->body->dynCast<Block>()) {
+    if (block->name.is()) {
+      if (delegateTargetNames.find(block->name) != delegateTargetNames.end()) {
+        BranchUtils::replaceDelegateTargets(block, block->name, curr->name);
+        delegateTargetNames.erase(block->name);
+      }
+      // maybe we don't need a block here?
+      if (block->list.size() == 1) {
+        curr->body = block->list[0];
+      }
+    }
+  }
+  if (delegateTargetNames.find(catchLabel) != delegateTargetNames.end()) {
+    for (auto* catchBody : curr->catchBodies) {
+      BranchUtils::replaceDelegateTargets(catchBody, catchLabel, curr->name);
+    }
+    delegateTargetNames.erase(catchLabel);
+  }
   curr->finalize(curr->type);
 
+  // For simplicity, we create an inner block within the catch body too, but the
+  // one within the 'catch' *must* be omitted when we write out the binary back
+  // later, because the 'catch' instruction pushes a value onto the stack and
+  // the inner block does not support block input parameters without multivalue
+  // support.
+  // try
+  //   ...
+  // catch $e   ;; Pushes value(s) onto the stack
+  //   block  ;; Inner block. Should be deleted when writing binary!
+  //     use the pushed value
+  //   end
+  // end
+  //
+  // But when input binary code is like
+  // try
+  //   ...
+  // catch $e
+  //   br 0
+  // end
+  //
+  // 'br 0' accidentally happens to target the inner block, creating code like
+  // this in Binaryen IR, making the inner block not deletable, resulting in a
+  // validation error:
+  // (try
+  //   ...
+  //   (catch $e
+  //     (block $label0 ;; Cannot be deleted, because there's a branch to this
+  //       ...
+  //       (br $label0)
+  //     )
+  //   )
+  // )
+  //
+  // When this happens, we fix this by creating a block that wraps the whole
+  // try-catch, and making the branches target that block instead, like this:
+  // (block $label  ;; New enclosing block, new target for the branch
+  //   (try
+  //     ...
+  //     (catch $e
+  //       (block   ;; Now this can be deleted when writing binary
+  //         ...
+  //         (br $label0)
+  //       )
+  //     )
+  //   )
+  // )
   if (breakTargetNames.find(catchLabel) == breakTargetNames.end()) {
     out = curr;
   } else {
@@ -5848,7 +5914,6 @@ void WasmBinaryBuilder::visitTryOrTryInBlock(Expression*& out) {
     auto* block = builder.makeBlock(catchLabel, curr);
     out = block;
   }
-  breakStack.pop_back();
   breakTargetNames.erase(catchLabel);
 }
 
diff --git a/src/wasm/wasm-s-parser.cpp b/src/wasm/wasm-s-parser.cpp
index bcce3993e..d2b24fbed 100644
--- a/src/wasm/wasm-s-parser.cpp
+++ b/src/wasm/wasm-s-parser.cpp
@@ -1859,7 +1859,7 @@ Expression* SExpressionWasmBuilder::makeCallIndirect(Element& s,
   return ret;
 }
 
-Name SExpressionWasmBuilder::getLabel(Element& s) {
+Name SExpressionWasmBuilder::getLabel(Element& s, LabelType labelType) {
   if (s.dollared()) {
     return nameMapper.sourceToUnique(s.str());
   } else {
@@ -1876,10 +1876,14 @@ Name SExpressionWasmBuilder::getLabel(Element& s) {
       throw ParseException("invalid label", s.line, s.col);
     }
     if (offset == nameMapper.labelStack.size()) {
-      // a break to the function's scope. this means we need an automatic block,
-      // with a name
-      brokeToAutoBlock = true;
-      return FAKE_RETURN;
+      if (labelType == LabelType::Break) {
+        // a break to the function's scope. this means we need an automatic
+        // block, with a name
+        brokeToAutoBlock = true;
+        return FAKE_RETURN;
+      }
+      // This is a delegate that delegates to the caller
+      return DELEGATE_CALLER_TARGET;
     }
     return nameMapper.labelStack[nameMapper.labelStack.size() - 1 - offset];
   }
@@ -1975,12 +1979,13 @@ Expression* SExpressionWasmBuilder::makeRefEq(Element& s) {
   return ret;
 }
 
-// try-catch-end is written in the folded wast format as
+// try can be either in the form of try-catch or try-delegate.
+// try-catch is written in the folded wast format as
 // (try
 //  (do
 //    ...
 //  )
-//  (catch
+//  (catch $e
 //    ...
 //  )
 //  ...
@@ -1991,6 +1996,14 @@ Expression* SExpressionWasmBuilder::makeRefEq(Element& s) {
 // Any number of catch blocks can exist, including none. Zero or one catch_all
 // block can exist, and if it does, it should be at the end. There should be at
 // least one catch or catch_all body per try.
+//
+// try-delegate is written in the folded format as
+// (try
+//  (do
+//    ...
+//  )
+//  (delegate $label)
+// )
 Expression* SExpressionWasmBuilder::makeTry(Element& s) {
   auto ret = allocator.alloc<Try>();
   Index i = 1;
@@ -2001,7 +2014,7 @@ Expression* SExpressionWasmBuilder::makeTry(Element& s) {
   } else {
     sName = "try";
   }
-  auto label = nameMapper.pushLabelName(sName);
+  ret->name = nameMapper.pushLabelName(sName);
   Type type = parseOptionalResultType(s, i); // signature
 
   if (!elementStartsWith(*s[i], "do")) {
@@ -2027,21 +2040,38 @@ Expression* SExpressionWasmBuilder::makeTry(Element& s) {
     ret->catchBodies.push_back(makeMaybeBlock(*s[i++], 1, type));
   }
 
+  // 'delegate' cannot target its own try. So we pop the name here.
+  nameMapper.popLabelName(ret->name);
+
+  if (i < s.size() && elementStartsWith(*s[i], "delegate")) {
+    Element& inner = *s[i++];
+    if (inner.size() != 2) {
+      throw ParseException("invalid delegate", inner.line, inner.col);
+    }
+    ret->delegateTarget = getLabel(*inner[1], LabelType::Delegate);
+  }
+
   if (i != s.size()) {
     throw ParseException(
       "there should be at most one catch_all block at the end", s.line, s.col);
   }
-  if (ret->catchBodies.empty()) {
-    throw ParseException("no catch bodies", s.line, s.col);
+  if (ret->catchBodies.empty() && !ret->isDelegate()) {
+    throw ParseException("no catch bodies or delegate", s.line, s.col);
   }
 
   ret->finalize(type);
-  nameMapper.popLabelName(label);
+
   // create a break target if we must
-  if (BranchUtils::BranchSeeker::has(ret, label)) {
+  if (BranchUtils::BranchSeeker::has(ret, ret->name)) {
     auto* block = allocator.alloc<Block>();
-    block->name = label;
+    // We create a different name for the wrapping block, because try's name can
+    // be used by internal delegates
+    block->name = nameMapper.pushLabelName(sName);
+    // For simplicity, try's name canonly be targeted by delegates. Make the
+    // branches target the new wrapping block instead.
+    BranchUtils::replaceBranchTargets(ret, ret->name, block->name);
     block->list.push_back(ret);
+    nameMapper.popLabelName(block->name);
     block->finalize(type);
     return block;
   }
diff --git a/src/wasm/wasm-stack.cpp b/src/wasm/wasm-stack.cpp
index 00b1e5368..cb9d94093 100644
--- a/src/wasm/wasm-stack.cpp
+++ b/src/wasm/wasm-stack.cpp
@@ -1904,7 +1904,7 @@ void BinaryInstWriter::visitRefEq(RefEq* curr) {
 }
 
 void BinaryInstWriter::visitTry(Try* curr) {
-  breakStack.emplace_back(IMPOSSIBLE_CONTINUE);
+  breakStack.push_back(curr->name);
   o << int8_t(BinaryConsts::Try);
   emitResultType(curr->type);
 }
@@ -1924,6 +1924,13 @@ void BinaryInstWriter::emitCatchAll(Try* curr) {
   o << int8_t(BinaryConsts::CatchAll);
 }
 
+void BinaryInstWriter::emitDelegate(Try* curr) {
+  assert(!breakStack.empty());
+  breakStack.pop_back();
+  o << int8_t(BinaryConsts::Delegate)
+    << U32LEB(getBreakIndex(curr->delegateTarget));
+}
+
 void BinaryInstWriter::visitThrow(Throw* curr) {
   o << int8_t(BinaryConsts::Throw) << U32LEB(parent.getEventIndex(curr->event));
 }
@@ -2216,6 +2223,9 @@ void BinaryInstWriter::emitMemoryAccess(size_t alignment,
 }
 
 int32_t BinaryInstWriter::getBreakIndex(Name name) { // -1 if not found
+  if (name == DELEGATE_CALLER_TARGET) {
+    return breakStack.size();
+  }
   for (int i = breakStack.size() - 1; i >= 0; i--) {
     if (breakStack[i] == name) {
       return breakStack.size() - 1 - i;
@@ -2321,6 +2331,10 @@ void StackIRToBinaryWriter::write() {
         writer.emitCatchAll(inst->origin->cast<Try>());
         break;
       }
+      case StackInst::Delegate: {
+        writer.emitDelegate(inst->origin->cast<Try>());
+        break;
+      }
       default:
         WASM_UNREACHABLE("unexpected op");
     }
diff --git a/src/wasm/wasm-validator.cpp b/src/wasm/wasm-validator.cpp
index 276b9602f..beb994390 100644
--- a/src/wasm/wasm-validator.cpp
+++ b/src/wasm/wasm-validator.cpp
@@ -236,6 +236,7 @@ struct FunctionValidator : public WalkerPass<PostWalker<FunctionValidator>> {
   };
 
   std::unordered_map<Name, BreakInfo> breakInfos;
+  std::unordered_set<Name> delegateTargetNames;
 
   std::set<Type> returnTypes; // types used in returns
 
@@ -276,11 +277,52 @@ public:
   void visitLoop(Loop* curr);
   void visitIf(If* curr);
 
+  static void visitPreTry(FunctionValidator* self, Expression** currp) {
+    auto* curr = (*currp)->cast<Try>();
+    if (curr->name.is()) {
+      self->delegateTargetNames.insert(curr->name);
+    }
+  }
+
+  // We remove try's label before proceeding to verify catch bodies because the
+  // following is a validation failure:
+  // (try $l0
+  //   (do ... )
+  //   (catch $e
+  //     (try
+  //       (do ...)
+  //       (delegate $l0) ;; validation failure
+  //     )
+  //   )
+  // )
+  // Unlike branches, if delegate's target 'catch' is located above the
+  // delegate, it is a validation failure.
+  static void visitPreCatch(FunctionValidator* self, Expression** currp) {
+    auto* curr = (*currp)->cast<Try>();
+    if (curr->name.is()) {
+      self->delegateTargetNames.erase(curr->name);
+    }
+  }
+
   // override scan to add a pre and a post check task to all nodes
   static void scan(FunctionValidator* self, Expression** currp) {
+    auto* curr = *currp;
+    // Treat 'Try' specially because we need to run visitPreCatch between the
+    // try body and catch bodies
+    if (curr->is<Try>()) {
+      self->pushTask(doVisitTry, currp);
+      auto& list = curr->cast<Try>()->catchBodies;
+      for (int i = int(list.size()) - 1; i >= 0; i--) {
+        self->pushTask(scan, &list[i]);
+      }
+      self->pushTask(visitPreCatch, currp);
+      self->pushTask(scan, &curr->cast<Try>()->body);
+      self->pushTask(visitPreTry, currp);
+      return;
+    }
+
     PostWalker<FunctionValidator>::scan(self, currp);
 
-    auto* curr = *currp;
     if (curr->is<Block>()) {
       self->pushTask(visitPreBlock, currp);
     }
@@ -334,6 +376,7 @@ public:
   void visitRefIs(RefIs* curr);
   void visitRefFunc(RefFunc* curr);
   void visitRefEq(RefEq* curr);
+  void noteDelegate(Name name, Expression* curr);
   void visitTry(Try* curr);
   void visitThrow(Throw* curr);
   void visitRethrow(Rethrow* curr);
@@ -767,6 +810,7 @@ void FunctionValidator::noteBreak(Name name, Type valueType, Expression* curr) {
     }
   }
 }
+
 void FunctionValidator::visitBreak(Break* curr) {
   noteBreak(curr->name, curr->value, curr);
   if (curr->value) {
@@ -2029,6 +2073,14 @@ void FunctionValidator::visitRefEq(RefEq* curr) {
     "ref.eq's right argument should be a subtype of eqref");
 }
 
+void FunctionValidator::noteDelegate(Name name, Expression* curr) {
+  if (name != DELEGATE_CALLER_TARGET) {
+    shouldBeTrue(delegateTargetNames.find(name) != delegateTargetNames.end(),
+                 curr,
+                 "all delegate targets must be valid");
+  }
+}
+
 void FunctionValidator::visitTry(Try* curr) {
   shouldBeTrue(getModule()->features.hasExceptionHandling(),
                curr,
@@ -2061,6 +2113,17 @@ void FunctionValidator::visitTry(Try* curr) {
   shouldBeTrue(curr->catchBodies.size() - curr->catchEvents.size() <= 1,
                curr,
                "the number of catch blocks and events do not match");
+
+  shouldBeFalse(curr->isCatch() && curr->isDelegate(),
+                curr,
+                "try cannot have both catch and delegate at the same time");
+  shouldBeTrue(curr->isCatch() || curr->isDelegate(),
+               curr,
+               "try should have either catches or a delegate");
+
+  if (curr->isDelegate()) {
+    noteDelegate(curr->delegateTarget, curr);
+  }
 }
 
 void FunctionValidator::visitThrow(Throw* curr) {
@@ -2470,6 +2533,9 @@ void FunctionValidator::visitFunction(Function* curr) {
 
   shouldBeTrue(
     breakInfos.empty(), curr->body, "all named break targets must exist");
+  shouldBeTrue(delegateTargetNames.empty(),
+               curr->body,
+               "all named delegate targets must exist");
   returnTypes.clear();
   labelNames.clear();
   // validate optional local names
diff --git a/src/wasm/wasm.cpp b/src/wasm/wasm.cpp
index 7bf9b8604..92e03f579 100644
--- a/src/wasm/wasm.cpp
+++ b/src/wasm/wasm.cpp
@@ -88,6 +88,7 @@ Name CASE("case");
 Name BR("br");
 Name FUNCREF("funcref");
 Name FAKE_RETURN("fake_return_waka123");
+Name DELEGATE_CALLER_TARGET("delegate_caller_target_waka123");
 Name MUT("mut");
 Name SPECTEST("spectest");
 Name PRINT("print");