Program (2mb PDF)

  Invited Speakers
  Research Papers
  Student Research Comp.
  Doctoral Symposium
  Educators' Symposium
  Wiki Symposium
  Dynamic Lang. Symp.
  Practitioner Reports
  Lightning Talks
  Instant Arts School Exp.
Other Events
Resort Map (364kb PDF)
Resort Map (JPG)



view, help

"Demand-Driven Points-to Analysis for Java"




  > Research Papers > Analysis Analyzed

 : Tuesday

Demand-Driven Points-to Analysis for Java

San Diego Room
Tuesday, 13:30, 30 minutes



Manu Sridharan, UC Berkeley
Denis Gopan, University of Wisconsin
Lexin Shan, UC Berkeley
Rastislav Bodik, UC Berkeley

We develop pointer analyses suitable for use highly time-constrained environments, such as just-in-time (JIT) compilers and interactive development environments (IDEs). In such environments, the running time of the analysis is critical, leading one to consider demand-driven solutions. In the worst case, however, a demand-driven analysis can take as long as an exhaustive analysis. For long-running queries, such environments could use early termination and simply stop the analysis after some timeout. Previous demand-driven pointer analyses do not perform well under such early termination constraints.

We formulate Andersen's analysis for Java as a CFL-reachability problem, and observe that it has the balanced-parentheses property seen in other program analysis problems. We use this observation to develop two new demand-driven pointer analysis algorithms, DemandFB and TargetedFS, that are suitable for use with early termination. DemandFB is an extremely simple field-based algorithm that essentially performs a depth-first search of the CFL-reachability graph. TargetedFS iteratively adds field-sensitivity to DemandFB where profitable, exploiting the balanced-parentheses structure for efficiency. We show that DemandFB is a very effective algorithm under early termination; for our clients, it can answer 89-94% of virtual call queries as precisely as an exhaustive field-sensitive Andersen's analysis, with each query taking less than 2ms. DemandFB can answer all queries in hot methods of javac with the same precision as an exhaustive field-sensitive Andersen's analysis, with a 34x speedup (and a 16x speedup over exhaustive field-based analysis). We also show that given a limited budget, TargetedFS is better than known demand-driven pointer analyses at closing the gap between DemandFB and exhaustive field-sensitive Andersen's.