Pointer analysis

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.
Example.
For the following example program, a points-to analysis would compute that the points-to set of codice_1 is {codice_2, codice_3}.
int x;
int y;
int* p = unknown() ? &x : &y;
Introduction.
As a form of static analysis, fully precise pointer analysis can be shown to be undecidable. Most approaches are sound, but range widely in performance and precision. For large programs, some tradeoffs may be necessary to make the analysis finish in reasonable time and space. Two examples of these tradeoffs are:
The disadvantage of these simplifications is that the calculated set of objects pointed to may become less precise.
Context-Insensitive, Flow-Insensitive Algorithms.
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. 
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 the LLVM codebase.
Flow-Insensitive Approaches.
Many approaches to flow-insensitive pointer analysis can be understood as forms of abstract interpretation, where heap allocations are abstrated by their allocation site (i.e., a program location).
Many flow-insensitive algorithms are specified in Datalog, including those in the Soot analysis framework for Java.
Context-sensitive, flow-insensitive 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). 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:
Call-site sensitivity.
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.
int *id(int* x) {
 return x;
int main() {
 int y;
 int z;
 int *y2 = id(&y); // call-site 1
 int *z2 = id(&z); // call-site 2
 return 0;
For this program, a context-insensitive analysis would (soundly but imprecisely) conclude that can point to either the allocation holding or that of , so and may alias, and both could point to either allocation. A callsite-sensitive analysis would analyze twice, once for call-site 1 and once for call-site 2, 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 .
Object sensitivity.
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.
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.