Re: Tightening Exception-based Control flow graph

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

    vranganath> I have a comment regarding the last 2 bullets.
    vranganath> In general, a control statement determines which
    vranganath> of it's successors gets control after it
    vranganath> completes.  Given this notion an exception
    vranganath> raising statement is a control statement.  The
    vranganath> definition was confined to control constructs
    vranganath> such as if, while, switch, ... in the days
    vranganath> earlier to languages supporting exceptions.  So,
    vranganath> bullet 3 is untrue in the presence of exception
    vranganath> only if the way the successor is determined by a
    vranganath> control statement is defined as dependent on a
    vranganath> boolean expression. 

Sure, but I guess that's my point.  With old fashioned
conditional branches, the choice of which edge you take depends
solely on the value of that boolean expression (or integer
expression in the case of a switch). The expression is explicitly
available in the program statement, and it is stated in terms of
constants and variables that are explicitly present in the
method's code, so even if a static analysis cannot determine the
value of the expression, it is at least clear where the value
comes from.

In principle, you can also express whether or not an exceptional
edge is taken in the form of a boolean expression, but the
expression is not explicitly available in the program statement,
and it may depend on factors that are not even mentioned in the
the function's code, such as whether referenced classes can be
loaded successfully given the current class path, whether the VM
is running short of memory, or whether some other thread is about
to ignore Sun's recommendations and call Thread.stop().

If you want to say that this is a difference of degree rather
than kind, fine, I'll concede that. But it's an awfully big
difference of degree.

    vranganath> As for the last bullet, asynchronous exceptions
    vranganath> can ensure that this bullet is true.  So in my
    vranganath> opinion, exceptional edges are different from
    vranganath> normal control flow edges but they are still
    vranganath> control flow edges, and any statement that can
    vranganath> raise an exception is a valid control statement.

The Java Language Specification certainly gives VM implementors
the leeway to delay checks for asynchronous exceptions to
convenient points (JLS 11.3.2). I'm not sure that this leeway is
available to Soot, though, since Soot is a bytecode-to-bytecode
transformer, not a VM. Shouldn't our analyses reflect the
possible behaviour of our generated bytecode on Java
implementations which choose to deliver asynchronous exceptions
immediately as well as those which delay them until the next
control transfer point? I don't know the answer to this question,
so I opt for a conservative approach.

    vranganath> Well, independent of the type or sort of
    vranganath> exception that may occur at the first statement
    vranganath> of the inner handler, if the inner handler was
    vranganath> covered by the outer catch block, this exception
    vranganath> will be caught by the outer handler.  

That's true, but that's not the issue. The issue is that the CFG
should indicate that it is possible for statements in the outer
handler to be executed (to completion) without any statements in
the inner handler being executed (to completion).

>     >> 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;  //A
>     >>     int i = values[index]; //x
>     >>     outer.value = i;       //y
>     >>   } catch (Throwable t) {
>     >>     a = 1;                //B
>     >>   }
>     >> } catch (Throwable t) {
>     >>   b = 1;                  //C
>     >> }
> 

    vranganath> Consider the following CFG:
    vranganath> 	A -> B,
    vranganath> 	x -> B,
    vranganath> 	y -> B,
    vranganath> 	B -> C

    vranganath> Let's consider your scenario, an exception at x
    vranganath> will transfer control to B, but before the B
    vranganath> begins an asynch exception occurs and transfers
    vranganath> control to C and C completes.  As the exception
    vranganath> occurs after A, index was assigned to inner.value
    vranganath> at A and 1 was assigned to B.  So, the given
    vranganath> graph gives enough information to capture your
    vranganath> scenario.

But in the given graph, the only way to get from A to C is
through B, which implies that whenever "b" has been assigned the
value 1 (by statement C), "a" has also been assigned the value 1
(by statement B). That's not true, "a" might still have the value
0, because you don't necessarily have to complete statement B to
get to statement C.

Incidentally, there really shouldn't be an edge from y to B,
since if y completes successfully, there hasn't been any
exception and B won't be executed (and y has no side effects; if
it did we would still need an edge from y to B, since those side
effects might occur before y throws its exception, so we would
need to flow the side effects into the handler).

    vranganath> On the other hand, with the original graph,

    vranganath> 	A -> B,	A -> C,
    vranganath> 	x -> B, x -> C,
    vranganath> 	y -> B, y -> C
    vranganath> 	B -> C

Again, there should be no edges from y to B and C, but the
existing CFG classes in Soot do produce them.

    vranganath> The data flow analysis will indicate that the
    vranganath> assignment to index.value at A is equally
    vranganath> eligible to be visible visible at B and C which
    vranganath> is incorrect by the exceution semantics of JVM.

I don't understand why it isn't potentially visiable at both B
and C. If statement x throws an exception caught at B and B does
not itself raise an exception, then the definition of index.value
at A will reach B. If statements x and B both throw exceptions,
the definition of index.value at A will reach C, won't it? 
Obviously I'm missing something here.

    vranganath> I think the same suggestion would be applicable
    vranganath> to any intermediate representation as it based on
    vranganath> language and JVM semantics and not based on the
    vranganath> IR semantics.

Well, maybe there should be a policy that in all IRs, the initial
statement in an exception handler should be an empty placeholder
that does nothing (and hence can be considered immune to
exceptions). That would certainly simplify program analysis
(which is, after all, the goal of an IR), but I don't see how it
is imposed by Java semantics. 

Are you saying that because the initial instruction in most
exception handlers just stores or pops the exception object from
the stack---pure ALU operations which are not subject to
synchronous exceptions---we can safely assume that the first
instruction in any exception handler will always complete
successfully? But that's just a matter of convention; I don't
know of any rule that says you can't ignore the exception object
entirely and, say, dereference a potentially null pointer as the
first instruction in your handler. And then there are those pesky
asynchronous exceptions, which you can't ignore when the catch
type is Throwable.

-- 
John Jorgensen		jjorge1@cs.mcgill.ca