Abstract
Type casting allows a program to access an object as if it had a type different from its declared type. This complicates the design of a pointer-analysis algorithm that treats structure fields as separate objects; therefore, some previous pointer-analysis algorithms "collapse" a structure into a single variable. The disadvantage of this approach is that it can lead to very imprecise points-to information. Other algorithms treat each field as a separate object based on its offset and size. While this approach leads to more precise results, the results are not portable because the memory layout of structures is implementation dependent.This paper first describes the complications introduced by type casting, then presents a tunable pointer-analysis framework for handling structures in the presence of casting. Different instances of this framework produce algorithms with different levels of precision, portability, and efficiency. Experimental results from running our implementations of four instances of this framework show that (i) it is important to distinguish fields of structures in pointer analysis, but (ii) making conservative approximations when casting is involved usually does not cost much in terms of time, space, or the precision of the results.
- ABS94 T. Austin, S. Breach, and G. Sohi. Efficient detection of all pointer and array access errors. In A CM SIGPLAN '9~ Conference on Programming Language Design and Implementation, pages 290-301, June 1994. Google ScholarDigital Library
- And94 L.O. Andersen. Program Analysis and Specialization for the C Programming Language. P hD thesis, DiKU, University of Copenhagen, May 1994. (DIKU report 94/19).Google Scholar
- BCCH94 M. Burke, P. Carini, J.-D. Choi, and M. Hind. Flow-insensitive interprocedural alias analysis in the presence of pointers. In K. Pingali, U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Language and Compilers for Parallel Computing, 7th International Workshop, LNCS 892, pages 234-250. Springer- Verlag, August 1994. Google ScholarDigital Library
- CBC93 J. Choi, M. Burke, and P. Carini. Efficient flow-sensitive interporcedural computation of pointer-induced aliases and side effects. In A CM Symposium on Principles of Programming Languages, pages 232-245, January 1993. Google ScholarDigital Library
- EGH94 M. Emami, R. Ghiya, and L. Hendren. Contextsensitive interprocedural points-to analysis in the presence of function pointers. In A CM SIG- PLAN '9~ Conference on Programming Language Design and Implementation, pages 242- 256, June 1994. Google ScholarDigital Library
- ISO90 ISO/IEC. International Standard ISO/IEC 9899, Programming Languages- C. 1st Ed. 1990.Google Scholar
- LRZ93 W. Landi, B. Ryder, and S. Zhang. Interprocedural modification side effect analysis with pointer aliasing. In A CM SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 56-67, June 1993. Google ScholarDigital Library
- Ruf95 E. Ruf. Context-insensitive alias analysis reconsidered. In A CM SIGPLAN '95 Conference on Programming Language Design and implementation, pages 13-22, June 1995. Google ScholarDigital Library
- Ryd98 B. Ryder. personal communication, September 1998.Google Scholar
- SH97a M. Shapiro and S. Horwitz. The effects of the precision of pointer analysis. In ~th International Symposium on Static Analysis, LNCS 1302. Springer-Verlag, September 1997. Google ScholarDigital Library
- SH97b M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In A CM Symposium on Principles of Programming Languages, January 1997. Google ScholarDigital Library
- SRLZ98 P. Stocks, B. Ryder, W. Landi, and S. Zhang. Comparing flow and context sensitivity on the modification-side-effects problem. In International Symposium on Software Testing and Analysis, pages 21-31, March 1998. 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 o/ Programming Languages, pages 32-41, January 1996. Google ScholarDigital Library
- Ton97 P. Tonella. Points-to analysis for program understanding. In Proceedings of the International Workshop on Program Comprehension, May 1997. Google ScholarDigital Library
- WFW+94 R. Wilson, R. French, C. Wilson, S. Amarasinghe, J. Anderson, S. Tjiang, S. Liao, C. Tseng, M. Hall, M. Lain, and J. Hennessy. SUIF: An infrastructure for research on parallelizing and optimizing compilers. In A CM SIGPLAN Notices, volume 29(12), pages 31- 37, December 1994. Google ScholarDigital Library
- WL95 R. Wilson and M. Lain. Efficient contextsensitive pointer analysis for C programs. In A CM SIGPLAN '95 Conference on Programming Language Design and Implementation, pages 1-12, June 1995. Google ScholarDigital Library
Index Terms
- Pointer analysis for programs with structures and casting
Recommendations
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Pointer analysis for programs with structures and casting
PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementationType casting allows a program to access an object as if it had a type different from its declared type. This complicates the design of a pointer-analysis algorithm that treats structure fields as separate objects; therefore, some previous pointer-...
Comments