Field Flow Sensitive Pointer and Escape Analysis for Java using Heap Array SSA [abstract] (SpringerLink, PDF)
Prakash Prabhu and Priti Shankar
Proceedings of the 2008 International Symposium on Static Analysis (SAS), July 2008.
Context sensitive pointer analyses based on Whaley and Lam's bddbddb
system have been shown to scale to large Java programs. We provide a technique
to incorporate flow sensitivity for Java fields into one such analysis and
obtain an escape analysis based on it. First, we express an intraprocedural
field flow sensitive analysis, using Fink et al.'s Heap Array SSA form in
Datalog. We then extend this analysis interprocedurally by introducing two new
\phi functions for Heap Array SSA Form and adding deduction rules corresponding
to them. Adding a few more rules gives us an escape analysis. We describe two
types of field flow sensitivity: partial (PFFS) and full (FFFS), the former
without strong updates to fields and the latter with strong updates. We compare
these analyses with two different (field flow insensitive) versions of
Whaley-Lam analysis: one of which is flow sensitive for locals (FS) and the
other, flow insensitive for locals (FIS). We have implemented this analysis on
the bddbddb system while using the SOOT open source framework as a front end.
We have run our analysis on a set of 15 Java programs. Our experimental results
show that the time taken by our field flow sensitive analyses is comparable to
that of the field flow insensitive versions while doing much better in some
cases. Our PFFS analysis achieves average reductions of about 23% and 30% in
the size of the points-to sets at load and store statements respectively and
discovers 71% more ``caller-captured'' objects than FIS.