Fast and accurate flow-insensitive points-to analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast and accurate flow-insensitive points-to analysis

Full text

Pdf (906 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Paris, France

Pages: 1 - 14

Year of Publication: 1997

ISBN:0-89791-853-3

Authors

Marc Shapiro	Computer Sciences Department, University of Wisconsin-Madison, 1210 West Dayton Street, Madison, WI
Susan Horwitz	Computer Sciences Department, University of Wisconsin-Madison, 1210 West Dayton Street, Madison, WI

Sponsors

L'Ecole des Mines de Paris : L'Ecole des Mines de Paris
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Ctr Natl de la Recherche Sci :
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 51, Citation Count: 82

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/263699.263703 What is a DOI?

REFERENCES

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
	AHU74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	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).
	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]
	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
	Deu90	Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
	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
	GH96	Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
	Hen90	Laurie Jane Hendren, Parallelizing programs with recursive data structures, Cornell University, Ithaca, NY, 1990
	HPR89	S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.28-40, June 19-23, 1989, Portland, Oregon, United States
	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.
	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
	MCCH94	Michael G. Burke , Paul R. Carini , Jong-Deok Choi , Michael Hind, Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.234-250, August 08-10, 1994
	Ruf95	Erik Ruf, Context-insensitive alias analysis reconsidered, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.13-22, June 18-21, 1995, La Jolla, California, United States
	SRW96	Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-31, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237725]
	Ste96a	Bjarne Steensgaard, Points-to Analysis by Type Inference of Programs with Structures and Unions, Proceedings of the 6th International Conference on Compiler Construction, p.136-150, April 24-26, 1996
	Ste96b	Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
	Tar83	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	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
	ZRL96	S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer-induced aliasing analysis. Technical report, Rutgers University LCSR-TR-259, 1996.

CITED BY 82

	Andreas Krall , Sylvain Lelait, Compilation Techniques for Multimedia Processors, International Journal of Parallel Programming, v.28 n.4, p.347-361, August 2000
	Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.199-215, Nov. 1999
	Frank Tip , Chris Laffra , Peter F. Sweeney , David Streeter, Practical experience with an application extractor for Java, ACM SIGPLAN Notices, v.34 n.10, p.292-305, Oct. 1999
	Jens Palsberg, Equality-based flow analysis versus recursive types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1251-1264, Nov. 1998
	Darren C. Atkinson , William G. Griswold, Effective whole-program analysis in the presence of pointers, ACM SIGSOFT Software Engineering Notes, v.23 n.6, p.46-55, Nov. 1998
	Markus Mock , Manuvir Das , Craig Chambers , Susan J. Eggers, Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-72, June 2001, Snowbird, Utah, United States
	Patrik Persson, Live memory analysis for garbage collection in embedded systems, ACM SIGPLAN Notices, v.34 n.7, p.45-54, July 1999
	Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Program Slicing with Dynamic Points-To Sets, IEEE Transactions on Software Engineering, v.31 n.8, p.657-678, August 2005
	Atanas Rountev , Barbara G. Ryder , William Landi, Data-flow analysis of program fragments, ACM SIGSOFT Software Engineering Notes, v.24 n.6, p.235-252, Nov. 1999
	Gregor Snelting , Frank Tip, Reengineering class hierarchies using concept analysis, ACM SIGSOFT Software Engineering Notes, v.23 n.6, p.99-110, Nov. 1998
	Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, ACM SIGPLAN Notices, v.35 n.10, p.281-293, Oct. 2000
	Peng-Sheng Chen , Ming-Yu Hung , Yuan-Shin Hwang , Roy Dz-Ching Ju , Jenq Kuen Lee, Compiler support for speculative multithreading architecture with probabilistic points-to analysis, ACM SIGPLAN Notices, v.38 n.10, October 2003
	Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, ACM SIGPLAN Notices, v.33 n.5, p.106-117, May 1998
	Markus Mock , Craig Chambers , Susan J. Eggers, Calpa: a tool for automating selective dynamic compilation, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.291-302, December 2000, Monterey, California, United States
	Esther Salamí , Jesús Corbal , Carlos Álvarez , Mateo Valero, Cost effective memory disambiguation for multimedia codes, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France
	Atanas Rountev , Satish Chandra, Off-line variable substitution for scaling points-to analysis, ACM SIGPLAN Notices, v.35 n.5, p.47-56, May 2000
	Marc Berndl , Ondrej Lhoták , Feng Qian , Laurie Hendren , Navindra Umanee, Points-to analysis using BDDs, ACM SIGPLAN Notices, v.38 n.5, May 2003
	Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su , Alexander Aiken, Partial online cycle elimination in inclusion constraint graphs, ACM SIGPLAN Notices, v.33 n.5, p.85-96, May 1998
	Peter F. Sweeney , Frank Tip, A study of dead data members in C++ applications, ACM SIGPLAN Notices, v.33 n.5, p.324-332, May 1998
	Philip A. Stocks , Barbara G. Ryder , William A. Landi , Sean Zhang, Comparing flow and context sensitivity on the modification-side-effects problem, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.21-31, March 1998
	Gregor Snelting , Frank Tip, Understanding class hierarchies using concept analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.540-582, May 2000
	Suan Hsi Yong , Susan Horwitz , Thomas Reps, Pointer analysis for programs with structures and casting, ACM SIGPLAN Notices, v.34 n.5, p.91-103, May 1999
	Nurit Dor , Michael Rodeh , Mooly Sagiv, Detecting memory errors via static pointer analysis (preliminary experience), ACM SIGPLAN Notices, v.33 n.7, p.27-34, July 1998
	Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999
	Erik Ruf, Effective synchronization removal for Java, ACM SIGPLAN Notices, v.35 n.5, p.208-218, May 2000
	Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States
	Donglin Liang , Mary Jean Harrold, Equivalence analysis: a general technique to improve the efficiency of data-flow analyses in the presence of pointers, ACM SIGSOFT Software Engineering Notes, v.24 n.5, p.39-46, Sept. 1999
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001
	Manuvir Das, Unification-based pointer analysis with directional assignments, ACM SIGPLAN Notices, v.35 n.5, p.35-46, May 2000
	Sean Zhang , Barbara G. Ryder , William A. Landi, Experiments with combined analysis for pointer aliasing, ACM SIGPLAN Notices, v.33 n.7, p.11-18, July 1998
	Anasua Bhowmik , Manoj Franklin, A fast approximate interprocedural analysis for speculative multithreading compilers, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA
	Donglin Liang , Mary Jean Harrold, Equivalence analysis and its application in improving the efficiency of program slicing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.11 n.3, p.347-383, July 2002
	Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, ACM SIGPLAN Notices, v.35 n.5, p.57-69, May 2000
	Rakesh Ghiya , Laurie J. Hendren, Putting pointer analysis to work, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.121-133, January 19-21, 1998, San Diego, California, United States
	Saumya Debray , Robert Muth , Matthew Weippert, Alias analysis of executable code, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 19-21, 1998, San Diego, California, United States
	Donglin Liang , Maikel Pennings , Mary Jean Harrold, Evaluating the precision of static reference analysis using profiling, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
	Satish Chandra , Thomas Reps, Physical type checking for C, ACM SIGSOFT Software Engineering Notes, v.24 n.5, p.66-75, Sept. 1999
	Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Improving program slicing with dynamic points-to data, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to and side-effect analyses for Java, ACM SIGSOFT Software Engineering Notes, v.27 n.4, July 2002
	Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, ACM SIGPLAN Notices, v.36 n.5, p.254-263, May 2001
	Nevin Heintze , Olivier Tardieu, Demand-driven pointer analysis, ACM SIGPLAN Notices, v.36 n.5, p.24-34, May 2001
	Frank Tip , Peter F. Sweeney, Class hierarchy specialization, ACM SIGPLAN Notices, v.32 n.10, p.271-285, Oct. 1997
	Michael Hind , Anthony Pioli, Which pointer analysis should I use?, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.113-123, Sept. 2000
	John L. Ross , Mooly Sagiv, Building a bridge between pointer aliases and program dependences, Nordic Journal of Computing, v.5 n.4, p.361-386, Winter 1998
	Zhendong Su , Manuel Fähndrich , Alexander Aiken, Projection merging: reducing redundancies in inclusion constraint graphs, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-95, January 19-21, 2000, Boston, MA, USA
	Radu Rugina , Martin C. Rinard, Pointer analysis for structured parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.1, p.70-116, January 2003
	Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Improving program slicing with dynamic points-to data, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002
	Glenn Bruns , Satish Chandra, Searching for points-to analysis, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002
	Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001
	Frank Tip , Peter F. Sweeney , Chris Laffra , Aldo Eisma , David Streeter, Practical extraction techniques for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.625-666, November 2002
	John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, ACM SIGPLAN Notices, v.34 n.10, p.187-206, Oct. 1999
	Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, ACM SIGPLAN Notices, v.34 n.5, p.77-90, May 1999
	Venkatesan T. Chakaravarthy, New results on the computability and complexity of points--to analysis, ACM SIGPLAN Notices, v.38 n.1, p.115-125, January 2003
	Amie L. Souter , Lori L. Pollock, OMEN: A strategy for testing object-oriented software, ACM SIGSOFT Software Engineering Notes, v.25 n.5, p.49-59, Sept. 2000
	Glenn Bruns , Satish Chandra, Searching for points-to analysis, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
	James Ezick, An optimizing compiler for batches of temporal logic formulas, ACM SIGSOFT Software Engineering Notes, v.29 n.4, July 2004
	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural pointer aliasing, ACM SIGPLAN Notices, v.39 n.4, April 2004
	David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001
	David J. Pearce , Paul H. J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis for C, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA
	Yuan-Shin Hwang, Parallelizing graph construction operations in programs with cyclic graphs, Parallel Computing, v.28 n.9, p.1307-1328, September 2002
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to analysis for Java, ACM Transactions on Software Engineering and Methodology (TOSEM), v.14 n.1, p.1-41, January 2005
	Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Complexity of Points-To Analysis of Java in the Presence of Exceptions, IEEE Transactions on Software Engineering, v.27 n.6, p.481-512, June 2001
	Francisco Corbera , Rafael Asenjo , Emilio L. Zapata, A Framework to Capture Dynamic Data Structures in Pointer-Based Codes, IEEE Transactions on Parallel and Distributed Systems, v.15 n.2, p.151-166, February 2004
	Esther Salamí , Mateo Valero, Dynamic memory interval test vs. interprocedural pointer analysis in multimedia applications, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.199-219, June 2005
	Baowen Xu , Ju Qian , Xiaofang Zhang , Zhongqiang Wu , Lin Chen, A brief survey of program slicing, ACM SIGSOFT Software Engineering Notes, v.30 n.2, March 2005
	Peng-Sheng Chen , Yuan-Shin Hwang , Roy Dz-Ching Ju , Jenq Kuen Lee, Interprocedural Probabilistic Pointer Analysis, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.893-907, October 2004
	Nevin Heintze, Aliasing analysis for a million lines of C, Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, p.47-49, September 12-14, 2002, Aizu, Japan
	Ana Milanova , Atanas Rountev , Barbara G. Ryder, Precise Call Graphs for C Programs with Function Pointers, Automated Software Engineering, v.11 n.1, p.7-26, January 2004
	Rebecca Hasti , Susan Horwitz, Using static single assignment form to improve flow-insensitive pointer analysis, ACM SIGPLAN Notices, v.33 n.5, p.97-105, May 1998
	Greta Yorsh , Thomas Reps , Mooly Sagiv , Reinhard Wilhelm, Logical characterizations of heap abstractions, ACM Transactions on Computational Logic (TOCL), v.8 n.1, p.5-es, January 2007
	V. Krishna Nandivada , Suresh Jagannathan, Dynamic state restoration using versioning exceptions, Higher-Order and Symbolic Computation, v.19 n.1, p.101-124, March 2006
	Angeles Navarro , Francisco Corbera , Adrian Tineo , Rafael Asenjo , Emilio L. Zapata, Detecting loop-carried dependences in programs with dynamic data structures, Journal of Parallel and Distributed Computing, v.67 n.1, p.47-62, January, 2007
	David Binkley , Nicolas Gold , Mark Harman, An empirical study of static program slice size, ACM Transactions on Software Engineering and Methodology (TOSEM), v.16 n.2, p.8-es, April 2007
	Yuan-Shin Hwang_cor , Joel Saltz, Interprocedural definition-use chains of dynamic pointer-linked data structures, Scientific Programming, v.11 n.1, p.3-37, January 2003
	Sean Foley, Tactics for minimal interference from class loading in real-time Java™, Proceedings of the 5th international workshop on Java technologies for real-time and embedded systems, September 26-28, 2007, Vienna, Austria
	David J. Pearce , Paul H. J. Kelly , Chris Hankin, Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis, Software Quality Control, v.12 n.4, p.311-337, December 2004
	Ákos Kiss , Judit Jász , Tibor Gyimóthy, Using Dynamic Information in the Interprocedural Static Slicing of Binary Executables, Software Quality Control, v.13 n.3, p.227-245, September 2005
	Marcio Buss , Daniel Brand , Vugranam Sreedhar , Stephen A. Edwards, Flexible pointer analysis using assign-fetch graphs, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	David J. Pearce , Paul H.J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis of C, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.4-es, November 2007
	Ondřej Lhoták , Laurie Hendren, Relations as an abstraction for BDD-based program analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.4, p.1-63, July 2008
	Mariana Sharp , Atanas Rountev, Static Analysis of Object References in RMI-Based Java Software, IEEE Transactions on Software Engineering, v.32 n.9, p.664-681, September 2006