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 generalization of pointer analysis is shape analysis.

Introduction

Performing pointer analysis on all but the smallest of programs is a very resource intensive activity. Various simplifications have been made to reduce this overhead, the disadvantages of these simplifications is that the calculated set of objects pointed to may be larger than it is in practice.

Simplifications include:

Treating all references to a structured object as being to one object.

Ignoring flow-of control when analysing which objects are assigned to pointers, known as context-insensitive pointer analysis (when ignoring the context in which function calls are made) or flow-insensitive pointer analysis (when ignoring the control flow within a procedure).

Algorithms

• Steensgaard's algorithm
• Andersen's algorithm

See also

• Alias analysis
• Escape analysis
• Shape analysis (software)

References

• Michael Hind (2001). "Pointer analysis: haven't we solved this problem yet?". PASTE '01: Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. ACM. pp. 54–61. ISBN 1-58113-413-4. http://www.cs.trinity.edu/~mlewis/CSCI3294-F01/Papers/p54-hind.pdf. 
• Bjarne Steensgaard (1996). "Points-to analysis in almost linear time". POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages. ACM. pp. 32–41. ISBN 0-89791-769-3. http://cms.dc.uba.ar/materias/aap/2008/c2/descargas/pointsTo.pdf. 
• Andersen, Lars Ole (1994). Program Analysis and Specialization for the C Programming Language (PhD thesis). http://eprints.kfupm.edu.sa/59416/.