Unwinding as a modifier to branching

[RossTate]

I think there's a way to view unwinding as a modifier to branching. But before I get into that, I first want to make sure I'm on the same page as everyone with respect to branching.

Branching

Contrary to what their names suggest, branching instructions like br do not correspond at the assembly level to jumping instructions. Rather, that's only half of the story. The other half has to do with the stack.

Suppose an engine has some type that is managed using reference counting—call it refcounted. Then consider the branch in the following code that calls some function $foo : [] -> [refcounted]:

(block $target ;; [] -> []
  (call $foo)
  (br $target)
)

This branch does not compile to simply a jump to the assembly-code location corresponding to $target. It also cleans up the portion of the stack that is not relevant to $target. In this case, that involves decrementing the reference count of the refcounted value returned by $foo that is sitting on the stack. In a single-threaded engine, that might in turn result in freeing the corresponding memory space and consequently require recursively decrementing the counts of any values contained therein. Depending on how large this structure is and how much of it is no longer necessary, this might take a while. So a simple instruction like br can actually execute a fair amount behind the scenes depending on how the engine manages resources and the stack.

All this is to illustrate that a label like $target more accurately corresponds to an assembly-code location and a location within the stack, and likewise an instruction like br $target more accurately corresponds to "clean up the stack up to the stack location corresponding to $target and then jump to the assembly-code location corresponding to $target".

Note, though, that "clean up" here only corresponds to the engine's resources on the stack. But what about the application's resources? That's where unwinding comes into play.

Unwinding

For the sake of this discussion, I am going to say that unwinders are specified using try instr1* unwind instr2* end, which executes instr* but indicates that instr2* : [] -> [] should be used to "unwind the stack", i.e. to perform application-level clean up. In a second, I'll get to how one causes the stack to be "unwound" rather than just "cleaned up".

Now consider some surface-level code using the common finally construct:

while (true) {
  File file = open(...);
  try {
    try {
      if (...)
        break;
    } catch (SomeException) {}
  } finally {
    close(file);
  }
}

Normally a break in a while loop would translate to a br in WebAssembly, but the finally clause in this snippet requires that its body be executed no matter how control leaves the try body. We could consider inlining the body of the finally at the break, but that results in code duplication, plus it would result in incorrectly catching SomeException if one gets thrown by close(file).nor does it work as well in other examples where there are other try/catch clauses surrounding the break).

Really what we want to do is to extend the semantics of "clean up the stack" that is already part of branching to incorporate "and execute unwinders". That is, we want to modify the branch instruction so that it also unwinds the stack.

One way we could enable this is to introduce an unwinding instruction that must precede a branching instruction, and its semantics is to modify that branching instruction to execute the unwinders in unwind clauses as it cleans up the stack. With this, the break instruction in the example above would translate to the instruction sequence unwinding (br $loop_exit).

Exception Handling

So far I haven't talked about exception handling, just unwinding. This illustrates that unwinding the stack, like cleaning up the stack, is its own concept. And although unwinding is an integral part of exception handling, bundling it with exception handling as the current proposal does is a misunderstanding of the concept.

But if unwinding is a separable component of exception handling, what is the other component? The answer to that depends on whether you're talking about single-phase exception handling or two-phase exception handling.

Single-Phase

Again, for the sake of this discussion, I am going to say that single-phase exception handling is done using try instr* catch $event $label, which indicates that any $event exceptions thrown from instr* should be caught and handled by $label (where the types of $event and $label match).

Now, consider the following WebAssembly program:

(try
  (try
    (throw $event)
  unwind
    ...
  end)
catch $event $label)

We can reduce this program to the following:

(try
  (try
    unwinding (br $label)
  unwind
    ...
  end)
catch $event $label)

When we can see the contents of the stack, we can replace a throw $event with a unwinding (br $label) to whatever label the event is currently bound to in the stack. That is, events are dynamically scoped variables that get bound to labels, and throw means "branch-and-unwind to whatever label the event is bound to in the current stack". (Of course, an important optimization is to unwind the stack as you search for these dynamically-scoped binding.)

This suggests that we can break throw up into two parts: unwinding and br_stack $event. The latter is an instruction that just transfers control to and does necessary cleanup up to some label determined by the current stack. This instruction on its own could even have utility, say for more severe exceptions that want to bypass unwinders or guarantee transfer.

Two-Phase

In two-phase exception handling, you use some form of stack inspection to determine the target label before you execute the unwinding branch to that label.

For the sake of this discussion, I'll say that an inspection is begun by using the instruction call_stack $call_tag, which looks up the stack for contexts of the form answer $call_tag instr1* within instr2* end (where execution is currently within instr2*, in which case the instructions instr1* are executed as the body of a dynamically-scoped function (see WebAssembly/design#1356 for more info).

As an example of unwinding in two-phase exception handling, consider the following C# code:

bool flag = …;
try {
    …
} catch (Exception) when (flag = !flag) {
    println(“caught first”);
} catch (Exception) {
    println(“caught second”);
}

This would be compiled to the following WebAssembly code (assuming C# throw compiles to call_stack $csharp_throw):

(call_tag $csharp_throw : [csharp_ref] -> [])

(block $outer
    (block $first
        (block $second
            (answer $csharp_throw ;; [csharp_ref] -> []
                (local.set $flag (i32.xor 1 (local.get $flag)))
                unwinding (br_if $first (local.get $flag))
                unwinding (br $second)
            within
                …
                (br $outer)
            )
        ) ;; $second : [csharp_ref]
        (call $println “caught second”)
        (br $outer)
    ) ;; $first : [csharp_ref]
    (call $println “caught first”)
    (br $outer)
) ;; $outer : []

Notice that the answer csharp_throw has a bunch of unwinding branches. Which of these gets executed depends on the state of the flag variable at the time the exception reaches the try in the C# source code. (Note that there is no try nor events in the compiled WebAssembly.) Depending on that flag, we'll either having an unwinding branch to $first or an unwinding branch to $second. In either case, the semantics is "clean up and unwind the stack up to the stack location corresponding to the chosen label and then jump to the assembly-code location corresponding to the chosen label". The difference between here and the original examples using finally is that the portion of the stack that needs to be cleaned up and unwound is not known statically. That is important for implementation (e.g. because it requires stack walking), but semantically speaking it is straightforward and aligns well with the existing abstractions in WebAssembly.

Summary

Regardless of whether we want to actually make an unwinding instruction, the important thing to note here is that unwinding is always done with a destination. How that destination is determined varies, but in most of the examples above the destination is known before unwinding begins.

The current proposal is about single-phase exception handling. But as I've tried to illustrate here, single-phase exception handling is really two concepts combined: dynamically-scoped branching and unwinding. So for the proposal to be extensible, it is important that its design for unwinding is compatible with other notions of destination, even if this proposal on its own solely enables dynamically-scoped destination labels (i.e. events). Ideas like those in #123 would help achieve this goal.

[aheejin]

• What additional functionalities do these new instructions achieve on top of existing throw and br? Not sure why we need yet another new instructions.
• You stressed that unwinding needs a destination. In two-phase unwinding, that destination is determined by the first phase. Not sure what you want to suggest here.
• Also not sure if it's a good idea to use your stack inspection instructions to discuss two-phase unwinding. You said you don't want to mix two discussions in Stack Inspection design#1356, and I'm not even very sure about what the semantics of those instructions are. My questions regarding that were not answered.

---

And just in case I wasn't clear in #123, in my proposed version of try-unwind, unwind block is entered only when any instruction in try part throws. Destructor code for normal path (when there's no exception) is compiled separately. You might say it is code duplication, but in many cases (especially in LLVM) that's how it's done, because destructor code for exception path has some more things to handle. If you want a dedicated code structure that is entered regardless of whether there's an exception or not, you want finally, which is a separate thing. I'm not necessarily against having finally; it might be useful for some toolchain other than LLVM. But I don't think our toolchain will use it.

[RossTate]

My primary intent for this post was to help develop conceptual understanding of unwinding, which I thought might be helpful for ongoing discussions. The instructions I use here are primarily pedagogical devices used to illustrate how the interwoven concepts in exception handling can be broken down. Sorry, I should have made my intentions clearer.

[aheejin]

My primary intent for this post was to help develop conceptual understanding of unwinding, which I thought might be helpful for ongoing discussions. The instructions I use here are primarily pedagogical devices used to illustrate how the interwoven concepts in exception handling can be broken down. Sorry, I should have made my intentions clearer.

I see, but that leaves my other questions. Unless they are answered, it's hard to continue discussions, or understand what the takeaway or suggestion from this post is.

What I understand is br might do more things things than we simply imagine. That I get it. But other than that not sure where we should proceed with that info, if you're not suggesting we add unwinding instruction. (If you are, then my first question: what additional functionalities does it achieve?)

[tlively]

This post seems to be mostly about factoring our understanding of programmer (or language designer) intent with regard to various exception/unwinding mechanisms into separate notions of control flow transfer and resource cleanup. @RossTate, since this post does not have a concrete call to action, I am unsure of what your goal in posting it is. Are there specific other discussions you think these ideas should influence?

[RossTate]

It seemed pertinent to the discussion in #123, giving a motivation for why to change the design for unwinding. (@aheejin asked me to not give this motivation in that issue.) It also seemed pertinent to the discussion in WebAssembly/design#1356, illustrating how stack inspection can be used to implement two-phase exception handling provided a suitable unwinding design is in place.

[ajklein]

It sounds like this was meant as background reading for discussions in several other issues. In future, @RossTate, I'd recommend not opening new issues in such cases, and instead creating a gist or similar external resource and linking it from the relevant places. Particularly on proposal repos, an issue generally implies that there's something about the relevant repo which the issue creator thinks ought to be changed.

[aheejin]

@RossTate

It seemed pertinent to the discussion in #123, giving a motivation for why to change the design for unwinding. (@aheejin asked me to not give this motivation in that issue.)

I don't remember I asked you something specific like that. Maybe I might have said that I wished to keep the issue post on the topic in our Zoom meeting maybe...? It's been a while, but so that's my best guess, but I don't think I asked you not to post about something specific.

I agree sometimes it is better to post something as a separate post if it gets too long. In that case I think it will help people figure out the context if you say this is a spin-off from a discussion from comments from another issue and for additional info for that part of the discussion. Also gist, as @ajklein suggested, is a good tool too.

[RossTate]

Ah, okay, thanks for the suggestions. I'll incorporate them in the future to avoid causing so much confusion!

[phoe]

Here's a bit more information from the point of view of a Common Lisp programmer - posting it here in order not to clutter #87.

but in most of the examples above the destination is known before unwinding begins.

This is also the case in Common Lisp.

Copying the basic information from the former thread: Common Lisp has three operators for performing non-local exits, which may cause stack unwinding: tagbody/go, block/return-from, and catch/throw.

• go is the "goto" operator that jumps to a label defined in a tagbody;
• return-from returns a value from a matching block in lexical scope;
• throw returns a value from a matching catch in dynamic scope.

This means that we have two classes of situations with regard to knowing the destination:

• In case of go and return-from, the destination is always known at compilation time because both operators are lexical in scope. Having a go without a lexically matching tagbody or return-from without a lexically matching block is a compilation error.
• In case of throw, the tag may not be provided at compilation time and may instead be given at runtime; additionally, it is possible to have a throw without a lexically matching catch. Therefore, throw must be able to inspect its dynamic environment in order to find its matching catch. This is done by scanning the call stack (or, equivalently, checking the contents of a dynamic/fluid variable), finding the matching catch tag, and setting it as the destination before performing the non-local exit.
  • Note: it is possible to emulate throw via go or return-from: see Baker, «"CATCH/THROW" emulated by "BLOCK/RETURN-FROM"». This means that, in the worst case, we can write throw and catch in Common Lisp itself, and therefore we don't strictly need it on the assembly level.

That's all. All unwinds in Common Lisp happen because of these three primitive operators.

---

However, one other important thing in Common Lisp is that non-local go/return is possible. In particular, it is possible to use a closure to close over a matching tagbody/block and execute that closure elsewhere in the dynamic scope of the same tagbody/block. Let us consider the following code:

(defun foo (function)
  (funcall function))

(defun bar ()
  (block nil
    (let ((function (lambda () (return-from nil 42))))
      (foo function)
      24)))

(defun baz ()
  (let ((result 42))
    (tagbody
       (let ((function (lambda () (go :end))))
         (foo function))
       (setf result 24)
     :end)
    result))

Slightly simplifying, we have defined three functions:

• foo, which:
  • accepts a single argument, which is a function,
  • calls it;
• bar, which:
  • defines a block named nil,
  • creates an anonymous function that closes over the block and contains an instruction to return 42 from it,
  • calls foo with this anonymous function,
  • returns 24;
• baz, which:
  • binds a variable named result with an initial value of 42,
  • establishes a tagbody with a single tag named :end at its end,
  • creates an anonymous function that closes over the tagbody and contains an instruction to go to the :end tag,
  • calls foo with this anonymous function,
  • sets result to 24,
  • leaves the tagbody,
  • returns the value of result.

In both situations, we can infer that, if there is no non-local exit, each function is supposed to return 24, as in case of bar the function naturally returns 24, and in case of baz, the result variable is set to 24 before being returned outside of tagbody.

However, by calling bar or baz, we can see that 42 is returned. This is because a non-local exit happens in both cases, altering the standard control flow of these functions.

In both cases, we can see that the anonymous functions that perform the non-local exits are created in the lexical scope of tagbody/block and that they are called indirectly, outside of that lexical scope but inside its dynamic scope - they are called inside foo. (They might also be called anywhere deeper inside foo, as long as control does not leave the dynamic scope of tagbody/block; it is possible that foo can call foo-1 which can call foo-2 which can call ... which can call foo-n which, finally, can call the originally created anonymous function and trigger an unwind.)

---

As mentioned in #87, unwind-protect is the singular equivalent of finally which ensures that a block of code (called the cleanup form in CL) is executed whenever control leaves another block of code (called the protected form in CL), and it is honored by all of the above operators as well as normal returns.

The aforementioned non-local goto behavior chains with unwind-protect. Even in case of an unwind that is initiated outside its direct lexical scope (and, therefore, anywhere deeper on the call stack), all unwind-protect forms encountered along the way must be honored.

---

What would be required to make such unwind-preserving non-local goto possible in WASM? (Perhaps it is already possible; as a newcomer, I apologize if I am trying to lockpick an already open door.)

[tlively]

If I understand correctly, tagbody ... :end could be compiled to use try-catch and a br_table once we introduce two-phase exception handling with filter functions in a follow-on proposal.

The general scheme could use an event like this: event $go_event of [i32, i32]. The first i32 identifies the target tagbody construct and the second identifies the target tag within that tagbody. First class labels would be compiled down to such a (tagbody_id, tag_id) pair and go label would become throw (tagbody_id, tag_id). tagbody itself would be compiled to a filtered catch $go_event that only catches go_events with matching tagbody ids and that uses the tag_id to index into a br_table to jump to the correct location.

[phoe]

The first i32 identifies the target tagbody construct and the second identifies the target tag within that tagbody.

I wonder if it is possible to bend this construct to make it possible to signal errors when the tagbody in question is not found.

If we consider the following code:

(let ((function (block nil (lambda () (return-from nil 42)))))
  (funcall function))

Then the extent of block has already ended after the function is returned and therefore, according to the specification, an error of type control-error should be signaled.

If I understand the above correctly, then this means that we should first search for the matching event on the stack. If it is found, we can perform a jump; if it is not found, then we should signal an error via normal CL means.

[RossTate]

Thanks for the great question, @phoe. I'll note that there seems to be a little bit of flexibility in how to solve the problem due to the fact that the language spec gives some flexibility when return-from and go target an exit point that is no longer dynamically in scope. (However, the spec is a little inconsistent because on the pages for return-from and go it explicitly says the behavior in this situation has "undefined consequences" whereas for control-error it says they should signal a control-error.)

Let's try to go for the control-error semantics in all cases. We can build on Thomas's suggestion, but we actually don't need two-phase (under some assumptions).

When control enters a block, we can allocate a mutable and equatable reference to some boolean (using the GC proposal). When control exits that block, we can update the boolean in that reference to indicate that its dynamic extent has ended. (We would need at least try/unwind to make sure this update happens even for non-local control flow.) The body of the block would be run in a try with a catch $block_event handler, where $block_event takes a mutable+equatable boolean reference and a Common Lisp value as its payload. If the payload's reference matches the allocated reference (stored in the stack frame), then we branch to the end of the block with the Common Lisp value in the payload. Otherwise, we continue the search+unwinding process. For return-from, we take advantage of the lexical scoping to ensure that return-from has the same reference its matching block allocated. We check the boolean in this reference to see if the corresponding block's dynamic extent still exists. If not, we signal a control-error. If it is, then we throw $block_event with the mutable+equatable boolean reference and the Common Lisp value to return as its payload.

When control enters a tagbody, we do something similar. The tricky additional thing is that WebAssembly does not provide direct support for irreducible CFGs. Thankfully, tagbody is untyped, so we can use br_table (as @tlively already described).

This implementation works in a Common Lisp world. But in a wasm world there are two things that can go wrong:

1. The dynamic extent can exist but the mutable+equatable reference can be outside of its extent. This can happen (in various wasm extensions) if the reference gets moved to another thread or if the block/tagbody frame are in a stack that has been captured is a (delimited) continuation. If you want to be robust to this situation, then you need a true two-phase solution to examine the current dynamic extent.
2. Despite not being exceptions, the $block_event/$tag_event are intercepted by catch_all. In another thread it was mentioned that the expectation was that catch_all would also intercept all searches in a two-phase system, so it is unclear that a two-phase solution would address this limitation.

As for the longer term, we could more directly support these lexically-scoped constructs (rather than emulate them through dynamically-scoped constructs) with invalidatable heap references to wasm labels. The reference would be invalidated whenever the referenced label is popped off its stack, and when you try to dereference the (valid) reference, the engine would do a (quick) check that the current control point is on the same stack (or continuation) as the referenced label. Then you could do an unwinding branch to the retrieved label.

[phoe]

Thanks for the elaborate explanation.

and a Common Lisp value as its payload.

Multiple values can be returned from a block, as CL supports multiple values. Is that possible?

I'll note that there seems to be a little bit of flexibility in how to solve the problem due to the fact that the language spec gives some flexibility when return-from and go target an exit point that is no longer dynamically in scope. (However, the spec is a little inconsistent because on the pages for return-from and go it explicitly says the behavior in this situation has "undefined consequences" whereas for control-error it says they should signal a control-error.)

This flexibility is because of the CL definition of undefined behavior. Generally, in case of UB, the implementation is allowed to do whatever it wants, including crashing. But, if the implementation decides to handle this aforementioned situation gracefully in some way (which is done by all CL implementations I know), then it must do it by signaling a control-error.

Thankfully, tagbody is untyped

What do you mean by it being untyped? A tagbody has two traits: that its tags can be either integers or symbols (which can be reduced to more integers during compilation stage), and that it always returns nil, but these might not be what you mean.

[tlively]

Multiple values can be returned from a block, as CL supports multiple values. Is that possible?

Yes, with the recently standardized multivalue proposal, WebAssembly can generally send multiple values wherever it can send one value. Note that all the control flow is statically typed, though, so a single WebAssembly block or event cannot carry one value on some code paths and multiple values on other code paths. I don't know if that would be a problem for CL, but it is, it could be solved by boxing the potentially-multiple values.

[phoe]

Note that all the control flow is statically typed, though, so a single WebAssembly block or event cannot carry one value on some code paths and multiple values on other code paths.

In Common Lisp, if a given block of code returns multiple values (e.g. by calling the values function), then only the primary value is used and other values are discarded unless the call site of that block of code is prepared to accept multiple values (e.g. by using multiple-value-bind or multiple-value-call). Missing values are coerced to nil, which is the case e.g. when zero values are returned but a value is expected, or when one attempts to grab three values from a block of code that only returns one value.

For a short example, (list 1 2 (values 3 4 5) 6 (values 7) (values)) evaluates to (1 2 3 6 7 NIL).

Is such a kind of primary value extraction and nil-substitution of missing values possible on the WebAssembly level?

[tlively]

Not directly, but it shouldn't be too hard to insert some WebAssembly to bridge the difference between the externally expected types and the internally provided types given that both are statically known. (Or are they not both statically known?)

[phoe]

Common Lisp is a strongly dynamically typed language and the number and types of the values may be known at compilation time, but need not be known in the general case.

If we have a function named foo without any optional type information provided, then it may return:

• zero values,
• an integer,
• a string,
• three integers as three values,
• three strings as three values,
• a string and an integer and a vector and a symbol and another string as five values,
• etc..

A sufficiently smart compiler™ might be able to infer some or all of this information statically at compilation time, but e.g. in case of (defun foo () (bar)), if function bar is not yet defined (which is permitted in CL), the compiler has no declared or deduced type information to work with, so it must prepare for bar, and therefore foo, to be able to return literally any combination of values.

[RossTate]

Common Lisp is a strongly dynamically typed language and the number and types of the values may be known at compilation time, but need not be known in the general case.

Yep. And there are a lot of implementation strategies for this. WebAssembly's goal is to support at least one of these strategies reasonably efficiently. It's up to the Common-Lisp-to-WebAssembly compiler to figure out which strategy works well. And if there's an extension to WebAssembly that can be made (and is more broadly useful), then one can develop a proposal to add such functionality to WebAssembly. My suspicion is that there's already a reasonable way to support this particular dynamism of Common Lisp in WebAssembly, but I'd be interested to learn if I'm mistaken or if there's a substantially better technique that we should be made aware of.