Rebecca Hasti
Abstract
A pointer-analysis algorithm can be either flow-sensitive or flow-insensitive. While flow-sensitive analysis usually provides more precise information, it is also usually considerably more costly in terms of time and space. The main contribution of this paper is the presentation of another option in the form of an algorithm that can be 'tuned' to provide a range of results that fall between the results of flow-insensitive and flow-sensitive analysis. The algorithm combines a flow-insensitive pointer analysis with static single assignment (SSA) form and uses an iterative process to obtain progressively better results.
- 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
- 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. 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
- CC95 C. Click and K.D. Cooper. Combining analyses, combining optimizations. A CM Transactions on Programming Languages and Systems, 17(2):181-196, 1995. Google ScholarDigital Library
- CFR+91 R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. A CM Transactions on Programming Languages and Systems, 13(4):451- 490, October 1991. Google ScholarDigital Library
- CG93 R. Cytron and R. Gershbein. Efficient accommodation of may-alias information in SSA form. SIGPLAN Conference on Programming Language Design and Implementation, 28(6):36- 45, June 1993. Google ScholarDigital Library
- Hor97 S. Horwitz. Precise flow-insensitive may-alias analysis is NP-hard. A CM Transactions on Programming Languages and Systems, 19(1):1-6, January 1997. Google ScholarDigital Library
- HP97 M. Hind and A. Pioli. An empirical comparison of interprocedural pointer alias analyses. IBM Research Report RC 21058, IBM Research Division, December 1997.Google Scholar
- Kil73 G.A. Kildall. A unified approach to global program optimization. In A CM Symposium on Principles of Programming Languages, pages 194-206, January 1973. Google ScholarDigital Library
- LH96 C. Lapkowski and L.J. Hendren. Extended SSA numbering: Introducing SSA properties to languages with multi-level pointers. ACAPS Technical Memo 102, School of Computer Science, McGill University, Montreal, Canada, April 1996.Google Scholar
- LR91 W. Landi and B.G. Ryder. Pointer induced aliasing: A problem classification. In ACM Symposium on Principles of Programming Languages, pages 93-103, 1991. Google ScholarDigital Library
- Mye81 E.W. Myers. A precise inter-procedural data flow algorithm. In A CM Symposium on Principles of Programming Languages, pages 219-230, 1981. Google ScholarDigital Library
- SG95 V.C. Sreedhar and G.R. Gao. A linear time algorithm for placing ~nodes. In ACM Symposium on Principles of Programming Languages, pages 62-73, 1995. Google ScholarDigital Library
- SH97 M. Shapiro and S. Horwitz. Fast and accurate flow-insensitive points-to analysis. In A CM Symposium on Principles of Programming Languages, pages 1-14, january 1997. Google ScholarDigital Library
- Ste96 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
Index Terms
- Using static single assignment form to improve flow-insensitive pointer analysis
Recommendations
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-...
Demand-driven pointer analysis
Known algorithms for pointer analysis are “global” in the sense that they perform an exhaustive analysis of a program or program component. In this paper we introduce a demand-driven approach for pointer analysis. Specifically, we describe a demand-...
Using static single assignment form to improve flow-insensitive pointer analysis
PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementationA pointer-analysis algorithm can be either flow-sensitive or flow-insensitive. While flow-sensitive analysis usually provides more precise information, it is also usually considerably more costly in terms of time and space. The main contribution of this ...
Comments