Re: Tightening Exception-based Control flow graph

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

I think I replied one day too soon :-).  

Two days ago, I paid more attention to what I thought your
proposal was intended to do (remove control flow edges leading
from the inner try block to the outer handler) rather than to how
it accomplished that goal.  Since I think there _should_ be edges
from the inner try block to the outer handler (a second attempt
to explain why will follow), I thought there was something wrong
with the proposal, but I wasn't sure what. So I waited a day to
reply.

Last night, after studying the clarification you provided Laurie,
I realized something which had escaped me the day before: if the
inner try block's handler is in the scope of the outer try block
but not within its own protected region, then exceptions thrown
by instructions within the inner handler will continue to to be
caught by the outer handler even after being modified by your
proposal. So---just as you said yesterday---the effect of the
code you produce remains unchanged.

How, then, was the modification simplifying your CFGs even though
the control flow was unaffected? I couldn't figure that out
yesterday, but I felt that you deserved some response without
further delay. So I produced yesterday's incoherent reply.  (I hope
you noticed the equivocal circumlocutions: I was careful to say
"I'm still not sure whether there are any circumstances where
your proposal would affect our analysis of such cases", rather
than "you're wrong" :-)).

Walking home today, I think I figured out the missing piece. I
had forgotten that you are dealing with the old UnitGraph and
BlockGraph classes, while I am accustomed to thinking in terms of
the behaviour of my experimental replacements for them. I agree
that your proposed change does not change the behaviour of the
code. And if I feed the output Jimple you describe to my CFG
classes, the resulting graph does indeed continue to have edges
from every instruction in the inner try block to the outer
handler as well as the inner handler. The reason that those
edges do not exist when you run your modification through Soot is
that the old Graph classes are broken. 

Or, less provocatively, they reflect an inconsistent notion of
what a CFG edge should mean.  In my mind, so long as the CFG does
not distinguish between exceptional and unexceptional edges
(which it probably should, but I was restricting my modifications
to changes that would not require rewriting Soot's existing
transformations), the meaning of a control flow edge from
statement A to statement B should be that if A completes, the
next statement to complete might be B (_will_ be B if there is only
one edge leaving A).  As a result, if statement C might throw an
exception to a handler starting at statement D, the CFG should
contain edges from all the _predecessors_ of statement C to
D. There doesn't need to be an edge from C itself to D unless C
might have some side effect that occurs even when it is
interrupted by an exception.

This is explained in some detail in section 2.4 of my technical
report
(http://www.sable.mcgill.ca/publications/techreports/#report2003-3)
but I'll try to at least illustrate the motivation below, with
reference to your example.  The main motivation is to preserve
the correctness, and as much as possible the precision, of
dataflow analyses that use the CFG.

So to deal with the details...

    vranganath> About the type of the exception, I do not see how
    vranganath> the catching of the most generic type of
    vranganath> exception will influence the proposed changes.
    vranganath> In a nested try block catching Throwable, any
    vranganath> exception thrown in it will be trapped by it's
    vranganath> handler before propogating it to the enclosing
    vranganath> handler (if any and if at all it does propogate).
    vranganath> Just based on Type equality and try-catch
    vranganath> semantics it should be safe to remove such
    vranganath> dubious nesting.

The type of exception matters because no matter what the first
statement is in the inner handler, it might throw an asynchronous
exception, which would be caught by the outer handler. That means
that the CFG has to include an edge from each of the throwing
statement's predecessors to both handlers, not just the inner
handler, since the next statement to complete execution after the
exception is thrown might be in the outer handler rather than the
inner one.

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

    vranganath> I do not quite understand this too.  Could you
    vranganath> please elaborate how the proposed changes will
    vranganath> prevent this situation?  Cos, the following would
    vranganath> be the jimple after the proposed changes and it
    vranganath> does not change the order or the way exceptions
    vranganath> will be handled except for the pruning the try
    vranganath> blocks. 

The example was supposed to provide an intuitive illustration of
why there needs to be a CFG edge from the statement I've now
labeled A to statement C as well as to B.  The edge from A to C
allows a dataflow analysis to see that it is possible for "index"
to be assigned to "inner.value" and 1 to be assigned to "b"
without any new values being assigned to "i", "outer.value", or
"a" (which is what happens if "values[index]" throws an
ArrayIndexOutOfBoundsException and then some asynchronous
exception occurs just before the assignment to a).  Of course the
CFG is actually built out of Jimple statements, where other
nuances exist, but the idea is most easily illustrated with Java
source.

    vranganath> Can you please explain the above 2 scenarios,
    vranganath> with a Jimple example, as to why the proposed
    vranganath> changes is unsound?  

For my purposes, since I am trying to build CFGs for arbirtrary
methods, there really isn't any difference between the 2
scenarios (i.e. exception handlers generated to implement
synchronized blocks and exception handlers generated from
explicit try/catch blocks in Java source). I focused on the
try/catch example because there it is plain why I want the edges
from inner block statements to both handlers. In the synchronized
block example, where the handlers just exit monitors, it is less
obvious (though the existence of the edges from the inner try block
to the outer handler for code generated by pre-1.3 javac does
illustrate what was wrong with that code: the inner monitor might
not be exited if an exception occurs at the wrong instant).

As a Jimple example, I will use the Jimple you present as your
translation for tryUpdate() (where the effect of your
transformation is to change the range of the second "catch" from
"from label0 to label3" to "from label1 to label3").  Again, I
have added labels as comments:

    vranganath>       label0:
    vranganath>          r2.<t: int value> = i0; //A
    vranganath>          i1 = r1[i0]; //B
    vranganath>          r3.<t: int value> = i1; //E

    vranganath>       label1:
    vranganath>          goto label3;

    vranganath>       label2:
    vranganath>          $r4 := @caughtexception; //C
    vranganath>          r5 = $r4;
    vranganath>          z2 = 1;

    vranganath>       label3:
    vranganath>          goto label5;

    vranganath>       label4:
    vranganath>          $r6 := @caughtexception; //D
    vranganath>          r7 = $r6;
    vranganath>          z3 = 1;

    vranganath>       label5:
    vranganath>          return;

    vranganath>          catch java.lang.Throwable from label0 to label1 with label2;
    vranganath>          catch java.lang.Throwable from label1 to label3 with label4;

There should be a CFG edge from statement A to statement D, to
reflect the fact that if statement B throws an exception that is
caught at label2, but an asynchronous exception immediately
arrives and is caught by label4, then it is possible for new
values to be assigned to r2.value and $r6 without any new values
being assigned to i1, or $r4.  Similarly there needs to be an
edge from B to D to reflect what could happen if exceptions occur
during the execution of statements E and C.

(I'm fudging something a bit here.  The "$r4 := @caughtException"
statement is really some Jimple bookkeeping which does not
correspond directly to anything in the input bytecode. So there
wouldn't be any harm in saying that our imagined asynchronous
exception cannot occur until after C completes, in which case you
wouldn't need the edge directly from A and B to D. But the CFG
building code must deal with any of Soot's intermediate
representations, not just Jimple, and in at least one of those
representations, Baf, the first statement in an exception handler
does correspond to real code.)

It's true that the Soot you're working with will not produce the
edge from A to D.  That's because when its CompleteUnitGraph
connects the predecessors of an excepting statement to the
catching handler, it fails to notice cases where the first
statement in the handler might itself throw an exception that
gets caught within the method. I fixed that by computing the
transitive closure of cascading exceptions (or at least I tried
to).  

I fed your Jimple to my graph constructor, and, sure enough,
there are edges from A to D as well as C.  And this despite the
fact that for this example the "TrapTightener" pass which
precedes my CFG builder (a kludge to prevent verification errors)
actually makes exactly the same change to the trap ranges as you
do (see section 3.4.4 of my report for information about the
TrapTightener).  I had actually forgotten about the TrapTightener
until I ran the example, so I haven't thought through whether it
would necessarily make identical changes to Trap ranges as you
do.

So, to summarize this rambling reply, I believe it is true that
your proposal does not, in itself, change the behaviour of output
code. With the existing CFG implementations, though, it does
cause dataflow analyses to be less accurate than they would
otherwise be, because of the missing edges from the inner try
block to the outer try block. With my CFG implementation, the
edge would not be missing, so your modification would trim the
output exception tables, but not simplify the CFGs as you want it
to.

    vranganath> The bug does exist :-)

I think if I fix this bug which leaves "local := @caghtException"
outside of self-protecting handlers, then my CFGs for
synchronized blocks generated by post 1.2 javac will only include
edges from the inner block to the inner try, but I have yet to
test that supposition. Moreover, there are other problems with my
graphs that might prevent them ever being merged into the main
Soot release.

    vranganath> On the same note, I wanted to know if soot was
    vranganath> extended in a considerable way, would Sable group
    vranganath> be willing to accept the changes and merge it
    vranganath> into their main branch providing the contributor
    vranganath> write access to the repository?  Or would the
    vranganath> contributor have to maintain a separate branch of
    vranganath> Soot from there on?

I can't comment on this, since I'm a departed student and not one
of Soot's current keepers.

-- 
John Jorgensen		jjorge1@cs.mcgill.ca