Most scalable approaches to inter-procedural dataflow analysis do not take into account the order in which fields are accessed, and methods are executed, at run-time. That is, they have no inter-procedural flow-sensitivity. In this chapter we present an approach to dataflow analysis named \emph{Simulated Execution}. It is flow-sensitive in the sense that a memory accessing operation (call or field access) will never be affected by another memory access that is executed there after in all runs of a program. This makes Simulated Execution strictly more precise than the most frequently used flow-insensitive approaches. We also outline a proof of correctness using abstract interpretation. Finally, although we present Simulated Execution as a dataflow algorithm applied to context-insensitive Points-to Analysis, it can be applied on any inter-procedural dataflow problem and in a context-sensitive manner.

Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, software engineering applications used in an edit-compile cycle need points-to analysis to be fast and precise.

In this article, we present a new context- and flow-sensitive approach to points-to analysis where calling contexts are distinguished by the points-to sets analyzed for their call target expressions. Compared to other well-known context-sensitive techniques it is faster in practice, on average, twice as fast as the call string approach and by an order of magnitude faster than the object-sensitive technique. In fact, it shows to be only marginally slower than a context-insensitive baseline analysis. At the same time, it provides higher precision than the call string technique and is similar in precision to the object-sensitive technique. We confirm these statements with experiments using a number of abstract precision metrics and a concrete client application: escape analysis.

Points-to analysis is a static program analysis that extracts reference information from programs, e.g., possible targets of a call and possible objects referenced by a field. Previous works evaluating different approaches to context-sensitive Points-to analyses use coarse-grained precision metrics focusing on references between source code entities like methods and classes. Two typical examples of such metrics are the number of nodes and edges in a call-graph. These works indicate that context-sensitive analysis with a call-depth k = 1 only provides slightly better precision than context-insensitive analysis. Moreover, these works could not find a substantial precision improvement when using the more expensive analyses with call-depth k > 1. The hypothesis in the present paper is that substantial differences between the context-sensitive approaches show if (and only if) the precision is measured by more fine-grained metrics focusing on individual objects (rather than methods and classes) and references between them. These metrics are justified by the many applications requiring such detailed object reference information. In order to experimentally validate our hypothesis we make a systematic comparison of ten different variants of context-sensitive Points-to analysis using different call-depths k >= 1 for separating the contexts. For the comparison we use a metric suite containing four different metrics that all focus on individual objects and references between them. The main results show that the differences between different context-sensitive analysis techniques are substantial, also the differences between the context-insensitive and the context-sensitive analyses with call-depth k = 1 are substantial. The major surprise was that increasing the call-depth k > 1 did not lead to any substantial precision improvements. This is a negative result since it indicates that, in practice, we cannot get a more precise Points-to analysis by increasing the call-depth. Further investigations show that substantial precision improvements can be detected for k > 1, but they occur at such a low detail level that they are unlikely to be of any practical use.