[Soot-list] Interprocedural flow analysis

[Antoine Mine]

> I'm currently looking into the
> soot.jimple.toolkits.annotation.purity.PurityIntraproceduralAnalysis class
> for inspiration. It's a bit difficult to follow, as I'm so new to soot, so
> any help would be appreciated. Especially letting me know if I'm heading in
> the right direction.

Dear Andy,

soot.jimple.toolkits.annotation.purity implements the combined points-to / 
side-effect / escape / purity analysis described in the paper "A Combined 
Pointer and Purity Analysis for Java Programs" by Alexandru Salcianu and
Martin Rinard.

It is a quite complex inter-procedural analysis and may not be what you 
want.
In particular, the analysis uses some specific framework.
Each method is analysed using an intra-procedural flow-sensitive 
ForwardFlowAnalysis, which is classical in Soot. However, there is also a
specific inter-procedural level that traverses the call-graph bottom-up 
(using a fix-point for recursive methods).
Each time a method is analysed, a summary (input-output relation) is 
computed. Actually, each intra-procedural analysis of a method m takes as 
argument the summary of all the methods m calls, and outputs a summary for 
m.
This framework is formalized in the abstract class 
AbstractInterproceduralAnalysis and specialized to the analysis
of Salcianu and Rinard in PurityInterproceduralAnalysis, using 
PurityIntraproceduralAnalysis to compute method summary. DirectedCallGraph 
is just an helper graph function. Other classes implement the (complex) 
data-structures to represent an program-state, as in Salcianu and Rinard.
Finally, the analysis suffers from scalability as well as precision 
problems due to the Java standard library. Indeed, the library 
is large (many undocumented helper methods), contains native methods
(that cannot be analysed) and cache mechanisms tend to render 
theoretically pure functions actually impure.
Thus, the analysis is "helped" a little bit, using the large tables at the 
top of PurityInterproceduralAnalysis.

The bottom line is that soot.jimple.toolkits.annotation.purity is probably 
not what you want.
Feel free, however, to ask more questions...

Best regards,
-
Antoine Mine