Re: exceptions & dataflow

Sergey Solyanik (sergey@solyanik.com) wrote:


[...snip...]


: If you are working on Java-like language, one possible approach is to
: terminate basic blocks at each function call or instruction that can
: throw exceptions. Create conditional edges from these basic blocks to
: every catch block. If there are no finallies in the code, any kind of
: analysis should apply unmodified to the resulting graph.


My experience in breaking Java bytecode up into basic blocks is that
code can be broken up into basic blocks but a bunch of rules have to
be followed. First, if an exception is thrown, the whole op stack is
discarded while the local variable store remains intact. If you can
live with the fact that the stack has to be "rolled back" from any
point in the code, you need not split a basicblock that causes only
modifications to the stack. So, additional basic block boundries are
needed in the places that affect the state of the machine, which could
affect the environment that the basic block is handled in:


(1) When a store is done to the local variables (like istore_0)
(2) When a field is stored to
(3) When an array is stored to
(4) When a method is invoked, if it is known that the metod does any of the
above.


This assumes that exception are generated within the blocks and they
can jump to a well defined exception dispatch routine when they occur.


: Finallies do seem to complicate things significantly. For normal block
: exiting I cannot come up with anything better than duplicating the
: code when its practical, and spilling everything when it's not. One
: will apparently have to spill everything before any call site as well.


: Good thing about finally, though, is that it is either entered through
: normal try block exit (i. e. explicit jsr before jump out), but your
: either exit a function or transfer to catch block (which was
: anticipated by fake edges inserted above). So just spilling before
: each call and separating non-unrolled finallies from flow analysis
: seems to be enough.


Because they are JSRs, they cause a whole bunch of problems when
dealing with them at the basic block level. Especially when doing data
flow analysis for verification (which is what I did with the Kimera
project).


: In Java, hardware exceptions can ony happen in very controlled manner
: (e. g. to test for null). If your language contains pointers, things
: are much worse and you'd have to break basic block with essentially
: any pointer dereference when you cannot prove that location exists.


This shouldn't be that much of a problem. If the pointer is null, then
throw an exception, you have to insert code to do this (but only a few
instructions do this). If the pointer is not null, then it exists (or
the JVM is not safe).




: I must confess that I am yet to implement this approach so it is possible
: for it to be sheer idiocy. I was, although not very seriously, looking for
: papers on exception optimizations and thinking about it at leisure for
: a few months, but did not hit much of an existing art :-).


I spend a few months trying to code it correctly with Java anyways,
just trying to implement it without thinking about doing data flow
analysis for optimization is hard enough. I would be very interested
to see how it was done by Sun or other compilers with exception
support (modula 2, C++, etc..).


Sean






























--

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