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

article

Free access

A program data flow analysis procedure

Authors:

J. CockeAuthors Info & Claims

Communications of the ACM, Volume 19, Issue 3

Page 137

https://doi.org/10.1145/360018.360025

Published: 01 March 1976 Publication History

Abstract

The global data relationships in a program can be exposed and codified by the static analysis methods described in this paper. A procedure is given which determines all the definitions which can possibly “reach” each node of the control flow graph of the program and all the definitions that are “live” on each edge of the graph. The procedure uses an “interval” ordered edge listing data structure and handles reducible and irreducible graphs indistinguishably.

References

[1]

Aho, A.V., and Ullman, J.D. The Theory of Parsing, Translation, and Compiling, Vol. 2. Prentice-Hall, Englewood Cliffs, N.J., 1973.

Digital Library

[2]

Aho, A.V., and Ullman, J.D. Node listings for reducible flow graphs. Proc. 7th Ann. Syrup. on the Theory of Computing, Albuquerque, N.M., May 1975, pp. 177-185.

Digital Library

[3]

Allen, F.E. Control flow analysis. SIGPLAN Notices (ACM Newsletter) 5 (July 1970), 1-19.

Digital Library

[4]

Allen, F.E. A basis for program optimization. Proc. IFIP Congress. North-Holland Pub. Co., Amsterdam, 1971, pp. 385-390.

[5]

Allen, F.E. A method for determining program data relationships. In Lecture Notes in Computer Science, Vol. 5, International Symposium on Theoretical Programming, Springer-Verlag, Berlin, 1974, pp. 299-308.

Digital Library

[6]

Allen, F.E. Interprocedural data flow analysis. Proc. IFIP Congress, North-Holland Pub. Co., Amsterdam, 1974, pp. 398-402; and IBM Research Rep. RC 4633, Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1973.

[7]

Allen, F.E., and Cocke, J. Graph theoretic constructs for program control flow analysis. IBM Research Report RC 3923, Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1972.

[8]

Cocke, J., and Schwartz, J.T. Programming Languages and their Compilers: Preliminary Notes. Courant Institute of Mathematical Sciences, New York U., N.Y., 1969.

Digital Library

[9]

Graham, S.U, and Wegman, M.,A fast and usually linear algorithm for global flow analysis. Conf. Rec., 2nd ACM Symp. on Principles of Programming Languages, Palo Alto, Calif., Jan. 1975, pp. 22-34.

Digital Library

[10]

Hecht, M.S., and Ullman, J.D. Analysis of a simple algorithm for global flow problems. Conf. Record, ACM Symp. on Principles of Programming Languages, Boston, Mass., Oct. 1973, pp. 207-217.

Digital Library

[11]

Hecht, M.S., and Ullman, J.D. Flow graph reducibility. SIAM J. Computing 1, 2 (June 1972), 188-202.

[12]

Hecht, M.S., and Ullman, J.D. Characterizations of reducible flow graphs. J. ACM 21, 3 (July 1974), 367-375.

Digital Library

[13]

Kam, J.B., and Ullman, J.D. Global optimization problems and iterative algorithms. TR-146, Computer Sci. Lab., Princeton U., Princeton, N.J., 1974.

[14]

Kennedy, K. A global flow analysis algorithm. Internat. J. Computer Math. A 3 (1971), 5-15.

[15]

Kennedy, K. A comparison of algorithms for global flow analysis. Tech. Rep. 476-093-1, Dep. of Mathematical Sciences, Rice U., Houston, Texas, 1974.

[16]

Kennedy, K. Node listings applied to data flow analysis. Conf. Rec., 2nd ACM Symp. on Principles of Programming Languages, Palo Alto, Calif., 1975, pp. 10-22.

Digital Library

[17]

Kildall, G.A. A unified approach to global program optimization. Conf. Record, ACM Syrup. on Principles of Programming Languages, Boston, Mass., 1973. pp. 194-206.

Digital Library

[18]

Knuth, D.E. An empirical study of FORTRAN programs. Software-Practice and Experience 1, 2 (1971), 105-134.

[19]

Kou, L.T. On live-dead analysis for global data flow problems. IBM Research Rep. RC 5278, Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1975.

[20]

Schaefer, M. A Mathematical Theory of Global Program Optimization. Prentice-Hall, Englewood Cliffs, N.J., 1973.

Digital Library

Cited By

Susan S(2024)Leveraging Slither and Interval Analysis to build a Static Analysis ToolElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.410.10410(150-166)Online publication date: 31-Oct-2024
https://doi.org/10.4204/EPTCS.410.10
Seo AKim YYang JLee YSon Y(2024)Software Weakness Detection in Solidity Smart Contracts Using Control and Data Flow Analysis: A Novel Approach with Graph Neural NetworksElectronics10.3390/electronics1316316213:16(3162)Online publication date: 10-Aug-2024
https://doi.org/10.3390/electronics13163162
Shi CLiu RChen HLi GGao S(2024)RNA: R1CS Normalization Algorithm Based on Data Flow Graphs for Zero-Knowledge ProofsFormal Aspects of Computing10.1145/366533936:4(1-24)Online publication date: 17-May-2024
https://dl.acm.org/doi/10.1145/3665339
Show More Cited By

Recommendations

Eliminating two kinds of data flow inaccuracy in the presence of pointer aliasing
APDC '97: Proceedings of the 1997 Advances in Parallel and Distributed Computing Conference (APDC '97)

Program languages with sophisticated usage of pointers as C are hard to analyze. Recent researches on pointer analysis focus on tracking the possible values of pointers, when a program point is reached, and great progress has been achieved. However, how ...
Double iterative framework for flow-sensitive interprocedural data flow analysis

Compiler optimization, parallel processing, data flow testing, and symbolic debugging can benefit from interprocedural data flow analysis. However, the live, reaching definition, and most summary data flow problems are theoretically intractable in the ...
Computing maximum fixed point solutions over feasible paths in data flow analyses
Abstract
The control flow graph (CFG) representation of a procedure used by virtually all flow-sensitive program analyses, admits a large number of infeasible control flow paths i.e., these paths do not occur in any execution of the program. Hence the ...
Highlights
- Infeasible control flow paths introduce imprecision in data flow analysis results.
- Maximum fixed point solutions should be computed over feasible paths only.
- Feasible path MFP solutions increase precision by eliminating effect of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 19, Issue 3

March 1976

53 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/360018

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago,IL

Issue’s Table of Contents

Copyright © 1976 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: 01 March 1976

Published in CACM Volume 19, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

314
Total Citations
View Citations
6,118
Total Downloads

Downloads (Last 12 months)424
Downloads (Last 6 weeks)54

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Susan S(2024)Leveraging Slither and Interval Analysis to build a Static Analysis ToolElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.410.10410(150-166)Online publication date: 31-Oct-2024
https://doi.org/10.4204/EPTCS.410.10
Seo AKim YYang JLee YSon Y(2024)Software Weakness Detection in Solidity Smart Contracts Using Control and Data Flow Analysis: A Novel Approach with Graph Neural NetworksElectronics10.3390/electronics1316316213:16(3162)Online publication date: 10-Aug-2024
https://doi.org/10.3390/electronics13163162
Shi CLiu RChen HLi GGao S(2024)RNA: R1CS Normalization Algorithm Based on Data Flow Graphs for Zero-Knowledge ProofsFormal Aspects of Computing10.1145/366533936:4(1-24)Online publication date: 17-May-2024
https://dl.acm.org/doi/10.1145/3665339
Pelton BSapek AEguro KLo DForin AHumphrey MXi JCox DKarandikar Rde Fine Licht JBabin ECaulfield ABurger D(2024)Wavefront Threading Enables Effective High-Level SynthesisProceedings of the ACM on Programming Languages10.1145/36564208:PLDI(1066-1090)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656420
Su ZXu XHuang ZZhang ZYe YHuang JZhang X(2024)CodeArt: Better Code Models by Attention Regularization When Symbols Are LackingProceedings of the ACM on Software Engineering10.1145/36437521:FSE(562-585)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643752
Hu GWang ZTang CShen JDong ZYao SChen H(2024)WeBridge: Synthesizing Stored Procedures for Large-Scale Real-World Web ApplicationsProceedings of the ACM on Management of Data10.1145/36393192:1(1-29)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639319
Xu XCogo FMcIntosh S(2024)Mitigating the Uncertainty and Imprecision of Log-Based Code Coverage Without Requiring Additional Logging StatementsIEEE Transactions on Software Engineering10.1109/TSE.2024.343506750:9(2350-2362)Online publication date: Sep-2024
https://doi.org/10.1109/TSE.2024.3435067
Taft S(2024)Sound and precise static analysis using a generalization of static single assignment and value numberingInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-024-00762-126:5(621-632)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10009-024-00762-1
Troost LNeugebauer JKuchen H(2024)Dynamic Data-Flow Analysis with Dacite: Evaluating an Integrated Data-Flow Visualization ApproachEvaluation of Novel Approaches to Software Engineering10.1007/978-3-031-64182-4_12(251-270)Online publication date: 10-Jul-2024
https://doi.org/10.1007/978-3-031-64182-4_12
Xu YZhang MWang XChen JLiang RZhen YZhen C(2024)A Review of Code Vulnerability Detection Techniques Based on Static AnalysisComputational and Experimental Simulations in Engineering10.1007/978-3-031-44947-5_21(251-272)Online publication date: 25-Jan-2024
https://doi.org/10.1007/978-3-031-44947-5_21
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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents