Re: Implementation and Optimization of exceptions ( static analysis possible? )

Steven D. Majewski <sdm7g@elvis.med.virginia.edu> wrote:
> The exception processing model I'm most familiar with ( from long
>years on a VAX, and from similar implementations for various
>languages ) is the stack based one, where every procedure or
>protected block of code has some stack based structure that indicates
>how ( and maybe what ) exceptions are handled. ...


The usual technique in Ada compilers has near-zero overhead for entering
a procedure/block with a handler, and lots of overhead for actually
raising an exception. This is good if exceptions are used for truly
exceptional situations. The technique is to keep a static table for
each procedure, which maps ranges of code addresses to the corresponding
exception handler. When you enter such a procedure, you don't need to
do anything. When an exception is raised, the run-time system searches
the table for the top-most stack frame, using the current value of the
PC. If that turns up a handler, jump to it. Otherwise, pop one frame
and try again.


This requires being able to find the static table from the frame. Store
the address of the per-procedure table at a location that is at a known
offset (say, -4 bytes) from the start of the procedure. The frame
contains a return address. Follow this, and back up one instruction, to
find the call instruction that called this procedure. Look in that
instruction to get the address of the start of the current procedure.
Subtract 4 to get the address of the address of the table.


This gets complex if the language support indirect calls, which most
languages do. But it can be done.


In any case, it requires the exception handling stuff to know what the
code looks like for a procedure call. For example, if the code calls
indirect through a register, the RTS needs to be able to track down the
value of that register (the value it had when the call occurred, which
might have been spilled to memory at this point -- the compiler needs to
ensure that that value is obtainable somehow).


An alternative is to store one giant table for the whole program,
created at link time from per-procedure information. Since Ada
implementations usually need to do extra work at link-time
("pre-linking") anyway, this works fine. Then you don't need to worry
about call-instruction formats. But searching the table is slower,
because it's bigger.


One other point: You really want to walk down the stack *twice*, i.e.
don't destroy the stack during the first walk. Walk it first, to find
the handler. If none is found, walk it again to produce a stack
traceback, or enter the debugger with the stack intact. If a handler is
found, *then* chop the stack back and jump to the handler.


The above techniques have "near zero" overhead, not quite zero, because
they inhibit certain optimizations, and/or make certain optimizations
more difficult (as compared to a language that doesn't have exceptions
at all). For example, you don't want to store a stack frame for all
procedures, which can get tricky. Also, if you have a call to another
language (say, from Ada to C, and the C compiler knows nothing about
exceptions), then you have to beware.


- Bob
--

Return to the comp.compilers page.
Search the comp.compilers archives again.