nonlocal go to -- how?

The languages I'm faced with compiling in the near future have nonlocal
go to statements and nested procedures.

A procedure gets implemented as a structure containing its entry point
and an environment pointer. It is easy enough to call its entry point
and pass the environment pointer as an extra argument (rather like the
pointer to this or self in object-oriented code). It's no problem. The
trampoline intrinsic is a neat way of packaging this so as to retrofit
into C's one-address-only function pointer, but that's not necessary in a
language where procedures are all known to have this behaviour.

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.

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.

-- hendrik

Well, I suppose it could be kind of done in not-quite C++, and therefore
it could probably be made to work in LLVM, like this.

Labels are values, like:

struct Label{ void * level, *target; }

The level identifies the activation record in which the jump target
occurs; the target is the actual address of the instruction to be jumped
to when the label is used.

Suppose the high-level language defined a label L in functino foo. Then
we build a Label object LL to represent it.

foo()
{
Label LL;
LL.level = ≪
LL.target = &L;

...
...

L:
}

Someplace else, syntactically nested within foo, there's another function
bar, which contains a goto L.

This goto gets translated into something like:
Translate the goto inso something like

  throw appropriate_static_link->LL;

where appropriate static link is whatever is needed to access the proper
variable in the enclosing scope.

Around every call *from* any function that contains a Label, we have code
like:

  try(
  the_call
  }
  catch(Label e)
  { if(e.level == LL.level)
  goto e.label;
    else throw e;
  }

Of course this coding requires that you can take addresses of labels and
jump to them later in C++, which as far as I can recall is not one of its
language features.

But LLVM is a lower-level language, so I'm hoping that something similar
can be accomplished. But I haven't noticed dynamic arguments to the br
instruction.

-- hendrik

Hi Hendrick,

LLVM's CFG is purely static. This is necessary for efficient register allocation behavior. Your front-end could implement a nonlocal goto by using a tail call and a switch in the entry block of your branched-to function. This is essentially how LLVM implements the address-of-label extension, transforming 'goto x' into a switch statement.

// 'foo' makes a nonlocal goto into 'bar'.
int foo() {
   return bar_impl(2 /* non-default entry point */, undef, undef /* who knows? */);
}

// Invoke for a 'normal' call.
int bar(int x, int y) {
   return bar_impl(0 /* default entry point */, x, y);
}

// Implementation detail.
int bar_impl(int label, int x, int y) {
   switch (label) {
   case 1: goto L1;
   case 2: goto L2;
   default: goto entry;
   }
entry:
   ...
L1:
   ...
L2:
   ...
}

Your front-end would need to track whether it is necessary to emit such a shim (i.e., whether there are any incoming gotos).

If you use a 'tail call' instruction to invoke 'bar_impl', LLVM will use proper tail calls in some cases.

Of course, this doesn't support the full generality of indirect nonlocal goto, so may not be suitable for your application.

The languages I'm faced with compiling in the near future have nonlocal goto statements and nested procedures.

You want to return to a previous activation record (pascal speak) or stack frame? If yes, then yes, EH will do that for you. You'll want to understand what EH is in detail and how to map the semantics you want onto it. That mapping could be simple (if you match the usual and customary EH semantics) or complex (if you want to stray farther away). You'll want to understand how you want other languages to behave if you have the ability to have other languages on the stack.

For example, Objective-C on Apple's platform currently doesn't interoperate very well when C++ is on the stack (imagine an Objective-C runtime that uses setjmp/longjmp that bypasses the running of C++ dtors for stack variables as you throw past them). This setup, I'd claim is unfortunate, and you really want to avoid it. It is better to map whatever semantics you want onto the normal platform EH abi, so that other languages, C++ included, just work.

Also, if you do it that way, you should be able to count on the optimizer getting rid of all the extra stuff and making the code `fast' in more trivial cases.

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 semantics you generally want are all stack allocated variables are destroyed as the frame which contained them is destroyed. Behavior other than this would be weird. A special exception is made for the object being thrown and all the data that goes with it.

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.

Additionally, one generally needs to deallocate stack variables as well.

I don't see a mechanism for this.

See llvm-g++ and C++. I believe that it works.

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 is.

What's not clear is whether the exception handling mechanism is sufficiently dynamic to
permit an accurate specification of the jump target.

It is.

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.

You're allowed an arbitrary predicate that explains if this is the right place to wind up.

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 }

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. 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.

Ciao,

Duncan.

Hendrick:

I suspect that exception handling is going to be the way to go here. The
following is partly tangential, but possibly relevant.

Largely for social reasons, we've been looking at doing a C-like surface
syntax for BitC. As part of that, we looked at multi-level break and
gotos to same-or-outer scope. In particular, we started by asking
whether either construct adds any new core semantics to the language,
given that we already have exception handling.

The answer is "no". As long as all gotos proceed to same-or-outer scope,
a program containing gotos can be transformed without loss of meaning
into a program containing only exception catch blocks and raise/throw
statements. The catch block executes a switch statement to determine how
to resume computation at the appropriate label. It isn't pretty, and
it's not the way that I would want to actually implement it, but we did
find that outcome comfortable from a formal semantic specification
standpoint.

The nice thing about it is that it generalizes to nested procedure exits
in all cases where the target label of the goto appears in a lexically
nested scope.

However, Mike Stump is right -- you need to consider what happens when
other languages intervene on the call stack. This may not arise in your
case precisely because you are speaking about inner procedures, but do
think it through.

shap

Yes. In fact, this generalizes to exception handlers in general, which
demonstrates that exceptions are "pure" in the functional language
sense.

Slight modification to what Duncan wrote. What you conceptually want
here is to convert the return type into a discriminated union. One leg
is used for normal return, while the other is used for goto exit and
target label ID (I'm assuming that goto exit does not carry a return
value). But it's the same idea as the one Duncan was sketching.

shap

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

Hi,

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).

correct, the dwarf exception mechanism would only add serious overhead when
you perform a non-local goto.

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?

No. The exception just winds up out of normal calls. Invoke is only
needed when you want to catch an exception.

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?

No, except to perform things like automatic object finalization (cleanups)
in which case cleanup code in the function needs to be run if an exception
unwinds through the function, even if you don't want to catch it there.

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

It is implemented. Take a look at what llvm-g++ -S -emit-llvm gives you.

Ciao,

Duncan.