Solving shape-analysis problems in languages with destructive updating

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving shape-analysis problems in languages with destructive updating

Full text

Pdf (1.77 MB)

Source

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

St. Petersburg Beach, Florida, United States

Pages: 16 - 31

Year of Publication: 1996

ISBN:0-89791-769-3

Authors

Mooly Sagiv	Computer Science Department, 1210 West Dayton Street, Madison, WI and IBM Israel Scientific Center
Thomas Reps	Computer Science Department, 1210 West Dayton Street, Madison, WI
Reinhard Wilhelm	Fachbereich 14 Informatik, 66123 Saarbrücken, Germany

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 40, Citation Count: 33

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/237721.237725 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.

	AW93	U. Assmann and M. Weinhardt. Interprocedural Heap Analysis For Parallelizing Imperative Programs. In W. K. Giloi, S. Jghnichen, and B. D Shriver, editors, Programming Models For Massively Parallel Computers, pages 74-82. IEEE Press, September 1993.
	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
	Deu92	A. Deutsch. A storeless model for aliasing and its abstractions using finite representations of right-regular equivalence relations. In IEEE International Conference on Computer Languages, pages 2-13, 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
	Hen90	Laurie Jane Hendren, Parallelizing programs with recursive data structures, Cornell University, Ithaca, NY, 1990
	HG92	L. Hendren and G.R. Gao. Designing programming languages for analyzability: A fresh look at pointer data structures. In Proceedings of the International Conference on Computer Languages, pages 242-251, 1992.
	HN90	L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990 [doi>10.1109/71.80123]
	HNH92	Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.249-260, June 15-19, 1992, San Francisco, California, United States
	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.
	JM82	Neil D. Jones , Steven S. Muchnick, A flexible approach to interprocedural data flow analysis and programs with recursive data structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.66-74, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582161]
	Lan92	William Landi, Undecidability of static analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.323-337, Dec. 1992 [doi>10.1145/161494.161501]
	Lar89	James Richard Larus , Paul Hifinger, Restructuring symbolic programs for concurrent execution on multiprocessors, 1989
	LH88	J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
	LR91	William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
	Mye81	Eugene M. Myers, A precise inter-procedural data flow algorithm, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.219-230, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567556]
	PCK93	John Plevyak , Andrew A. Chien , Vijay Karamcheti, Analysis of Dynamic Structures for Efficient Parallel Execution, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.37-56, August 12-14, 1993
	Ram94	G. Ramalingam, The undecidability of aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1467-1471, Sept. 1994 [doi>10.1145/186025.186041]
	Rey68	J.C. Reynolds. Automatic computation of data set definitions. In Informatwn Processing 68: Proceedings of the IFIP Congress, pages 456-461, New York, NY, 1968. North-Holland.
	SP81	M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In S.S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 7, pages 189-234. Prentice-Hall, 1981.
	SRW95	M. Sagiv, T. P#eps, and R. Wilhelm. Solving shapeanalysis problems in languages with destructive updating. Technical Report TR-1276, Computer Sciences Department, University of Wisconsin, Madison, WI, July 1995. Available on the WWW from URL http: //www. cs. wisc. edu / t rs. ht ml.
	Str92	Jan Stransky, A lattice for abstract interpretation of dynamic (LISP-like) structures, Information and Computation, v.101 n.1, p.70-102, Nov. 1992 [doi>10.1016/0890-5401(92)90076-R]

CITED BY 33

	Patrik Persson, Live memory analysis for garbage collection in embedded systems, ACM SIGPLAN Notices, v.34 n.7, p.45-54, July 1999
	Sean Zhang , Barbara G. Ryder , William Landi, Program decomposition for pointer aliasing: a step toward practical analyses, ACM SIGSOFT Software Engineering Notes, v.21 n.6, p.81-92, Nov. 1996
	Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France
	Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, ACM SIGPLAN Notices, v.34 n.10, p.35-46, Oct. 1999
	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
	Yuan-Shin Hwang , Joel H. Saltz, Identifying parallelism in programs with cyclic graphs, Journal of Parallel and Distributed Computing, v.63 n.3, p.337-355, March 2003
	Pascal Fradet , Daniel Le Métayer, Shape types, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.27-39, January 15-17, 1997, Paris, France
	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
	Peng Wu , Paul Feautrier , David Padua , Zehra Sura, Instance-wise points-to analysis for loop-based dependence testing, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
	Berhard Scholz , Johann Blieberger , Thomas Fahringer, Symbolic pointer analysis for detecting memory leaks, ACM SIGPLAN Notices, v.34 n.11, p.104-113, Nov. 1999
	Christopher Colby , Patrice Godefroid , Lalita Jategaonkar Jagadeesan, Automatically closing open reactive programs, ACM SIGPLAN Notices, v.33 n.5, p.345-357, May 1998
	Viktor Kuncak , Patrick Lam , Martin Rinard, Role analysis, ACM SIGPLAN Notices, v.37 n.1, p.17-32, Jan. 2002
	Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Parametric shape analysis via 3-valued logic, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-118, January 20-22, 1999, San Antonio, Texas, United States
	John Lu , Keith D. Cooper, Register promotion in C programs, ACM SIGPLAN Notices, v.32 n.5, p.308-319, May 1997
	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
	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
	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
	Fausto Spoto , Thomas Jensen, Class analyses as abstract interpretations of trace semantics, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.5, p.578-630, September 2003
	Beatrix Braune , Reinhard Wilhelm, Focusing in Algorithm Explanation, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.1-7, January 2000
	Steven Dawson , C. R. Ramakrishnan , David S. Warren, Practical program analysis using general purpose logic programming systems—a case study, ACM SIGPLAN Notices, v.31 n.5, p.117-126, May 1996
	Jakob L. Jensen , Michael E. Jørgensen , Michael I. Schwartzbach , Nils Klarlund, Automatic verification of pointer programs using monadic second-order logic, ACM SIGPLAN Notices, v.32 n.5, p.226-234, May 1997
	Easwaran Raman , David I. August, Recursive data structure profiling, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois
	David Chase , Mark Wegman , F. Ken Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Yuan-Shin Hwang, Parallelizing graph construction operations in programs with cyclic graphs, Parallel Computing, v.28 n.9, p.1307-1328, September 2002
	Douglas Gregor , Sibylle Schupp, STLlint: lifting static checking from languages to libraries, Software—Practice & Experience, v.36 n.3, p.225-254, March 2006
	Mark Marron , Darko Stefanovic , Manuel Hermenegildo , Deepak Kapur, Heap analysis in the presence of collection libraries, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.31-36, June 13-14, 2007, San Diego, California, USA
	Milind Kulkarni , Keshav Pingali , Bruce Walter , Ganesh Ramanarayanan , Kavita Bala , L. Paul Chew, Optimistic parallelism requires abstractions, ACM SIGPLAN Notices, v.42 n.6, June 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
	Sandrine Blazy, Specifying and Automatically Generating a Specialization Tool for Fortran 90, Automated Software Engineering, v.7 n.4, p.345-376, December 2000
	Bolei Guo , Matthew J. Bridges , Spyridon Triantafyllis , Guilherme Ottoni , Easwaran Raman , David I. August, Practical and Accurate Low-Level Pointer Analysis, Proceedings of the international symposium on Code generation and optimization, p.291-302, March 20-23, 2005
	Xiaodong Ma , Ji Wang , Wei Dong, Shape Analysis by Refining on Abstract Evaluation Path, Electronic Notes in Theoretical Computer Science (ENTCS), 207, p.137-151, April, 2008
	Sascha A. Parduhn , Raimund Seidel , Reinhard Wilhelm, Algorithm visualization using concrete and abstract shape graphs, Proceedings of the 4th ACM symposium on Software visuallization, September 16-17, 2008, Ammersee, Germany
	Bassem Elkarablieh , Patrice Godefroid , Michael Y. Levin, Precise pointer reasoning for dynamic test generation, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA