More Web Proxy on the site http://driver.im/

Article

Free access

A precise inter-procedural data flow algorithm

Author:

Eugene M. MyersAuthors Info & Claims

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

Pages 219 - 230

https://doi.org/10.1145/567532.567556

Published: 26 January 1981 Publication History

Abstract

Data flow analysis is well understood at the intra-procedural level and efficient algorithms are available. When inter-procedural mechanisms such as recursion, procedure nesting, and pass-by-reference aliasing are introduced, the data flow problems become much more difficult. The avail, live, and must-summary data flow problems are shown to be NP-complete in the presence of aliasing. However, an algorithm is presented with O(SET*EDGE) time performance where EDGE is the size of the program's flow graph and SET is a possible exponential number which reflects the number of aliasing patterns of the program. It is argued that in practice SET is small and on the order of the number of variables of the program.

References

[1]

{A} Allen,F. E. "Interprocedural Data Flow Analysis." Information Processing 74, North-Holland Pub. Co., Amsterdam (1974), 398-402.

[2]

{AC} Allen, F. E. and Cocke, J. "A Program Data Flow Analysis Procedure." Comm. ACM 19, 3(1976), 137-146.

Digital Library

[3]

{Barth} Barth, J. M. "A Practical Interprocedural Data Flow Analysis Algorithm." Comm. ACM 21, 9(1978), 724-736.

Digital Library

[4]

{Ban} Banning, J. P. "An Efficient Way to Find the Side Effects of Procedure Calls and the Aliases of Variables." Conf. Rec. Seventh ACM Symp. Principles of Programming Languages (1980), 29-41.

Digital Library

[5]

{Cocke} Cocke, J. "Global Common Subexpression Elimination." SIGPLAN Notices 5(1970), 20-24.

Digital Library

[6]

{Cook} Cook, S. A. "The Complexity of Theorem Proving Procedures." Proc. 3rd Annual ACM Symposium on Theory of Computing (1971), 151-158.

Digital Library

[7]

{FO} Fosdick, L. D. and Osterweil, L. J. "Data Flow Analysis in Software Reliability." ACM Computing Surveys 8, 3(1976).

Digital Library

[8]

{GJ} Garey, M. R. and Johnson, D. S. Computers and Intractibility -- A Guide to the Theory of NP-Completeness. W. H. Freeman and Co. (1978).

Digital Library

[9]

{GW} Graham, S. L. and Wegman, M. "A Fast and Usually Linear Algorithm for Global Flow Analysis." J. ACM 23, 1(1976), 172-202.

Digital Library

[10]

{H} Hecht, M. S. Flow Analysis of Computer Programs. North-Holland Pub. Co., New York (1977).

Digital Library

[11]

{Karp} Karp, R. M. "A Note on the Application of Graph Theory to Digital Computer Programming." Information and Control, 3(1960), 179-190.

[12]

{Kildall} Kildall, G. A. "A Unified Approach to Global Program Optimization." Conf. Rec. First ACM Symp. Principles of Programming Languages (1973), 194-206.

Digital Library

[13]

{M} Myers, E. W. "A Precise and Efficient Algorithm for Determining Existential Summary Data Flow Information." Tech. Rep. CU-CS-175-80, Univ. of Colorado, Boulder, Colo., March 1980.

[14]

{R1} Rosen, B. K. "High Level Data Flow Analysis, Pt. 1(Classical Structured Programming)." Res. Rep. RC5598, IBM T.J. Watson Res. Ct., Yorktown Heights, New York, August 1975.

[15]

{R2} Rosen, B. K. "High Level Data Flow Analysis, Pt. 2(Escapes and Jumps)." Res. Rep. RC5744, IBM T.J. Watson Rec. Ct., Yorktown Heights, New York, April 1976.

[16]

{S} Spillman, T. C. "Exposing Side-Effects in a PL/1 Optimizing Compiler." Information Processing, North-Holland Pub. Co., Amsterdam (1971), 376-381.

[17]

{UH} Ullman, J. D. and Hecht, M. S. "A Simple Algorithm for Global Data Flow Analysis Problems." SIAM J. Computing 4, 4(1975), 519-532.

[18]

{UK} Ullman, J. D. and Kam, J. B. "Global Data Flow Analysis and Iterative Algorithms." J. ACM 23, 1(1976), 158-171.

Digital Library

Cited By

Conrado GGoharshady ALam C(2023)The Bounded Pathwidth of Control-Flow GraphsProceedings of the ACM on Programming Languages10.1145/36228077:OOPSLA2(292-317)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622807
Liu YWang WJia YXu SLiu Z(2023)CRSExtractor: Automated configuration option read sites extraction towards IoT cloud infrastructureHeliyon10.1016/j.heliyon.2023.e153539:4(e15353)Online publication date: Apr-2023
https://doi.org/10.1016/j.heliyon.2023.e15353
Jaiswal SKhedker UMycroft A(2021)A Unified Model for Context-Sensitive Program Analyses:ACM Computing Surveys10.1145/345656354:6(1-37)Online publication date: 13-Jul-2021
https://dl.acm.org/doi/10.1145/3456563
Show More Cited By

Recommendations

Inter-procedural data-flow analysis with IFDS/IDE and Soot
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis

The IFDS and IDE frameworks by Reps, Horwitz and Sagiv are two general frameworks for the inter-procedural analysis of data-flow problems with distributive flow functions over finite domains. Many data-flow problems do have distributive flow functions ...
Precise and efficient integration of interprocedural alias information into data-flow analysis

Data-flow analysis is a basis for program optimization and parallelizing transformations. The mechanism of passing reference parameters at call sites generates interprocedural aliases which complicate this analysis. Solutions have been developed for ...
Precise flow-insensitive may-alias analysis is NP-hard

Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

January 1981

230 pages

ISBN:089791029X

DOI:10.1145/567532

Conference Chairs:
John White
University of Connecticut, Storrs, Connecticut
,
Richard Lipton
Princeton University, Princeton, NJ
,
Program Chair:
Patricia C. Goldberg
IBM Thomas J. Watson Research Center, Yorktown Heights, NY

Copyright © 1981 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: 26 January 1981

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

POPL '81 Paper Acceptance Rate 24 of 121 submissions, 20%;

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

156
Total Citations
View Citations
1,222
Total Downloads

Downloads (Last 12 months)238
Downloads (Last 6 weeks)61

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Conrado GGoharshady ALam C(2023)The Bounded Pathwidth of Control-Flow GraphsProceedings of the ACM on Programming Languages10.1145/36228077:OOPSLA2(292-317)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622807
Liu YWang WJia YXu SLiu Z(2023)CRSExtractor: Automated configuration option read sites extraction towards IoT cloud infrastructureHeliyon10.1016/j.heliyon.2023.e153539:4(e15353)Online publication date: Apr-2023
https://doi.org/10.1016/j.heliyon.2023.e15353
Jaiswal SKhedker UMycroft A(2021)A Unified Model for Context-Sensitive Program Analyses:ACM Computing Surveys10.1145/345656354:6(1-37)Online publication date: 13-Jul-2021
https://dl.acm.org/doi/10.1145/3456563
Alhanahnah MStevens CBagheri HKhurshid SPăsăreanu C(2020)Scalable analysis of interaction threats in IoT systemsProceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3395363.3397347(272-285)Online publication date: 18-Jul-2020
https://dl.acm.org/doi/10.1145/3395363.3397347
Zhang JWang XZhang HSun HWang KLiu XAtlee JBultan TWhittle J(2019)A novel neural source code representation based on abstract syntax treeProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00086(783-794)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00086
Cai HSantelices R(2016)Method-level program dependence abstraction and its application to impact analysisJournal of Systems and Software10.5555/3044222.3051229122:C(311-326)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.5555/3044222.3051229
Cai HSantelices RThain D(2016)DiaProACM Transactions on Software Engineering and Methodology10.1145/289475125:2(1-50)Online publication date: 6-Apr-2016
https://dl.acm.org/doi/10.1145/2894751
Chen KWang XChen YWang PLee YWang XMa BWang AZhang YZou W(2016)Following Devil's Footprints: Cross-Platform Analysis of Potentially Harmful Libraries on Android and iOS2016 IEEE Symposium on Security and Privacy (SP)10.1109/SP.2016.29(357-376)Online publication date: May-2016
https://doi.org/10.1109/SP.2016.29
Cai HSantelices R(2015)Abstracting Program Dependencies Using the Method Dependence GraphProceedings of the 2015 IEEE International Conference on Software Quality, Reliability and Security10.1109/QRS.2015.18(49-58)Online publication date: 3-Aug-2015
https://dl.acm.org/doi/10.1109/QRS.2015.18
Caltais G(2015)Expression-Based Aliasing for OO–languagesFormal Techniques for Safety-Critical Systems10.1007/978-3-319-17581-2_4(47-61)Online publication date: 16-Apr-2015
https://doi.org/10.1007/978-3-319-17581-2_4
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