[LLVMdev] nonlocal go to -- how?

[Hendrik Boom]

On Mon, 05 May 2008 09:56:26 +0200, Duncan Sands wrote:

> Hi,
> 
>> The problem is with the go to statement.  Again, local go to's, that go
>> somewhere within the same function are no particular problem -- though
>> I haven't studied the interaction with alloca yet; that might offer a
>> few surprises.  The questions I have are about goto's that exit from a
>> function.  The traditional mechanism is to implement a label as an
>> instruction-pointer/environment-pointer pair, just as for procedures.
>> You just load the environment-pointer into the appropriate register,
>> and jump to the address.  (again there are technical details about the
>> size of the local stack at the destination, disposition of alloca
>> storage, and the like, and nowadays, unwinding the stack).
>> 
>> I don't see a mechanism for this.
> 
> you can roll your unwinder using multiple return values (support for
> functions that return multiple values was recently added): the first
> return value is the usual function return value; the next one is the
> nesting depth to which you want to go (I'm assuming that you can only go
> to a less nested function); the last one is a number indicating which
> label in the final function you want to branch to.
> 
> A non-local goto (to function F, label L) becomes:
>   ret { undef, F_static_depth, L_number }
> After every call to this function you then check the second return value
> to see if it is a valid static depth (if not, no non-local goto happened
> and execution continues normally) and if it is then either: (a) the
> static depth is that for this function; you then execute a switch
> statement using L_number that branches to the right label; or (b) the
> static depth is for a lexically less nested function, and you again
> execute ret { undef, F_static_depth, L_number }

Except that it's not the static depth you want, it's the dynamic stack-
nesting depth that at run-time corresponds to the function activation 
that is at the right static depth in the jumper's environment.  All 
invocations of one function are at the same static depth -- that's what's 
static about it.  This doesn't much affect the mechanisms you are 
presenting, though.

The problem with this is that it places a lot of overhead on every 
function call and return.  The alternative mechanisms involving 
exceptions, while more complex, involve overhead only for functions that 
actually involve labels (which are rare in practise).

Or am I wrong on this.? Does every call through which an exception might 
pass have to be implemented by an invoke, even though the code there 
knows nothing whatsoever about exceptions?  Might functions with no try, 
catch, or throw in their code still have to perform calls using invoke 
instead of call in case their callee might throw an exception straight 
through them to a faraway outer function?

> 
>> The closest I see is the mechanism for exceptions.  I cannot tell by
>> reading the documentation for exception-handling whether it is
>> sufficiently flexible to accomodate nonlocal goto's.  It's plain that
>> on modern systems (which dribble saved registers all over the sack)
>> some kind of unwinding is necessary, and that the traditional model of
>> loading a register and jumping is no longer sufficient.  What's not
>> clear is whether the exception handling mechanism is sufficiently
>> dynamic to permit an accurate specification of the jump target.  It's
>> not necessarily the most local version of the label on the stack that's
>> the target; it's the one whose stack frame is reached by the jumping
>> procedure's array of static links.
> 
> The problem with unwinding is that you need to have a personality
> function and writing your own is a pain.

At the moment I haven't seen (or if I have seen, I haven't understood in 
detail) enough documentation on exceptions that I can figure out what 
code to generate or exactly what a personality function does.

> On my infinite list of things
> to do is working out how to codegen invoke when there is no personality
> function, and how to codegen unwind.

So this makes me ask, is the C++ exception handling implemented?  If so, 
I might be able to use it instead of my own.
 
> 
> Ciao,
> 
> Duncan.

-- hendrik