Readings about Pointer Alias Analysis
Terminology:
- Alias: An alias occurs at some program point when two or more names exist for the same memory locations.
- Recursive Structure: A structure is recursive if any of its fields (directly or indirectly) points to the same structure, otherwise, it is called non-recursive structure.
- Flow-sensitivity: This dimension considers whether the control flow information of a procedure is used during the analysis.
- Context-sensitivity: This dimension considers whether the calling context is used when analysing a function or can values flow from one call through the function return to another caller.
Surveys:
- M. Hind. Pointer Analysis: Haven't We Solved this Problem Yet? In PASTE 2001. Link
- V. Raman. Pointer Analysis - A Survey. 2004. Link
- D. Rayside. Points-to Analysis. MIT CSAIL. 2005. Link
Milestones:
- W. Landi. Undecidability of Static Analysis. In ACM Letters on Programming Languages and Systems, December 1992.
Link
- W. Landi and B. Ryder, "A safe approximate algorithm for inter-procedural pointer aliasing". In PLDI 1992.
Link
- J. Choi, M. Burke and P. Carini, "Efficient flow-sensitive inter-procedural computation of pointer-induced aliases and side effects,", In POPL'93, pp.233-245, January 1993
Link
- M. Emami, A practical inter-procedural alias analysis for an optimizing/paralleling C compiler, Master thesis, School of Computer Science, McGill University, August 1993.
Link
- L. Andersen. Program Analysis and Specialization for the C Programming Langusages. PhD thesis, DIKU, University of Copenhagen, May 1994.
Link
- M. Emami, R. Ghiya, and L. Hendren. Context-sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers. In PLDI 1994.
Link
- R. Wilson and M. Lam. Efficient Context-sensitive Pointer Analysis for C Programs. In PLDI 1995.
Link
- B. Steensgaard. Points-to Analysis in Almost Linear Time. In POPL 1996.
Link
- S. Horwitz. Precise Flow-insensitive May-alias Analysis is NP-hard. In ACM Transactions on Programming Languages and Systems, January 1997.
Link
- R. Wilson. Efficient Context-sensitive Pointer Analysis for C Programs. PhD thesis, Stanford University, Dec 1997.
Link
- T. Reps. Program Analysis via Graph Reachability. Information and Software Technology 40, 11-12, pp. 701-726. 1998.
Link
- N. Heintze and O. Tardieu. Demand-Driven Pointer Analysis. PLDI'2001.
Link
- N. Heintze and O. Tardieu. Ultra-fast Aliasing Analysis using CLA: A Million Lines of C Code in a second. PLDI'2001.
Link
- M. Berndl, O Lhotak, F. Qian, L. Hendren and N. Umanee. Points-to Analysis using BDDs. PLDI'2003.
Link Slides
- D. Pearce, P. Kelly and C. Hankin. Efficient Field-Sensitive Pointer Analysis for C. PASTE'2004.
Link
- J. Whaley and M. Lam. Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams. PLDI'2004 (Best Paper).
Link
- M. Sridharan, D. Gopan, L. Shan, R. Bodik. Demand-Driven Points-to Analysis for Java. OOPSLA'2005.
Link
- A. Milanova, A. Rountev and B. Ryder. Parameterized Object Sensitivity for Points-to Analysis for Java. ACM Transactions on Software Engineering and Methodology, 14(1):1-41, January, 2005.
Link
- C. Lattner and V. Adve. Automatic Pool Allocation: Improving Performance by Controlling Data Structure Layout in the Heap. PLDI'2005 (Best Paper).
Link
- O. Lhotak. Program Analysis using Binary Decision Diagrams. PhD thesis, McGill University, January 2006.
Link
- M. Sridharan, R. Bodik. Refinement-Based Context-Sensitive Points-To Analysis for Java. PLDI'2006.
Link
- J. Whaley. Context-Sensitive Pointer Analysis Using Binary Decision Diagrams. PhD thesis, Stanford University, March 2007.
Link
- B. Hardekopf and C. Lin, The Ant and the Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code. PLDI 2007 (Best Paper).
Link
- C. Lattner, A. Lenharth and V. Adve. Making Context-Sensitive Points-to Analysis with Heap Cloning Practical For the Real World. PLDI 2007.
Link
- V. Kahlon. Bootstrapping: A Technique for Scalable Flow and Context-Sensitive Pointer Analysis. PLDI'2008.
Link
- X. Zheng, R. Rugina. Demand-Driven Alias Analysis for C. POPL'2008.
Link
- B. Hardekopf and C. Lin. Semi-Sparse Flow-Sensitive Pointer Analysis. POPL'2009.
Link