article

Free access

Dependence analysis for pointer variables

Authors:

T. RepsAuthors Info & Claims

ACM SIGPLAN Notices, Volume 24, Issue 7

Pages 28 - 40

https://doi.org/10.1145/74818.74821

Published: 21 June 1989 Publication History

Abstract

Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as Lisp and Pascal. We have defined a family of algorithms that compute safe approximations to the flow, output, and anti-dependencies of a program written in such a language. Our algorithms account for destructive updates to fields of a structure and thus are not limited to the cases where all structures are trees or acyclic graphs; they are applicable to programs that build cyclic structures.

Our technique extends an analysis method described by Jones and Muchnick that determines an approximation to the actual layouts of memory that can arise at each program point during execution. We extend the domain used in their abstract interpretation so that the (abstract) memory locations are labeled by the program points that set their contents. Data dependencies are then determined from these memory layouts according to the component labels found along the access paths that must be traversed during execution to evaluate the program's statements and predicates.

For structured programming constructs, the technique can be extended to distinguish between loop-carried and loop-independent dependencies, as well as to determine lower bounds on minimum distances for loop-carried dependencies.

References

[1]

Aho, A.V., Sethi, R., and Ullman, J.D., Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading, MA (1986).

Digital Library

[2]

Allen, J.R., "Dependence analysis for subscripted variables and its application to program transformations," Ph.D. dissertation, Dept. of Math. Sciences, Rice Univ., Houston, TX (April 1983).

Digital Library

[3]

Chase, D.R., "Garbage collection and other optimizations," Ph.D. dissertation, Dept. of Computer Science, Rice Univ., Houston, TX (August 1987).

Digital Library

[4]

Cousot, P. and Cousot, R., "Abstract interpretation: A unified latrice model for static analysis of programs by construction or approximation of fixpoints," pp. 238-252 in Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, (Los Angeles, CA, January 17-19, 1977), ACM, New York, NY (1977).

Digital Library

[5]

Donzeau-Gouge, V., "Denotational definition of properties of program computations," in Program Flow Analysis: Theory and Applications, ed. S.S. Muchniek and N.D. lones,Prentice-Hall, Englewood Cliffs, NJ (1981).

[6]

Ferrante, J., Ottenstein, K., and Warren, J., "The program dependence graph and its use in optimization," ACM Transactions on Programming Languages and Systems 9(3)pp. 319-349 (July 1987).

Digital Library

[7]

Guama, V.A. Jr., "A technique for analyzing pointer and structure references in parallel restructuring compilers," CSRD Tech. Rep. 721, Center for Superccnnputing Research and Development, University of Illinois at Urbana-Champaign, Urbana, IL (January 1988).

[8]

Horwitz, S., Prins, J., and Reps, T., "Integrating non-interfering versions of programs," pp. 133-145 in Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages, (San Diego, CA, January 13-15, 1988), ACM, New York, NY (1988).

Digital Library

[9]

Horwitz, S., Reps, T., and Binktey, D., "Interproeedural slicing using dependence graphs," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23C/)(July 1988).

Digital Library

[10]

Horwitz, S., Pfedfer, P., and Reps, T., "Dependence analysis for poimer variables," <In preparation>, Computer Sciences Department, University of Wisconsin, Madison, Wi (1989).

[11]

Hudak, P., "A semantic model of reference counting and its abstraction," pp. 45-62 in Abstract Interpretation of Declarative Languages, ed. S. Abramsky and C. Hankin,Ellis Horwood Limited, Chichester, West Sussex, England (1987).

[12]

Jones, N.D. and Muchnick, S.S., "Flow analysis and optimization of Lisp-like structures," in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones,Prentice-Hall, Englewood Cliffs, NJ (I 981 ).

[13]

Kennedy, K., "A survey of data flow analysis techniques," in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones,Prentice-Hall, Englewood Cliffs, NJ (1981).

[14]

Kuck, D.J., Kuhn, R.H., Leasure, B., Padua, D.A., and Wolfe, M., "Dependence graphs and compiler optimizations," pp. 20%218 in Conference Record of the Eighth ACM Symposium on Principles of Programming Languages, (Williamsburg, VA, January 26-28, 1981), ACM, New York, NY (1981).

Digital Library

[15]

Lares, J.R., "Curare: Restructuring Lisp programs for concurrent execution," UCB/CSD 87/344, Ctnnputer Science Division, Dept. of Elec. Eng. and Comp. Sci., Univ. of California -Berkeley, Berkeley, CA (February 1987).

Digital Library

[16]

Lares, I.R. and Hilfinger, P.N., "Detecting conflicts between stmctun: accesses," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23(7)pp. 21-34 (July 1988).

Digital Library

[17]

Larus, J.R. and Hilfinger, P.N., "Restructuring Lisp programs for concurrent execution," Proceedings of the ACM/SIGPLAN PPEALS 88 (New Haven, CT, July 19-21, 1988), ACM $IGPLAN Notices 23(9) pp. 100-1 I0 (September 1988).

Digital Library

[18]

Lares, J.R., "Refining and Classifying Data Dependences," unpublished extended abstract, Berkeley, CA (November 1988).

[19]

Lams, J.R., private communication. 1988.

[20]

Neirynck, A., "Static Analysis of Aliases and Side Effects in Higher-Order Languages," Ph.D. dissertation, Computer Science Department, Comell University, Ithaca, NY (February 1988).

Digital Library

[21]

Ottenstein, K.J. and Ottenstein, L.M., "The program dependence graph in a software development environment," Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, (Pittsburgh, PA, Apr. 23-25, 1984), ACM SIGPLAN Notices 19(5)pp. 177-184 (May 1984).

Digital Library

[22]

Padua, D.A., "Multiprocessors: Discussion of some theoretical and practical problems," Ph.D. dissertation and Tech. Rep. R-79-990, Dept. of Computer Science, University of Illinois, Urbana, IL (November 1979).

Digital Library

[23]

Reps, T. and Yang, W., "The semantics of program slicing," TR- 777, Computer Sciences Department, University of Wisconsin, Madison, WI (June 1988).

[24]

Ruggieri, C. and Murtagh, T.P., "Lifetime analysis of dynamically allocated objects," pp. 285-293 in Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages, (San Diego, CA, January 13-15, 1988), ACM, New York, NY (1988).

Digital Library

[25]

Stransky, l., "Analyse sananfique de structures de donn~es dynamiques avec application au cas paniculier de langages LISPiens," Ph.D. dissertation, Universit~ de Paris-Sud, Centre d'Orsay (June 1988).

[26]

Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).

Digital Library

Cited By

(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Data-Flow AnalysisEngineering a Compiler10.1016/B978-0-12-815412-0.00015-2(449-516)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00015-2
Fu X(2016)On detecting environment sensitivity using slicingTheoretical Computer Science10.1016/j.tcs.2016.09.004656(27-45)Online publication date: Dec-2016
https://doi.org/10.1016/j.tcs.2016.09.004
Show More Cited By

Index Terms

Dependence analysis for pointer variables
1. Software and its engineering
  1. Software creation and management
    1. Software development process management
      1. Software development methods
  2. Software notations and tools
    1. Formal language definitions
      1. Semantics
    2. General programming languages
      1. Language features
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
    2. Program semantics

Recommendations

Dependence analysis for pointer variables
PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

Our concern is how to determine data dependencies between program constructs in programming languages with pointer variables. We are particularly interested in computing data dependencies for languages that manipulate heap-allocated storage, such as ...
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 ...
Practical pointer aliasing analysis

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 24, Issue 7

Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques

July 1989

355 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/74818

Editor:
Richard Wexelblat

Issue’s Table of Contents

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation
June 1989
355 pages
ISBN:089791306X
DOI:10.1145/73141
Editor:
R. L. Wexelblat
ACM Headquarters, New York, NY

Copyright © 1989 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 1989

Published in SIGPLAN Volume 24, Issue 7

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

188
Total Citations
View Citations
1,158
Total Downloads

Downloads (Last 12 months)162
Downloads (Last 6 weeks)22

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Data-Flow AnalysisEngineering a Compiler10.1016/B978-0-12-815412-0.00015-2(449-516)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00015-2
Fu X(2016)On detecting environment sensitivity using slicingTheoretical Computer Science10.1016/j.tcs.2016.09.004656(27-45)Online publication date: Dec-2016
https://doi.org/10.1016/j.tcs.2016.09.004
Dévai RJász JNagy CFerenc R(2014)Designing and implementing control flow graph for magic 4th generation languageActa Cybernetica10.14232/actacyb.21.3.2014.921:3(419-437)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.14232/actacyb.21.3.2014.9
(2012)BibliographyEngineering a Compiler10.1016/B978-0-12-088478-0.00024-4(765-785)Online publication date: 2012
https://doi.org/10.1016/B978-0-12-088478-0.00024-4
Kidd NReps TDolby JVaziri M(2011)Finding concurrency-related bugs using random isolationInternational Journal on Software Tools for Technology Transfer10.1007/s10009-011-0197-713:6(495-518)Online publication date: 23-Apr-2011
https://doi.org/10.1007/s10009-011-0197-7
Wilhelm RReps TSagiv M(2010)Shape Analysis and ApplicationsThe Compiler Design Handbook10.1201/9781420040579.ch5Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch5
Mund GMall R(2009)Program SlicingThe Compiler Design Handbook10.1201/9781420043839.ch14(14-1-14-35)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch14
Wilhelm RSagiv MReps T(2009)Shape Analysis and ApplicationsThe Compiler Design Handbook10.1201/9781420043839.ch12(12-1-12-44)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch12
Binkley DDanicic SGyimóthy THarman MKiss ÁKorel B(2006)A formalisation of the relationship between forms of program slicingScience of Computer Programming10.1016/j.scico.2006.04.00762:3(228-252)Online publication date: 15-Oct-2006
https://dl.acm.org/doi/10.1016/j.scico.2006.04.007
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

Figures

Tables

Media

View Issue’s Table of Contents