Donglin Liang
Abstract
To function on programs written in languages such as C that make extensive use of pointers, automated software engineering tools require safe alias information. Existing alias-analysis techniques that are sufficiently efficient for analysis on large software systems may provide alias information that is too imprecise for tools that use it: the imprecision of the alias information may (1) reduce the precision of the information provided by the tools and (2) increase the cost of the tools. This paper presents a flow-insensitive, context-sensitive points-to analysis algorithm that computes alias information that is almost as precise as that computed by Andersen's algorithm — the most precise flow- and context-insensitive algorithm — and almost as efficient as Steensgaard's algorithm — the most efficient flow- and context-insensitive algorithm. Our empirical studies show that our algorithm scales to large programs better than Andersen's algorithm and show that flow-insensitive alias analysis algorithms, such as our algorithm and Andersen's algorithm, can compute alias information that is close in precision to that computed by the more expensive flow- and context-sensitive alias analysis algorithms.
- 1 L.O. Andersen. Program analysis and specialization for the C programming language. Technical Report 94-19, University of Copenhagen, 1994.Google Scholar
- 2 D. Atkinson and W. Griswold. Effective whole-program analysis in the presence of pointers. In Proceedings of the Sixth ACM SIGSOFT Symposium on the Foundation of Software Engineering, pages 46-55, November 1998. Google ScholarDigital Library
- 3 M. Burke, P. Carini, J. D. Choi, and M. Hind. Flow-insensitive interprocedrual alias analysis in the presence of pointers. In Language and Compilers for Parallel Computing: Proceedings of the 7th International Workshop, pages 234-250, 1994. Google ScholarDigital Library
- 4 Ramkrishna Chatterjee, Barbara G. Ryder, and William A. Landi. Relevant context inference. In Proceedings of 26th ACM SIGACT/SIGPLAN Symposium on PrincipEes of Programming Languages, January 1999. Google ScholarDigital Library
- 5 M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural pointsto analysis in the presence of function pointers. In Proceedings of SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 242-256, June 1994. Google ScholarDigital Library
- 6 Programming Languages Research Group. PROLANGS Analysis Framework. http://www.prolangs.rutgers.edu/, Rutgers University, 1998.Google Scholar
- 7 M. J. Harrold and N. Ci. Reuse-driven interprocedural slicing. In The 20th International Conference on Software Engineering, pages 74-83, April 1998. Google ScholarDigital Library
- 8 M. J. Harrold and G Rothermel. Separate computation of alias information for reuse. IEEE Transactions on Software Engineering, 22(7):107-120, June 1996. Google ScholarDigital Library
- 9 M. J. Harrold and M. L. Soffa. Efficient computation of interprocedural definition-use chains. ACM Transactions on Programming Languages and Systems, 16(2):175-204, March 1994. Google ScholarDigital Library
- 10 S. Horwitz, T. Reps, and D. Binkley. Interprocedural slicing using dependence graphs. AGM nansactions on Programming Languages and Systems, 12(1):26-60, January 1990. Google ScholarDigital Library
- 11 W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In Proceedings of 1992 ACM Symposium on Programming Language Design and Implementation, pages 235-248, June 1992. Google ScholarDigital Library
- 12 D. Liang and M. J. Harrold. Context-sensitive, procedure-specific points-to analysis. Technical Report OSU-CISRC-3/99-TR05, The Ohio State University, March 1999.Google Scholar
- 13 M. Shapiro and S. Horwitz. The effects of the precision of pointer analysis. In Static Analysis 4th International Symposium, SAS '97, Lecture Notes in Computer Science Vol 1302, pages 16-34, September 1997. Google ScholarDigital Library
- 14 M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In Conference Record of the 24th ACM Symposium on Principles of Programming Languages, pages 1-14, 1997. Google ScholarDigital Library
- 15 B. Steensgaard. Points-to analysis by type inference of programs with structures and unions. In Proc. of the Int. Conf. on Compiler Construction, pages 136-150, 1996. Google ScholarDigital Library
- 16 B. Steensgaard. Points-to analysis in almost linear time. In Conference Record of the 23rd ACM Symposium on PrincipEes of Programming Languages, pages 32-41, 1996. Google ScholarDigital Library
- 17 R. P. Wilson and M. S. Lam. Efficient context-sensitive pointer analysis for C programs. In Proceedings of SIGPLAN '95 C on erence f on Programming Language Design and Implementation, pages l-12, 1995. Google ScholarDigital Library
- 18 S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer analysis: A step toward practical analyses. In Proceedings of the Fourth ACM SIGSOFT Symposium on the Foundation of Software Engineering, pages 81-92, November 1996. Google ScholarDigital Library
Index Terms
- Efficient points-to analysis for whole-program analysis
Recommendations
Efficient points-to analysis for whole-program analysis
ESEC/FSE-7: Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineeringTo function on programs written in languages such as C that make extensive use of pointers, automated software engineering tools require safe alias information. Existing alias-analysis techniques that are sufficiently efficient for analysis on large ...
Connection Analysis: A Practical Interprocedural Heap Analysis for C
Special issue: selected papers from the eighth international workshop on languages and compilers for parallel computingThis paper presents a practical heap analysis technique, connection analysis, that can be used to disambiguate heap accesses in C programs. The technique is designed for analyzing programs that allocate many disjoint objects in the heap such as ...
Semi-sparse flow-sensitive pointer analysis
POPL '09Pointer analysis is a prerequisite for many program analyses, and the effectiveness of these analyses depends on the precision of the pointer information they receive. Two major axes of pointer analysis precision are flow-sensitivity and context-...
Comments