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 p is.

int x;
int y;
int* p = unknown ? &x : &y;

Introduction

Techniques 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.

Algorithms

Pointer analysis algorithms are used to convert collected raw pointer usages to a useful graph of what each pointer can point to.
The two primary algorithms are Steensgaard's algorithm and Andersen's algorithm.