Pointer analysis also called Points-to analysis is a static code analysis technique which refers to analyzing the memory locations pointers or heap references point to and how the transformation happens. A related term called Alias analysis is used in compiler theory to analyze the ways to access the memory locations.
Flow-sensitive pointer analysis computes for each program point what memory locations pointer expressions may refer to. Flow-insensitive pointer analysis computes what memory locations pointer expressions may refer to, at any time in program execution. The Flow-sensitive analysis is too expensive. Generally flow-insensitive pointer analysis is used for complete program analyses.
There are two main algorithms studied namely Steensgaard’s Algorithm and Andersen’s Algorithm.
The basic first idea of each is to map a pointer object to the sets of possible memeory locations that it may point to. This is called Referencing (A = &B) and it says that the location A points to B if “Bound” location set points that B may be found is a subset of points that A points to. This idea is extended to define Aliasing that says two pointers are equal if location points set of one is subset of other. Dereferencing says the location points set of RHS is subset of LHS.
following is a simple example :
int a = &b;
// loc(b) is a subset of pts(a).
int a = b;
// pts(a) = pts(b).
int a = *b;
// it means pts(*b) is a subset of pts(a).
Lets says intially we have some initial points-to-set elements, We then build a Directed inclusion Graph. Where each of the nodes are memory locations and edges (A -> B) refer to pts(a) is subset of pts(b). For an “Error-less” program, it should compute to a finite transitive closure.
For computing the transitive closure, the key difference to make note of is given two pointers pointing to two location point sets , Steensgaard’s approach merges the two set to create a new set, the Andersen’s approach says that one location point set may be subset of other and carries out this “subset of” relation to finally reduce to a transitive closure.
References :
- https://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec06-PointerAnalysis.pdf
- https://www.cs.cmu.edu/~aldrich/courses/15-819O-13sp/resources/pointer.pdf
- https://www.youtube.com/watch?v=erIkdIwypbE