Marc Shapiro
ABSTRACT
In order to analyze a program that involves pointers, it is necessary to have (safe) information about what each pointer points to. There are many different approaches to computing points-to information. This paper addresses techniques for flow- and context-insensitive interprocedural analysis of stack-based storage.The paper makes two contributions to work in this area: - The first contribution is a set of experiments that explore the trade-offs between techniques previously defined by Lars Andersen and Bjarne Steensgaard. The former has a cubic worst-case running time, while the latter is essentially linear. However, the former may be much more precise than the latter. We have found that in practice, Andersen's algorithm is consistently more precise than Steensgaard's. For small programs, there is very little difference in the times required by the two approaches; however, for larger programs, Andersen's algorithm can be much slower than Steensgaard's. - The second contribution is the definition of two new algorithms. The first algorithm can be "tuned" so that its worst-case time and space requirements, as well as its accuracy range from those of Steensgaard to those of Andersen. We have experimented with several versions of this algorithm; one version provided a significant increase in accuracy over Steensgaard's algorithm, while keeping the running time within a factor of two. The second algorithm uses the first as a subroutine. Its worst-case time and space requirements are a factor of log N (where N is the number of variables in the program) worse than those of Steensgaard's algorithm. In practice, it appears to run about ten times slower than Steensgaard's algorithm; however it is significantly more accurate than Steensgaard's algorithm, and significantly faster than Andersen's algorithm on large programs.
- ABS94.T. Austin, S. Breach, and G. Sohi. Efficient detection of all pointer and array access errors. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 290-301, June 1994. Google Scholar
Digital Library
- AHU74.A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison- Wesley, 1974. Google ScholarDigital Library
- And94.L.O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994. (DIKU report 94/19).Google Scholar
- CBC93.J.-D. Choi, M. Burke, and P. Carini. Efficient flowsensitive interprocedural computation of pointerinduced aliases and side-effects. In A CM Symposium on Principles of Programming Languages, pages 232- 245, 1993. Google ScholarDigital Library
- CWZ90.D.R. Chase, M. Wegman, and F. Zadeck. Analysis of pointers and structures. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 296-310, 1990. Google ScholarDigital Library
- Deu90.A. Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications. In A CM Symposium on Principles of Programming Languages, pages 157-168, January 1990. Google ScholarDigital Library
- Deu94.A. Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In SIGPLAN Conference on Programming Languages Design and Implementation,, pages 230-241, 1994. Google ScholarDigital Library
- EGH94.M. Emami, R. Ghiya, and L. Hendren. Contextsensitive interprocedural points-to analysis in the presence of function pointers. In SIGPLAN Conference on Programming Languages Design and Implementation, 1994. Google ScholarDigital Library
- GH96.R. Ghiya and L.J. Hendren. Is it a tree, a dag, or a cyclic graph? A shape analysis for heap-directed pointers in C. In A CM Symposium on Principles of Programming Languages. ACM, New York, January 1996. Google ScholarDigital Library
- Hen90.L. Hendren. Parallelizing Programs with Recursive Data Structures. PhD thesis, Cornell University, Jan 1990. Google ScholarDigital Library
- HPR89.S. Horwitz, P. Pfeiffer, and T. Reps. Dependence analysis for pointer variables. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 28-40, 1989. Google ScholarDigital Library
- JM81.N.D. Jones and S.S. Muchnick. Flow analysis and optimization of Lisp-like structures. In S.S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 4, pages 102-131. Prentice-Hall, 1981.Google Scholar
- LR92.W. Landi and B. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In SIC- PLAN Conference on Programming Languages Design and Implementation, pages 235-248, June 1992. Google ScholarDigital Library
- LRZ93.W. Landi, B. Ryder, and S. Zhang. Interprocedural modification side effect analysis with pointer aliasing. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 56-67, June 1993. Google ScholarDigital Library
- MCCH94.M.Burke, P. Carini, J.D. Choi, and M. Hind. Flowinsensitive interprocedural alias analysis in the presence of pointers. In K. Pingali, U. Banerjee, D. Galernter, A. Nicolau, and D. Padua, editors, Languages and Compilers for Parallel Computing: Proceedings of the 7th International Workshop, volume 892 of Lecture Notes in Computer Science, pages 234-250, ithaca, NY, August 1994. Springer-Verlag. Google ScholarDigital Library
- Ruf95.E. Rut. Context-sensitive alias analysis reconsidered. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 13-22, June 1995. Google ScholarDigital Library
- SRW96.M. Sagiv, T. Reps, and R. Wilhelm. Solving shapeanalysis problems in languages with destructive updating. In A CM Symposium on Principles of Programming Languages. ACM, New York, January 1996. Google ScholarDigital Library
- Ste96a.B. Steensgaard. Points-to analysis by type inference of programs with structures and unions. In International Conference on Compiler Construction, April 1996. Google ScholarDigital Library
- Ste96b.B. Steensgaard. Points-to analysis in almost linear time. In A CM Symposium on Principles of Programming Languages, pages 32-41, January 1996. Google ScholarDigital Library
- Tar83.R. Tarjan. Data structures and network flow algorithms, volume CMBS44 of Regional Conference Series in Applied Mathematics. SIAM, 1983. Google ScholarDigital Library
- Wei80.W.E. Weihl. Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables. In A CM Symposium on Principles of Programming Languages, pages 83-94, 1980. Google ScholarDigital Library
- WL95.R. Wilson and M. Lam. Efficient context-sensitive pointer analysis for C programs. In SIGPLAN Conference on Programming Language Design and Implementation, pages 1-12, June 1995. Google ScholarDigital Library
- ZRL96.S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer-induced aliasing analysis. Technical report, Rutgers University LCSR-TR-259, 1996.Google Scholar
Index Terms
- Fast and accurate flow-insensitive points-to analysis
Recommendations
Precise flow-insensitive may-alias analysis is NP-hard
Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. ...
Fast and precise points-to analysis
Many software engineering applications require points-to analysis. These client applications range from optimizing compilers to integrated program development environments (IDEs) and from testing environments to reverse-engineering tools. Moreover, ...
Context-insensitive alias analysis reconsidered
PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementationRecent work on alias analysis in the presence of pointers has concentrated on context-sensitive interprocedural analyses, which treat multiple calls to a single procedure independently rather than constructing a single approximation to a procedure's ...
Comments