Article

Free access

Solving shape-analysis problems in languages with destructive updating

Authors:

Reinhard WilhelmAuthors Info & Claims

POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 16 - 31

https://doi.org/10.1145/237721.237725

Published: 01 January 1996 Publication History

Abstract

This paper concerns the static analysis of programs that perform destructive updating on heap-allocated storage. We give an algorithm that conservatively solves this problem by using a finite shape-graph to approximate the possible "shapes" that heap-allocated structures in a program can take on. In contrast with previous work, our method is even accurate for certain programs that update cyclic data structures. For example, our method can determine that when the input to a program that searches a list and splices in a new element is a possibly circular list, the output is a possibly circular list.

References

[1]

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.

[2]

J.-D. Choi, M. Burke, and P. Carim. E#cient flow-sensitive interprocedural computation of pointerinduced aliases and side-effects. In ACM Symposium on Principles of Programmzn9 Languages, pages 232- 245, 1993.

Digital Library

[3]

D.P#. Chase, M. Wegman, and F. Zadeck. AnaIysis of pointers and structures. In SIGPLAN Conference on Programming Languages Design and Implementation, 1990.

Digital Library

[4]

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.

[5]

A. Deutsch. Interprocedural may-alias analysis for pointers: Beyond k-limiting. In SIGPLAN Conference on Programming Languages Design and Implementation, 1994.

Digital Library

[6]

L. Hendren. Parallelizing Programs with Recursivc Data Structures. PhD thesis, Cornell University, Jan 1990.

Digital Library

[7]

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.

[8]

L. Hendren and A. Nicolau. ParaIielizing programs with recursive data structures. IEEE Transactions on Parallel and D#stributed Systems, 1(1):35-47, January 1990.

Digital Library

[9]

L. Hendren, A. Nicotau, and J. Hummel. Abstractions for recursive pointer data structures: Improving the analysis and the transformation of imperative programs. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 249-260, June 1992.

Digital Library

[10]

S. Horwitz, P. Pfeiffer, and T. Reps. Dependence analysis for pointer variables. In SIGPLAN Conference on Programming Languages Design and Implementation, pages 28-40, 1989.

Digital Library

[11]

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.

[12]

N.D. Jones and S.S. Muchnick. A flexible approach to interprocedural data flow analysis and programs with recursive data structures. In A CM Symposium. on Principles of Programmzng Languages, pages 66-74, 1982.

Digital Library

[13]

W. Landi. Undecidability of static analysis. ACM Letters on Program'rning Languages and Systems, 1(4), 1992.

Digital Library

[14]

J.R. Larus. Restructuring Symbolic Programs for Concurrent Execution on Multiprocessors. PhD thesis, UnL versity of California, 1989.

Digital Library

[15]

J.R. Larus and P.N. Hilfinger. Detecting conflicts between structure accesses. In SIGPLAN Conference on Programming Languages Deszgn and Implementation, pages 21-34, 1988.

Digital Library

[16]

W. Landi and B.G. Ryder. Pointer induced aliasing: A problem classification. In A CM Symposium on Pranceples of Programming Languages, pages 93-103, 1991.

Digital Library

[17]

E.W. Myers. A precise inter-procedural data flow algorithm. In A CM Symposzum on Princwles of Programruing Languages, pages 219-230, 1981.

Digital Library

[18]

J. Plevyak, A.A. Chien, and V. Karamcheti. Analysis of dynamic structures for efficient parallel execution. In U. Banerjee, D. Gelernter, A. Nicolau, and D. Padua, editors, Languages and Compzlers for Parallel Computi#tg, volume 768 of Lecture Notes in Computer Science, pages 37-57, Portland, OR, August 1993. Springer-Verlag.

Digital Library

[19]

G. Ramalingam. The undecidability of aliasing. ACM Transactions on Programming Languages and Systems, 16(5):1467-1471, 1994.

Digital Library

[20]

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.

[21]

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.

[22]

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.

[23]

J. Stransky. A lattice for abstract interpretation of dynamic (Lisp:like) #tructures. Information and Computation, 101(1):70-1:}2, November 1992.

Digital Library

Cited By

Hainry EPéchoux R(2023)A General Noninterference Policy for Polynomial TimeProceedings of the ACM on Programming Languages10.1145/35712217:POPL(806-832)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571221
Apostolakis SXu ZTan ZChan GCampanoni SAugust DDonaldson ATorlak E(2020)SCAF: a speculation-aware collaborative dependence analysis frameworkProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386028(638-654)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386028
Karkare AHaddad HWainwright RChbeir R(2018)TwASProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167330(1857-1864)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167330
Show More Cited By

Index Terms

Solving shape-analysis problems in languages with destructive updating
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

Solving shape-analysis problems in languages with destructive updating

This article concerns the static analysis of programs that perform destructive updating on heap-allocated storage. We give an algorithm that uses finite shape graphs to approximate conservatively the possible “shapes” that heap-allocated structures in a ...
Destructive effect analysis and finite differencing for strict functional languages
Shape analysis in a functional language by using regular languages

Shape analysis is concerned with the compile-time determination of the 'shape' the heap may take at runtime, meaning by this the pointer chains that may happen within, and between, the data structures built by the program. This includes detecting alias ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1996

423 pages

ISBN:0897917693

DOI:10.1145/237721

Chairman:
Hans-J. Boehm
Xerox Palo Alto Research Center,Palo Alto,CA
,
Conference Chair:
Guy Steele
Sun Microsystems Labs.

Copyright © 1996 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL96

Sponsor:

POPL96: 23rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 21 - 24, 1996

Florida, St. Petersburg Beach, USA

Acceptance Rates

POPL '96 Paper Acceptance Rate 34 of 148 submissions, 23%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

90
Total Citations
View Citations
122
Total Downloads

Downloads (Last 12 months)65
Downloads (Last 6 weeks)8

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hainry EPéchoux R(2023)A General Noninterference Policy for Polynomial TimeProceedings of the ACM on Programming Languages10.1145/35712217:POPL(806-832)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571221
Apostolakis SXu ZTan ZChan GCampanoni SAugust DDonaldson ATorlak E(2020)SCAF: a speculation-aware collaborative dependence analysis frameworkProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386028(638-654)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386028
Karkare AHaddad HWainwright RChbeir R(2018)TwASProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167330(1857-1864)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167330
Johnson NFix JBeard SOh TJablin TAugust DReddi VSmith ATang L(2017)A collaborative dependence analysis frameworkProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049849(148-159)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049849
Johnson NFix JBeard SOh TJablin TAugust D(2017)A collaborative dependence analysis framework2017 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2017.7863736(148-159)Online publication date: Feb-2017
https://doi.org/10.1109/CGO.2017.7863736
Kanvar VKhedker U(2016)Heap Abstractions for Static AnalysisACM Computing Surveys10.1145/293109849:2(1-47)Online publication date: 30-Jun-2016
https://dl.acm.org/doi/10.1145/2931098
Krall ASchordan MPavlu V(2014)Computation of alias sets from shape graphs for comparison of shape analysis precisionIET Software10.1049/iet-sen.2012.00498:3(120-133)Online publication date: 1-Jun-2014
https://doi.org/10.1049/iet-sen.2012.0049
Rival XToubhans AChang B(2014)Construction of Abstract Domains for Heterogeneous Properties (Position Paper)Leveraging Applications of Formal Methods, Verification and Validation. Specialized Techniques and Applications10.1007/978-3-662-45231-8_40(489-492)Online publication date: 2014
https://doi.org/10.1007/978-3-662-45231-8_40
Dasgupta SKarkare AReddy V(2013)Precise shape analysis using field sensitivityInnovations in Systems and Software Engineering10.1007/s11334-013-0198-79:2(79-93)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s11334-013-0198-7
Dasgupta SKarkare AOssowski SLecca P(2012)Precise shape analysis using field sensitivityProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2231982(1300-1307)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2231982
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents