[Soot-list] Exceptional edges in control flow analysis in SOOT

[John Jorgensen]

    wuxiaoquan07> When building CFG with exceptional edges, why
    wuxiaoquan07> the ExceptionalUnitGraph adds edges from the
    wuxiaoquan07> predecessors of the thrower to the catcher?

When an instruction throws an exception, at least some of the
state changes normally associated with that instruction might not
have occurred.  So you need the edges from the thrower's
predecessors to the catch instruction in order to preserve the
correctness of data flow analyses performed on the CFG.

This is explained in more detail in section 2.4 of the technical
report on the exceptional control flow analysis
(http://www.sable.mcgill.ca/publications/techreports/#report2003-3)
but an example from that section probably suffices to make the
idea clear.  Let's say Soot is analyzing this code snippet:

 int l0 = 0;                                          // 1
 try {						      // 2
   l0 = o.f * o.f + 1;   // rhs necessarily positive. // 3
   return l0;					      // 4
 } catch (NullPointerException e) {		      // 5
   System.err.println("NullPointerException");	      // 6
   if (l0 == 0) return 0; else return 1;	      // 7
 }						      // 8

if o contains a null pointer, line 3 will throw an exception,
caught at line 5, before it changes the value of l0.  

Let's say you're using the CFG generated from this program
fragment in some fancy constant propagator.  If the only edge
leading to line 5's node is from line 3, your constant propagator
could mistakenly conclude that the value of l0 must be non-zero
(since the last assignment to l0 was of "o.f * o.f + 1", and "o.f
* o.f" cannot have a value of -1), leading to the conclusion that
you couldoptimize away the true branch of the if statement on
line 7.

In fact, exactly the opposite is true; if an exception is thrown
to line 5, l0 still has the value 0, and it's the false branch of
the if statement which you could optimize away.  

Moreover, you could argue that the only edge to line 5 should be
from line 1, with no edge to line 5 from line 3, since the only
way that line 3 can execute to completion is if it does not throw
an exception. The main reason that Soot includes the edge from 3
to 5 (by default, there are switches to turn this off) is that in
Soot's intermediated representations, method calls on the right
hand side of an assignment might occur even if the assignment to
the left hand side is prevented by an exception.  (The secondary
reason is that I was never clear on what guarantees the JVM
provides about the timing of asynchronous exceptions).

I appreaciate that there are purposes other than data flow
analysis to which you could put the CFGs---human program
understanding comes to mind---for which the edges from the
thrower's predecessors are unwelcome.  It's possible that for
those purposes you could combine the results of, say,
ExceptionalGraph.getUnexceptionalSuccsOf() (for unexceptional
program flow) and and ExceptionalGraph.getExceptionDests()
(for exceptions) to get what you're looking for (but treat that
suggestion with skepticism; it's been a long time since I've
looked at this code).