Re: Tightening Exception-based Control flow graph

[John Plond JORGENSEN <jjorge1@cs.mcgill.ca>]

>>>>> "vranganath" == Venkatesh Prasad Ranganath <vranganath@cox.net> writes:
    vranganath> Laurie Hendren wrote:
    hendren> Could you please give us a concrete example of what
    hendren> you are doing and why you are doing it.  John
    hendren> Jorgensen was working on improving our exception
    hendren> edges in Soot and we would like to see how (or if)
    hendren> that relates to his work.

I essentially pruned from the CFGs edges to exception handlers
from protected statements that could not possibly throw the type
of exception that the handler catches.  Intuitively, you would
think that such an analysis would also accomplish your goal:  if
exceptions from the nested synchronized block are always caught
by the nested block's exception handler, then there will be no
edge to the outer block's handler from statements in the inner
synchronized block.  

But the handlers for synchronized blocks catch Throwable,
i.e. they catch absolutely any exception, including asynchronous
ones.  As a result of this, the pruned graphs I produce can still
include edges from the inner block to the outer handler, though
I'll concede that this is of dubious utility.  In the case of
synchronized blocks generated by Sun's javac since Java 1.3 (when
javac started producing catch clauses that include themselves in
their own protected region), I think my pruned control flow graphs could
potentially produce the same CFGs as your modification.  though
they don't not right now because of a bug in which your
proposal revealed (the bug is that in the Jimple produced for
such a self-protecting handler, the initial assignment of the
caught exception to a local is not necessarily included in the
protected region).

Your proposal would affect the handling of bytecode generated for
synchronized blocks by older compilers, and code generated for
try blocks that have nothing to do with synchronization.  In
those cases, I'm still not sure if we can do away with the edges
from the inner try block to the outer catch.

I'll try to explain the rationale for what I did with an
example, based on yours:

    void synchUpdate(int[] values, int index, 
		     LockObject inner, LockObject outer) {
	synchronized (outer) {
	    synchronized(inner) {
		inner.value = index;
		int i = values[index];
		outer.value = i;
	    }
	}
    }

The code generated for that Java is roughly equivalent to the
following try blocks, with comments indicating operations  which
cannot be represented explicitly in Java source (this code
corresponds to what Sun's javac produced before Java 1.3):

    void tryUpdate(int[] values, int index, 
		   LockObject inner, LockObject outer) {
	try {
	    // entermonitor(outer)
	    try {
		// entermonitor(inner)
		inner.value = index;
		int i = values[index];
		outer.value = i;
		// exitmonitor(inner)
	    } catch (Throwable t) {
		// exitmonitor(inner)
		throw t;
	    }
	    // exitmonitor(outer)
	} catch (Throwable t) {
	    // exitmonitor(outer)
	    throw t;
	}
    }

Now imagine that the assignment to i in the inner try block
throws an ArrayIndexOutOfBoundsException. The exception gets
caught by the inner catch block. But before its exitmonitor
statement gets executed, some asynchronous exception occurs ---
the VM throws InternalError or some other thread inflicts our
thread with ThreadDeath.  As a result, the outer exception
handler is invoked before any statements in the inner handler are
completed.  In this case, that means the inner monitor might not
be exited before the outer one is, a Bad Thing which is
presumably the reason that javac now produces code where an
exception raised by the handler reinvokes the same handler.

As for code generated for other try blocks, we want to ensure
that we do not lose the ability to recognize that in the
following code it is possible for "b" to get set to 1 even though
"a" remains 0:

    static int a = 0;
    static int b = 0;

    void tryUpdate(int[] values, int index, 
		   LockObject inner, LockObject outer) {
	try {
	    try {
		inner.value = index;
		int i = values[index];
		outer.value = i;
	    } catch (Throwable t) {
		a = 1;
	    }
	} catch (Throwable t) {
	    b = 1;
	}
    }

I'm still not sure whether there are any circumstances where
your proposal would affect our analysis of such cases.  Thanks
for giving me the occasion to think about this again from a new
perspective.

I have just put a technical report describing my project at 

  http://www.sable.mcgill.ca/publications/techreports

in case you want to see a more complete explanation of why there
are edges to handlers from the predecessors of statements that
may throw exceptions, as well as from the statements themselves.

My code is not ready for integration into a Soot release, but it
is available from our source repository, at 

  http://svn.sable.mcgill.ca/viewcvs/soot/branches/soot-2-exceptional/

via the web interface, or at 

  http://svn.sable.mcgill.ca/soot/soot/branches/soot-2-exceptional/

if you have svn.

-- 
John Jorgensen		jjorge1@cs.mcgill.ca