Article

Free access

Interprocedural dependence analysis and parallelization

Authors:

Ron CytronAuthors Info & Claims

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

Pages 162 - 175

https://doi.org/10.1145/12276.13328

Published: 01 July 1986 Publication History

Abstract

We present a method that combines a deep analysis of program dependences with a broad analysis of the interaction among procedures. The method is more efficient than existing methods: we reduce many tests, performed separately by existing methods, to a single test. The method is more precise than existing methods with respect to references to multi-dimensional arrays and dependence information hidden by procedure calls. The method is more general than existing methods: we accommodate potentially aliased variables and structures of differing shapes that share storage. We accomplish the above through a unified approach that integrates subscript analysis with aliasing and interprocedural information.

References

[1]

John R. Allen, "Dependence Analysis for Subscript Variables and Its Application to Program Transformations", Rice Ph.D. Thesis, April 1983.

Digital Library

[2]

Utpal Banerjee, "Data Dependence in Ordinary Programs", M,S. Thesis, University of Illinois at Urbana-Champaign, DCS Report No. UIUCDCS-R-76-837, November 1976.

[3]

Utpal Banerjee, "Speedup of Ordinary Programs", Ph.D. Thesis, University of Illinois at Urbana- Champaign, DCS Report No. UIUCDCS-R-79-989, October 1979.

Digital Library

[4]

John Banning, "An Efficient Way to Find the Side Effects of Procedure Calls and the Aliases of Variables", Conf. Rec. Seventh ACM Symposium on Principles of Programming Languages, January 1980.

Digital Library

[5]

Michael Burke, "An Interval Analysis Approach Toward Interprocedural Data Flow", IBM Research Report RC 10640, July 1984.

[6]

Michael Burke and Ron Cytron, "Interprocedural Dependence Analysis and Parallelization", IBM Research Report RCI 1794, April, 1986.

[7]

Keith Cooper, "Interprocedural Data Flow Analysis in a Programming Environment", Rice Ph.D. Thesis, April 1983.

Digital Library

[8]

Keith Cooper, "Analyzing Aliases of Reference Formal Parameters", Conf. Rec. Twelfth ACM Symposium on Principles of Programming Languages, 281-290, January 1985.

Digital Library

[9]

Keith Cooper and Ken Kennedy, "Efficient Computation of Flow Insensitive Interproeedurai Summary Information", Proceedings of the SIGPLAN 84 Symposiumon Compiler Construction, June 1984.

Digital Library

[10]

Ron Cytron, "Compile-time Scheduling and Optimization for Asynchronous Machines", Ph.D. Thesis, University of Illinois at Urbana- Champaign, August, 1982.

[11]

Christopher A. Huson, "An In-Line Subroutine Expander for Parafrase", M.S. Thesis, University of Illinois at Urbana-Champaign, 1982.

[12]

G. KildaU, "A Unified Approach to Program Optimization", Conf, Rec. First A CM Symposium on Principles of Programming Languages, 194-206, October 1973.

Digital Library

[13]

David J. Kuck, The Structure of Computers and Computations, Volume 1, John Wiley and Sons, New York, 1978.

Digital Library

[14]

Bruce R. Leasure, "Compiling Serial Languages for Parallel Machines", M.S. Thesis, University of Illinois at Urbana-Champaign, 1976.

[15]

J.H. Reif and H.R. Lewis, "Symbolic Evaluation and the Global Value Graph", Conf. Rec. Fourth ACM Symposium on Principles of Programming Languages, January 1977.

Digital Library

[16]

Robert Shostak, "Deciding Linear Inequalities by Computing Loop Residues", Journal of the Association for Computing Machinery, Vol. 28, No. 4, October 1981.

Digital Library

[17]

Remi J. Triolet, "Contribution a la Parellisation Automatique de Programmes Fortran Comportant des Appels de Procedure", Ph.D. Thesis, L'Universite Pierre et Marie Curie (Paris VI), December 1984.

[18]

Mark Wegman and Ken Zadeck, "Constant Propagation with Conditional Branches", Conf. Rec. Twelfth ACM Symposium on Principles of Programming Languages, 291-299, January 1985.

Digital Library

[19]

Michael J. Wolfe, "Optimizing Supercompilers for Supercomputers", Ph.D. Thesis, University of Illinois at Urbana-Champaign, 1982.

Digital Library

Cited By

Lubin JFerguson JYe KYim JChasins S(2024)Equivalence by Canonicalization for Synthesis-Backed RefactoringProceedings of the ACM on Programming Languages10.1145/36564538:PLDI(1879-1904)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656453
Vasilakis NKallas KMamouras KBenetopoulos ACvetković LBarbalace ABhatotia PAlvisi LCadar C(2021)PaShProceedings of the Sixteenth European Conference on Computer Systems10.1145/3447786.3456228(49-66)Online publication date: 21-Apr-2021
https://dl.acm.org/doi/10.1145/3447786.3456228
Vasilakis NKarel BPalkhiwala YSonchack JDeHon ASmith JMcKinley KFisher K(2019)Ignis: scaling distribution-oblivious systems with light-touch distributionProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314586(1010-1026)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314586
Show More Cited By

Index Terms

Recommendations

Interprocedural dependence analysis and parallelization
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

The area of dependence analysis has served as grounds for fruitful research as well as practical implementation. Compilers and tools that utilize dependence information can generate code that takes advantage of parallel resources and storage hierarchies ...
Interprocedural dependence analysis and parallelization

We present a method that combines a deep analysis of program dependences with a broad analysis of the interaction among procedures. The method is more efficient than existing methods: we reduce many tests, performed separately by existing methods, to a ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

July 1986

275 pages

ISBN:0897911970

DOI:10.1145/12276

Editor:
Richard L Wexelblat
Philips Laboratories, Briarcliff Manor, NY

ACM SIGPLAN Notices Volume 21, Issue 7
July 1986
275 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/13310
Editor:
Richard L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY
Issue’s Table of Contents

Copyright © 1986 Authors.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCC86

Sponsor:

SIGPLAN

SCC86: SIGPLAN Symposium on Compiler Construction

June 25 - 27, 1986

California, Palo Alto, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

239
Total Citations
View Citations
1,031
Total Downloads

Downloads (Last 12 months)93
Downloads (Last 6 weeks)17

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lubin JFerguson JYe KYim JChasins S(2024)Equivalence by Canonicalization for Synthesis-Backed RefactoringProceedings of the ACM on Programming Languages10.1145/36564538:PLDI(1879-1904)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656453
Vasilakis NKallas KMamouras KBenetopoulos ACvetković LBarbalace ABhatotia PAlvisi LCadar C(2021)PaShProceedings of the Sixteenth European Conference on Computer Systems10.1145/3447786.3456228(49-66)Online publication date: 21-Apr-2021
https://dl.acm.org/doi/10.1145/3447786.3456228
Vasilakis NKarel BPalkhiwala YSonchack JDeHon ASmith JMcKinley KFisher K(2019)Ignis: scaling distribution-oblivious systems with light-touch distributionProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314586(1010-1026)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314586
Ma SBertino ENepal SLi JOstry DDeng RJha S(2019)Finding Flaws from Password Authentication Code in Android AppsComputer Security – ESORICS 201910.1007/978-3-030-29959-0_30(619-637)Online publication date: 15-Sep-2019
https://doi.org/10.1007/978-3-030-29959-0_30
Hong DChen QMao ZKim TWang CKim TWu D(2017)An Initial Investigation of Protocol CustomizationProceedings of the 2017 Workshop on Forming an Ecosystem Around Software Transformation10.1145/3141235.3141236(57-64)Online publication date: 3-Nov-2017
https://dl.acm.org/doi/10.1145/3141235.3141236
ElTantawy AAamodt THsu WYang CLipasti MLee H(2016)MIMD synchronization on SIMT architecturesThe 49th Annual IEEE/ACM International Symposium on Microarchitecture10.5555/3195638.3195652(1-14)Online publication date: 15-Oct-2016
https://dl.acm.org/doi/10.5555/3195638.3195652
Kumar SSrinivasan VSharifian ASumner NShriraman A(2016)Peruse and ProfitProceedings of the 2016 International Conference on Supercomputing10.1145/2925426.2926269(1-13)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1145/2925426.2926269
ElTantawy AAamodt T(2016)MIMD synchronization on SIMT architectures2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO.2016.7783714(1-14)Online publication date: Oct-2016
https://doi.org/10.1109/MICRO.2016.7783714
Ou PDemsky B(2015)AutoMO: automatic inference of memory order parameters for C/C++11ACM SIGPLAN Notices10.1145/2858965.281428650:10(221-240)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814286
Ou PDemsky BAldrich JEugster P(2015)AutoMO: automatic inference of memory order parameters for C/C++11Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814286(221-240)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814286
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