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

> "Steven D. Majewski" <sdm7g@elvis.med.virginia.edu> writes:


      [One] exception processing model ... 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....


      Do any language implementations do static analysis and optimization
      of exceptions within a procedure - in effect, translating them into
      goto's and avoiding the overhead of handlers ?


There are many ways of implementing exception handling. They depend
on the details of language semantics, the implementor's goals, and the
hardware architecture.


There are actually two parts to the problem: exception detection, and
exception dispatching.


Exception detection is how the program knows at runtime that an
exception happened. In the case of an floating-point overflow or
integer divide-by-zero, for instance, some architectures support
traps, others require explicit checks, and others allow you to choose.
On the other hand, on most architectures, out-of-range array index and
integer overflow have to be checked by in-line code. And of course
many exceptions (such as reading past the end of file) are software
generated by a called routine.


Once you've detected the exception, you need to dispatch to the
appropriate handler, and set up the correct environment -- in the case
of non-resumptive semantics, this means cutting back the stack and
possibly executing clean up routines requested by intermediate blocks.
Here are a few ways of dispatching exceptions.


Stack-frame based


    In this approach, every stack frame contains an exception handler
    area. This means that every procedure entry and every nested
    exception handler needs to initialize this area, even if it does not
    use exception handlers. At runtime, handling exceptions requires
    unwinding the stack frame by frame. On the other hand, it is simple
    to implement both in the compiler and at runtime.


Special exception stack


    Another approach (as you mentioned) is a separate stack devoted only
    to exception handlers. This incurs no cost for procedures and
    blocks that do not have exception handlers, but a somewhat higher
    cost for those that do. On the other hand, when an exception
    happens, it can be handled faster.


Address range table


    It is possible to implement exceptions so that there is zero
    execution overhead unless an exception happens. Instead of
    dynamically pushing exception records on a stack, you keep a static
    table of address ranges within which exceptions are set. When an
    exception happens, you check whether you are executing within a
    range has a handler for that exception. If not, you pop to the next
    frame up, and repeat the check. The cost is somewhat higher if an
    exception occurs, but zero if it does not.


So there is a fairly wide range of possibilities. In the special case
where the handler textually includes the code generating the
exception, you can in some cases optimize to a goto. Of course, the
goto itself may have non-trivial semantics if it jumps out of a
monitor block, a rendezvous, or whatever.


      ...I often use exceptions as a way to break out of an inner loop -
      in effect, as a "structured goto". Is this necessarily less
      effecient, or are there cases where a compiler could produce the
      equivalent code?...


This can certainly be made as efficient as a goto. This will depend
heavily on the particular language, compiler, and optimization level
you're using.


For that matter, I don't think it's very good programming practice.
An exception is not only a goto, it is a _hidden_ goto. Depending on
exceptions for your program's control structure seems like a good way
of making the it less clear.


So I would generally recommend against it.


-s
--

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