In computer science, pointer analysis, or points-to analysis, is a static code analysis technique that establishes which pointers, or heap references, can point to which variables, or storage locations. It is often a component of more complex analyses such as escape analysis. A closely related technique is shape analysis.
This is the most common colloquial use of the term. A secondary use has pointer analysis be the collective name for both points-to analysis, defined as above, and alias analysis. Points-to and alias analysis are closely related but not always equivalent problems.
Consider the following C program:
A pointer analysis computes a mapping from pointer expressions to a set of allocation sites of objects they may point to. For the above program, an idealized, fully precise analysis would compute the following results:
| Pointer expression | Allocation site | |
|---|---|---|
&x | main::x | |
&y | main::y | |
u | main::x | |
v | main::y | |
p | main::x, main::y |
(Where X::Y represents the stack allocation holding the local variable Y in the function X.)
However, a context-insensitive analysis such as Andersen's or Steensgaard's algorithm would lose precision when analyzing the calls to id, and compute the following result:
| Pointer expression | Allocation site | |
|---|---|---|
&x | main::x | |
&y | main::y | |
u | main::x, main::y | |
v | main::x, main::y | |
p | main::x, main::y |
As a form of static analysis, fully precise pointer analysis can be shown to be undecidable.[1] Most approaches are sound, but range widely in performance and precision. Many design decisions impact both the precision and performance of an analysis; often (but not always) lower precision yields higher performance. These choices include:[2]
malloc or an object constructor),Pointer analysis algorithms are used to convert collected raw pointer usages (assignments of one pointer to another or assigning a pointer to point to another one) to a useful graph of what each pointer can point to.[3]
Steensgaard's algorithm and Andersen's algorithm are common context-insensitive, flow-insensitive algorithms for pointer analysis. They are often used in compilers, and have implementations in SVF[4] and LLVM.
Many approaches to flow-insensitive pointer analysis can be understood as forms of abstract interpretation, where heap allocations are abstracted by their allocation site (i.e., a program location).[5]
Many flow-insensitive algorithms are specified in Datalog, including those in the Soot analysis framework for Java.[6]
Context-sensitive, flow-sensitive algorithms achieve higher precision, generally at the cost of some performance, by analyzing each procedure several times, once per context. Most analyses use a "context-string" approach, where contexts consist of a list of entries (common choices of context entry include call sites, allocation sites, and types).[7] To ensure termination (and more generally, scalability), such analyses generally use a k-limiting approach, where the context has a fixed maximum size, and the least recently added elements are removed as needed. Three common variants of context-sensitive, flow-insensitive analysis are:
In call-site sensitivity, the points-to set of each variable (the set of abstract heap allocations each variable could point to) is further qualified by a context consisting of a list of callsites in the program. These contexts abstract the control-flow of the program.
The following program demonstrates how call-site sensitivity can achieve higher precision than a flow-insensitive, context-insensitive analysis.
| Pointer expression | Allocation site | |
|---|---|---|
&x | main::x | |
&y | main::y | |
u | main::x, main::y | |
v | main::x, main::y | |
p | main::x, main::y |
A callsite-sensitive analysis would analyze twice, once for main.3 and once for main.4, and the points-to facts for would be qualified by the call-site, enabling the analysis to deduce that when returns, can only point to the allocation holding and can only point to the allocation holding :
| Context | Pointer expression | Allocation site | |
|---|---|---|---|
[] | &x | main::x | |
[] | &y | main::y | |
[] | u | main::x | |
[] | v | main::y | |
[main.3] | p | main::x | |
[main.4] | p | main::y |
In an object sensitive analysis, the points-to set of each variable is qualified by the abstract heap allocation of the receiver object of the method call. Unlike call-site sensitivity, object-sensitivity is non-syntactic or non-local: the context entries are derived during the points-to analysis itself.
Type sensitivity is a variant of object sensitivity where the allocation site of the receiver object is replaced by the class/type containing the method containing the allocation site of the receiver object. This results in strictly fewer contexts than would be used in an object-sensitive analysis, which generally means better performance.