Field Flow Sensitive Pointer and Escape Analysis for Java as Logic Programs Using SSA
Prakash Prabhu and Priti Shankar

IISc-CSA-TR-2006-10
(September 2006)

Available formats: [ps] [ps.gz]

Filed on September 19, 2006
Updated on September 19, 2006


We present a flow and context sensitive combined pointer and escape analysis
for Java. Our analysis provides both context and flow sensitivity for Java
fields and it does so by extending the Heap Array SSA form. We first express
a flow-sensitive pointer analysis as a set of deduction rules on database
relations in Datalog, a logic programming language. We then get a context
sensitive pointer analysis using techniques developed by Whaley and Lam and
introducing new $\phi$ functions for Heap Array SSA. Adding a few more
deduction rules gives an escape analysis. The advantages of this method are
two fold: Firstly, a precise points-to analysis directly provides a precise
escape analysis result with very little overhead and hence no separate heavy
weight analysis to determine escape information needs to be carried out.
Secondly, a precise points-to analysis can help in a variety of other compiler
optimizations like code motion and dead store elimination. We have implemented
this analysis in the \textit{SOOT} open source framework and used
\textit{bddbddb} (Binary Decision Diagram based Deductive Database) - a solver
for Datalog rules, to obtain the analysis results. We have run our analysis on
a set of 14 Java programs and compared our escape analysis results with a
field flow insensitive (FFIS) analysis. Our experimental results show that
the running times of our analysis are comparable to a FFIS analysis while
doing much better in many cases. At the same time achieving improvements
ranging from 21\% to 79\% in the number of one-level captured objects.


Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2006/10/.

Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]