unwind

Problem definition
------------------

We are compiling Common Lisp (CL). CL has a pair of operators `block` and `return-from`. They work very similarly to `call-with-escape-continuation` in Racket.

`(block [name] [code...])` executes the code. If execution doesn't hit a `return-from` for the name, nothing special occurs.

`(return-from [name] ...)` performs a non local exit: The _lexically_ enclosing `block` with the same name exits immediately.

So for example, in `(block b (when (condition) (return-from b)) ...more code...)`, if `(condition)` evaluates to true, the `...more code...` is never executed.

Lisp has closures and it is possible to close over block names, so a `return-from` may not be in the same function as its linked `block`. This means that execution of a `return-from` may need to unwind the stack. (`block`/`return-from` pairs in the same function are just translated into intraprocedural jumps, and aren't relevant here.) Because block names are lexical, the compiler knows at which exit point (instruction address) any given `return-from` will end up. However, the frames between the `return-from` function and the `block` function are in general unknown.

The lexicality makes this mechanism more like `setjmp`/`longjmp` than `try/catch`, in C++ terms. For example, consider the pair of functions:

```lisp
(defun foo ()
  (block abcdefg (bar (lambda () (return-from abcdefg)))))
(defun bar (f)
  (block abcdefg (funcall f))
  (print "Hello world"))
```

The `foo` function creates a closure over the block, and then the `bar` function calls that closure. If you execute `(foo)`, `bar` will call the closure, and control will return to the `foo` frame - so nothing is printed, and the `block` in `bar` is irrelevant. This is somewhat like passing around a `jmp_buf`.

These are not full continuations: Once a block has exited, normally or abnormally, trying to exit it again (e.g. by calling a closure with a linked `return-from`) is undefined behavior. We would however like to define it to use higher level debugging mechanisms rather than terminate or crash. Ideally our debugger would be entered from the frame that executed the faulty `return-from`, i.e. before any unwinding has actually occurred.

Additionally, there is another Lisp operator, `unwind-protect`, that allows code to be executed when a frame is exited normally or abnormally. This is more or less the same semantics as C++ destructors for automatic objects, though there may not be any actual object. Since our implementation interoperates with C++, it's also possible that actual C++ frames will be between a `return-from` and its `block`, and these frames need to be cleaned up properly.

Due to deficiencies in our handling of other parts of the language, we currently have far more unwinding `block`/`return-from` pairs than we need to have. However, while it will be rarer in the future, it's still a normal language construct, rather than only executed in exceptional cases.

Current solution
----------------

We use C++ exception handling, including the C++ level of the Itanium ABI. When we enter a `block`, we save the frame base pointer - obtained with `llvm.frameaddress` - and pass it down to any `return-from`s to that block. Unwinding `return-from`s construct an instance of our special exception class, and execute an actual C++ throw of this object. The object contains this frame base pointer to indicate the destination frame, and a small integer to disambiguate which `block` in a frame is being returned to (a compile time constant).

Function calls within a `block` are translated as LLVM-IR invoke instructions. The landing pad for these instructions checks if the exception is one of ours, and if not, executes an LLVM-IR resume. If it is, the frame pointer is checked for a match. If it doesn't match, the exception is rethrown. If it does, the disambiguating integer is checked, and execution branches to the appropriate code in the function. Using C++ exceptions requires that these landing pads include calls to `__cxa_begin_catch` and such.

C++ throw would `std::terminate` for an unhandled exception, meaning that in the case of an illegal multiple return as described above, the process would die. To avoid this, in the `return-from` generated code, before the exception is actually thrown, we iterate through the stack using libunwind to see if the frame pointer is actually present. If it isn't, we enter our debugger.

`unwind-protect` is implemented as a C++ function that puts the code to execute in an automatic object destructor.

Problems
--------

While semantically correct, it's slow. There's a general slowness, because we iterate over the stack three times (one more than usual for C++ exceptions), execute all this complicated landing pad code, implicitly use `__cxa_allocate_exception` which heap allocates unnecessarily, etc. Also, drmeister has found that throwing an exception grabs a mutex on some systems, meaning that if multiple threads unwind simultaneously there is notable contention.

Additionally, `llvm.frameaddress` is described as being intended only for debugging, so our use of it is maybe a bad idea. Plus the fact that a new stack frame could end up at the same address - we'll probably need to include some other disambiguation there, like an atomic counter value maybe.

Solution 1
----------

I am currently trying to figure out how to write a custom personality function and custom unwinding code using the Itanium ABI. This should remove one of the stack iteration phases, since we can just examine the return value of `_Unwind_RaiseException` to see if the exception would be handled or not. Additionally the personality can itself check the frame address, so the landing pad code doesn't need to, and we can make a few other simplifications since we don't need full C++ behavior for our frames. So hopefully it should be faster.

Solution 2
----------

Since under Itanium/LLVM/something `setjmp` and `longjmp` apparently do execute cleanups in frames, we could use those instead of C++ exceptions and checking frame pointers ourselves.

Questions
---------

* Are we completely on the wrong track here?
* Does LLVM provide any way to customize the language-specific data areas for frames? With the custom personality I am trying to parse the usual C++ data, which has lots of stuff we don't need - apparently OpenDylan does the same thing (they have been helpful). I mean, if we do stick with this exception approach, we don't really need type information at all - the exceptionClass is enough.
* About the LLVM exception handling design: Under Itanium, a given call site can have multiple landing pads, corresponding to different types (or cleanups). In LLVM, however, there is only one landing pad for any invocation, and the landing pad code has to check the selector itself and branch appropriately. The personality and the landing pad code both seem to do type discrimination - is this not redundant? Am I missing something here?
* If we do switch to SJLJ - how do we generate code appropriately? The intrinsics exist, but I don't see any documentation on how big a `jmp_buf` to alloca.
* Also with SJLJ, under Itanium this is a one phase process, meaning there is no way we can directly check whether the `jmp_buf` is still valid - is that correct? If so, is there a better way to check whether a frame is still on the stack than our `llvm.frameaddress`/libunwind combo?
* If we use the Itanium unwinders at all, we apparently hit this mutex contention problem on some operating systems. Is there any alternative? (So far the answer seems to be "no".)