SDA SE Wiki

Computing precise points-to information needs a precise call-graph and computing a precise call graph needs points-to information.

One way to deal with this mutual dependency is to compute a context-insensitive call graph upfront with a fast, linear algorithm (e.g. Bacon's rapid type analysis), and use it during the points-to analysis. The drawback of this approach is that the graph will probably be much bigger than required because, lacking points-to information, too many methods will be included as potential targets for dynamically bound invocations. Thus the subsequent points-to analysis will waste time on analysing effectively unreachable code and its precision will degrade because it includes points-to information from such code.

A better alternative is to construct a context-sensitive call-graph on-the-fly, during computation of points-to relations. This talk will present an extension of Sridharan's field- and context-sensitive, refinement-based points-to analysis. This extension allows construction of a context-sensitive call-graph on-the-fly:

• Challenge
• Approach overview
• Extended graph representation
• Extended formalism
• Algorithms
• Examples
• Benchmark results
• Open issues (questions to discuss in the lab)

This variant of Sridharan's algorithms represents the maximum degree of precision and efficiency that we aim to implement and evaluate in the lab phase.

A summary of the entire approach of Sridharan is contained in his PLDI 2006 article [ Sridharan & Bodik 2006 ]. You can use it as a relatively concise overview of what your colleagues will present before your talk.

The details are in his PhD thesis [ Sridharan 2007 ]:

• Chapter 3 is an overview of all the three PTA variants (field-sensitive, context-sensitive, on-the-fly)
  • In particular, Section 3.4 (page 59-75) elaborates the on-the-fly approach
• Chapter 5 is an in-depth discussion of the context-sensitive variant
  • In particular, Section 5.3 (page 153-164) elaborates the refinement algorithm in pseudocode, including portions that integrate the on-the-fly approach.

CFL-Reachability as a solution to the “unrealizable path” problem is introduced by Reps: PDF, Citation

The “unrealizable paths” problem that arises if context-sensitive analysis is viewed as graph reachability is described in an earlier paper of Reps & Horowitz & Sagiv: PDF, Citation.

The first complete version of the talk will be presented (to GK) on Friday, Oct 01, 2010 at 14:30. We will then discuss open issues and once these are resolve, fine-tuning of the contents and presentation.