Erik Ruf
ABSTRACT
Recent 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 effect on all of its callers. While context-sensitive modeling offers the potential for greater precision by considering only realizable call-return paths, its empirical benefits have yet to be measured.
This paper compares the precision of a simple, efficient, context-insensitive points-to analysis for the C programming language with that of a maximally context-sensitive version of the same analysis. We demonstrate that, for a number of pointer-intensive benchmark programs, context-insensitivity exerts little to no precision penalty. We also describe techniques for using the output of context-insensitive analysis to improve the efficiency of context-sensitive analysis without affecting precision.
- ABS94.T. M Austin, S. E. Breach, and G. S. Sohi. Effiment detection of all pointer and array access errors. In Proceedings of the SIGPLAN '9~ Conference on Programming Language Design and Implementation, pages 290-301. ACM Press, 1994. Google Scholar
Digital Library
- CBC93.J-D Choi, M. Burke, and P. Carini. Efficient flowsenmtive mterprocedural computation of pointerinduced aliases and side effects. In Proceedings of the Twentieth Annual A CM SIGPLAN-SICACT Symposium on Principles of Programming Languages, pages 232-245 ACM Press, Jan. 1993. Google ScholarDigital Library
- CFR+91.R. Cytron, J Perrante, 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, t3(4) 451-490, Oct 1991 Google ScholarDigital Library
- Coo89.B.G. Cooper. Ambitious data flow analysm of procedural programs. Master's thesm, Umversity of Minnesota, May 1989.Google Scholar
- Cou86.D S. Coutant Retargetable hlgh-level alias analysis. In Proceed~ng~ of the Thirteenth Annual ACM Sympossum on Princtples of Programming Languages, pages 110-118. ACM Press, 1986. Google Scholar
- CR82.A.L. Chow and A Rudmlk The demgn of a data flow analyzer. In Proceedings of ~he SICPLAN '32 Symposium on Compiler Construction, pages 106- 119. ACM Press, 1982. Google ScholarDigital Library
- CWZ90.D. R Chase, M. Wegman, and F. K. Zadeck. Analysis of pointers and structures In Proceedings of the $IGPLAN '90 Conference on Programming Language Design and Implementation, pages 296-310, June 20-22, 1990 Google ScholarDigital Library
- Deu92.A. Deutsch. A storeless model of aliasing and its abstractions using fimte representations of rightregular equivalence relations. In International Conference on Computer Languages, pages 2-13 IEEE, Apr. 1992.Google Scholar
- Deu94.A. Deutsch. Interprocedural may-alias analysis for pmnters. Beyond k-limiting. In Proceedings of the SIGPLAN '9~ Conference on Programming Language Design and Implementation, pages 230-239. ACM Press, 1994. Google ScholarDigital Library
- EGH94.M Emami, R Ghiya, and L J Hendren Contextsensitive interprocedural analysis in the presence of function pmnters. In Proceedings of the SIGPLAN '9~ Conference on Programming Language Des,gn and Implementation, pages 242-256. ACM Press, June 1994 Google ScholarDigital Library
- Har89.W. L Harrison IIt. The interprocedural analysis and automatic parallelization of Scheme programs Lisp and Symbolic Computation, 2(3/4).179-396, 1989.Google Scholar
- HPR89.S. Horwitz, P. Pfmffer, and T. Reps. Dependence analysis for pointer variables. In Proceedings of the SIGPLAN'89 Symposium on Compiler Con~truction~ pages 28-40. June 1989 Published as SIC- PLAN Notices Vol 24, Num. 7. Google ScholarDigital Library
- Lan92.W. A Landi fnterprocedural Aliasmg in the Presence of Pointers PhD thesis, Rutgers University, Jan 1992 Google ScholarDigital Library
- LR92.W. Lan& and B. G. Ryder A safe approxlmate algorithm for mterprocedural pointer aliaslng In Procced~r~gs of the SICPLAN '92 Conference on Programm~ng Language Design and Implementation, pages 235-248 ACM Press, June 1992 Google ScholarDigital Library
- LRZ93.W Landi, B G Ryder, and S Zhang Interprocedural modification side effect analysis with pointer aliasing. In Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, pages 56-67 ACM Press, June 1993 Google ScholarDigital Library
- PLR92.H.D. Pande, W Lan&, and B. G. Ryder. Interprocedural reaching definitions m the presence of single level pointers. Techmcal Report lcsr-tr-193, Laboratory for Computer Smence Research, Rutgers Umversity, Oct 1992.Google Scholar
- RM88.C. Ruggmrl and T P. Murtagh. Lffetmae analyms of dynammally allocated objects. In Proceedings of the Fifteenth Annual A CM Symposium on Pmnc~ples of Programmzng Languages, pages 285-293, Jan. 1988. Google ScholarDigital Library
- Ruf95.E. Ruf Optimizing sparse representations for datafiow analysis. In A CM SIGPLAN Workshop on Intermediate t~epresen~a~lon5 (11~'95), pages 50-61, Jan 1995 Proceedings available as Microsoft Research technical report MSR-TR-95-01 Google ScholarDigital Library
- Ryd89.B.G. Ryder Isnam Incremental soRware maintenance manager. In Proceedings of the It~EE Computer Society Conference on Software Maintenance, pages 142-164, 1989.Google Scholar
- WCES94a.D. Weise, R. F Crew, M Ernst, and B. Steensgaard. Value dependence graphs: Representation without taxation In Proceedings 21st ACM SIGPLAN- SIGACT Symposzum on PrmcJples of Programming Languages, pages 297-310, Jan 1994 Google ScholarDigital Library
- WCES94b.D. Weise, R F. Crew, M. Ernst, and B. Steensgaard Value dependence graphs: t~epresentatmn without taxation. Techmcal Report MSR-TR~94-03, Microsoft Research, Redmond, WA, Apr. 13, 1994.Google Scholar
- Wei80.W.E. Wmhl. Interprocedurat data flow anatysls in the presence of pointers, procedure variables, and label vanables In Proceedings of the Seventh Annual A CM Symposz~m on Pr,nczples of Programruing Languages, pages 83-94, Jan 1980. Google ScholarDigital Library
- WL95.R P Wilson and M S Lain. Efficient contextsensitive pointer analysis for C programs In Proceedrags of the SIGPLAN '95 Conference on Programm~ng Language Design and Implementation ACM Press, June 1995 (this volume) Google ScholarDigital Library
Index Terms
- Context-insensitive alias analysis reconsidered
Recommendations
Context-insensitive alias analysis reconsidered
Recent 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 ...
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. ...
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 ...
Comments