Article

Free access

Analyzing aliases of reference formal parameters

Author:

Keith D. CooperAuthors Info & Claims

POPL '85: Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

Pages 281 - 290

https://doi.org/10.1145/318593.318658

Published: 01 January 1985 Publication History

PDF eReader

Abstract

Compilers for languages with call-by-reference formal parameters must deal with aliases arising from the renaming effects at call sites. This paper presents a set of techniques for analyzing aliasing patterns. The analysis is divided into detecting the introduction of aliases and tracking their propagation. The algorithm for introduction analysis is simple enough to be performed in a structured editor or parser. A data flow analysis framework is given for the propagation problem, making it possible to solve using standard algorithms from global data flow analysis. Several optimizations are shown which can shrink the size of the problem, and extensions are given to handle ALGOL-style name scoping. Finally, this technique is compared to an alternative implementation strategy and an approximate technique.

References

[1]

{AhUl} A. Aho, and J. Ullman. Principles of Compiler Design, Addison-Wesley, Reading, Ma., 1977.

Digital Library

Google Scholar

[2]

{Alle} F. Allen, J. Carter, J. Fabri, J. Ferrante, W. Harrison, P. Loewner. L. Trevillyan, "The Experimental Compiling System", IBM Journal of Research and Development, Vol. 24, No. 6, Nov. 1980.

Digital Library

Google Scholar

[3]

{ANSI} ANSI, American National Standard FORTRAN-66 X3.9-1966.

Google Scholar

[4]

{Bann} J. Banning, "A Method for Determining the Side Effects of Procedure Calls", PhD Dissertation, Stanford University, Aug. 1978.

Digital Library

Google Scholar

[5]

{Bart} J. Barth, "A Practical Interprocedural Data Flow Analysis Algorithm". CACM Vol. 21. No. 9, Sept. 1978, pp. 724-736.

Digital Library

Google Scholar

[6]

{CoKe} K. Cooper, and K. Kennedy, "Efficient Computation of Flow Insensitive Interprocedural Summary Information", Proceedings SICPLAN '84 Symposium on Compiler Construction, June, 1984.

Digital Library

Google Scholar

[7]

{Coop} K. Cooper, "Interprocedural Data Flow Analysis in a Programming Environment", PhD Dissertation, Rice University, May 1983.

Digital Library

Google Scholar

[8]

{HoKe} R. Hood, and K. Kennedy, "A Programming Environment for Fortran". Rice University, Department of Mathematical Sciences TR84-1, Rice University, 1984. (to appear in the proceedings of the Eighteenth Annual Hawaii International Conference on Systems Sciences, January, 1985).

Google Scholar

[9]

{KaUl} J. Kam and J. Ullman, "Global Data Flow Analysis and Iterative Algorithms", JACM, Vol. 23, No. 1, Jan. 1976, pp. 158-171.

Digital Library

Google Scholar

[10]

{Myer} E. Myers, "A Precise and Efficient Algorithm for Determining Existential Summary Data Flow Information", University of Colorado at Boulder, Department of Computer Science Technical Report #CU-CS-175-80.

Google Scholar

[11]

{Paul} G. Paul, "VECTRAN and the Proposed Vector/Array Extensions to ANSI FORTRAN for Scientific and Engineering Computation", IBM Conference on Scientific and Parallel Computing, Rome, Italy, March 1982.

Digital Library

Google Scholar

[12]

{Spil} T. Spillman, "Exposing Side-Effects in a PL/I Optimizing Compiler", IFIPS Proceedings, 1971, pp 376-381.

Google Scholar

[13]

{Wieh} W. Weihl, "Interprocedural Data Flow Analysis in the Presence of Pointers, Procedure Variables, and Label Variables", Proceedings 7th POPL, Jan. 1980.

Digital Library

Google Scholar

Cited By

View all

Shivam AWolfe M(2019)OpenACC Routine Directive Propagation Using Interprocedural AnalysisAccelerator Programming Using Directives10.1007/978-3-030-12274-4_5(99-113)Online publication date: 24-Jan-2019
https://doi.org/10.1007/978-3-030-12274-4_5
Ryder BWiedermann B(2012)Language design and analyzabilitySoftware—Practice & Experience10.1002/spe.113342:1(3-18)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1002/spe.1133
Khedker USanyal ASathe B(2010)ReferencesData Flow Analysis10.1201/9780849332517.bmatt(371-378)Online publication date: 13-Jan-2010
https://doi.org/10.1201/9780849332517.bmatt
Show More Cited By

Index Terms

Analyzing aliases of reference formal parameters
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types

Recommendations

Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We present practical approximation methods for computing interprocedural aliases and side effects for a program written in a language that includes pointers, reference parameters and recursion. We present the following results: 1) An algorithm for flow-...
Building a bridge between pointer aliases and program dependences

In this paper we present a surprisingly simple reduction of the program dependence problem to the may-alias problem. While both problems are undecidable, providing a reduction between them has great practical importance. Program dependence information ...
Interprocedural Symbolic Evaluation of Ada Programs with Aliases
Ada-Europe '99: Proceedings of the 1999 Ada-Europe International Conference on Reliable Software Technologies

Symbolic Evaluation is a technique aimed at determining dynamic properties of programs. We extend our intraprocedural data-flow framework introduced in [3] to support interprocedural symbolic evaluation. Our data-flow framework utilizes a novel approach ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

POPL '85: Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

January 1985

340 pages

ISBN:0897911474

DOI:10.1145/318593

Chairmen:
Mary S. Van Deusen
IBM Watson Research
,
Zvi Galil
Columbia University, New York, NY
,
Brian K. Reid
Stanford Univ., Stanford, CA

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: 01 January 1985

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

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

66
Total Citations
View Citations
454
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)18

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shivam AWolfe M(2019)OpenACC Routine Directive Propagation Using Interprocedural AnalysisAccelerator Programming Using Directives10.1007/978-3-030-12274-4_5(99-113)Online publication date: 24-Jan-2019
https://doi.org/10.1007/978-3-030-12274-4_5
Ryder BWiedermann B(2012)Language design and analyzabilitySoftware—Practice & Experience10.1002/spe.113342:1(3-18)Online publication date: 1-Jan-2012
https://dl.acm.org/doi/10.1002/spe.1133
Khedker USanyal ASathe B(2010)ReferencesData Flow Analysis10.1201/9780849332517.bmatt(371-378)Online publication date: 13-Jan-2010
https://doi.org/10.1201/9780849332517.bmatt
Budimlić ZJoyner MKennedy K(2007)Improving Compilation of Java Scientific ApplicationsInternational Journal of High Performance Computing Applications10.1177/109434200707843721:3(251-265)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1177/1094342007078437
Uehara TKunieda YTsuda T(2005)An automatic vectorizing/parallelizing Pascal compiler V-Pascal ver. 3High Performance Computing10.1007/BFb0024217(205-216)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0024217
Gellerich WPloedereder E(2005)Parameter-induced aliasing and related problems can be avoidedReliable Software Technologies — Ada-Europe '9710.1007/3-540-63114-3_15(161-172)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-63114-3_15
Callahan DCooper KHood RKennedy KTorczon LWarren S(2005)Parallel programming support in ParaScopeParallel Computing in Science and Engineering10.1007/3-540-18923-8_16(89-106)Online publication date: 5-Jun-2005
https://doi.org/10.1007/3-540-18923-8_16
Landi WRyder B(2004)A safe approximate algorithm for interprocedural pointer aliasingACM SIGPLAN Notices10.1145/989393.98944039:4(473-489)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1145/989393.989440
Callahan DCooper KKennedy KTorczon L(2004)Interprocedural constant propagationACM SIGPLAN Notices10.1145/989393.98941239:4(155-166)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1145/989393.989412
Burke MCytron R(2004)Interprocedural dependence analysis and parallelizationACM SIGPLAN Notices10.1145/989393.98941139:4(139-154)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1145/989393.989411
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects

Building a bridge between pointer aliases and program dependences

Interprocedural Symbolic Evaluation of Ada Programs with Aliases