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.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ABS94	Todd M. Austin , Scott E. Breach , Gurindar S. Sohi, Efficient detection of all pointer and array access errors, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.290-301, June 20-24, 1994, Orlando, Florida, United States
	CBC93	Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States  [doi>10.1145/158511.158639]
	CFR+91	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991  [doi>10.1145/115372.115320]
	Coo89	B.G. Cooper. Ambitious data flow analysm of procedural programs. Master's thesm, Umversity of Minnesota, May 1989.
	Cou86	Deborah S. Coutant, Retargetable high-level alias analysis, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-118, January 01, 1986, St. Petersburg Beach, Florida  [doi>10.1145/512644.512654]
	CR82	Anita L. Chow , Andres Rudmik, The design of a data flow analyzer, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.106-113, June 23-25, 1982, Boston, Massachusetts, United States
	CWZ90	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
	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.
	Deu94	Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.230-241, June 20-24, 1994, Orlando, Florida, United States
	EGH94	Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
	Har89	W. L Harrison IIt. The interprocedural analysis and automatic parallelization of Scheme programs Lisp and Symbolic Computation, 2(3/4).179-396, 1989.
	HPR89	S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
	Lan92	William Alexander Landi, Interprocedural aliasing in the presence of pointers, Rutgers University, New Brunswick, NJ, 1992
	LR92	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
	LRZ93	William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.56-67, June 21-25, 1993, Albuquerque, New Mexico, United States
	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.
	RM88	C. Ruggieri , T. P. Murtagh, Lifetime analysis of dynamically allocated objects, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.285-293, January 10-13, 1988, San Diego, California, United States  [doi>10.1145/73560.73585]
	Ruf95	Erik Ruf, Optimizing sparse representations for dataflow analysis, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.50-61, January 23-25, 1995, San Francisco, California, United States
	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.
	WCES94a	Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States  [doi>10.1145/174675.177907]
	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.
	Wei80	William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada  [doi>10.1145/567446.567455]
	WL95	Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  

• ACM SIGPLAN Notices
  Volume 30 ,  Issue 6   June 1995