article

Free access

The design of a data flow analyzer

Authors:

Anita L. Chow,

Andres RudmikAuthors Info & Claims

ACM SIGPLAN Notices, Volume 17, Issue 6

Pages 106 - 113

https://doi.org/10.1145/872726.806985

Published: 01 June 1982 Publication History

PDF eReader

Abstract

This paper presents an efficient inter-procedural data flow analysis algorithm for precisely determining aliases in programs that employ a rich set of parameter passing mechanisms and pointer data types. This approach handles the use of pointers bounded to a data type as in Pascal, as well as unbounded pointers that can point to the same locations to which variables map. In the last step of this approach, the alias information is used to compute data flow information that is required for optimization.

References

[1]

Rudmik, A. and B.G. Moore, "The CHILL Compiling System: Towards a CHILL Programming Environment," Proc. Fourth Int. Conf. Software Engr. for Telecommunication Switching Systems (1981), 187-190.

Google Scholar

[2]

Spillman, T.C., "Exposing Side-Effects in a PL/I Optimizing Compiler," Proceedings IFIP Conference 1971, North Holland Publishing Co., Amsterdam, 376-381.

Google Scholar

[3]

Allen, F.E., "Interprocedural Data Flow Analysis," Proceedings IFIP Congress 74, North Holland Publishing Company, Amsterdam, 398-402.

Google Scholar

[4]

Allen, F.E. and J.T. Schwartz, "Determining the Data Relationships in a Collection of Procedures," Computer Science Report RC 4989, IBM Thomas J. Watson Research Center, (1974).

Google Scholar

[5]

Rosen, B.K., "Data Flow Analysis for PL/I Programs," Computer Science Report RC 5211, IBM Thomas J. Watson Research Center, Yorktown Heights (1975).

Google Scholar

[6]

Lomet, D.B., "Data Flow Analysis in the Presence of Procedure Calls," IBM Journal of Research and Development 21, 5 (1977), 559-571.

Digital Library

Google Scholar

[7]

Barth, J., "An Interprocedural Data Flow Analysis Algorithm," Conf. Rec. Fourth ACM Symposium on Principles of Programming Languages, (1977), 119-131.

Digital Library

Google Scholar

[8]

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

Google Scholar

[9]

Weihl, W.E., "Interprocedural Data Flow Analysis in the Presence of Pointers, Procedure Variables, and Label Variables," Research Report RC8060, IBM T. J. Watson Research Center, Yorktown Heights, New York, January, 1980.

Google Scholar

[10]

Lepage, M.T., D.T. Barnard and A. Rudmik, "Optimization of Hierarchical Directed Graphs," Computer Languages 6 (1981), 19-34.

Digital Library

Google Scholar

[11]

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

Digital Library

Google Scholar

[12]

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

Digital Library

Google Scholar

[13]

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

Digital Library

Google Scholar

Cited By

View all

Goharshady AZaher A(2023)Efficient Interprocedural Data-Flow Analysis Using Treedepth and TreewidthVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-24950-1_9(177-202)Online publication date: 17-Jan-2023
https://doi.org/10.1007/978-3-031-24950-1_9
Johnson H(2019)Data flow analysis for `intractable' system softwareACM SIGPLAN Notices10.1145/13310.1332221:7(109-117)Online publication date: 28-Jun-2019
https://dl.acm.org/doi/10.1145/13310.13322
Johnson H(1986)Data flow analysis for `intractable' system softwareProceedings of the 1986 SIGPLAN symposium on Compiler construction10.1145/12276.13322(109-117)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1145/12276.13322
Show More Cited By

Index Terms

The design of a data flow analyzer
1. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

The design of a data flow analyzer
SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction

This paper presents an efficient inter-procedural data flow analysis algorithm for precisely determining aliases in programs that employ a rich set of parameter passing mechanisms and pointer data types. This approach handles the use of pointers bounded ...
A demand-driven analyzer for data flow testing at the integration level
ICSE '96: Proceedings of the 18th international conference on Software engineering

Data-flow testing relies on static analysis for computing the definition-use pairs that serve as the test case requirements for a program. When testing large programs, the individual procedures are first tested in isolation during unit testing. ...
Context-, flow-, and field-sensitive data-flow analysis using synchronized Pushdown systems

Precise static analyses are context-, field- and flow-sensitive. Context- and field-sensitivity are both expressible as context-free language (CFL) reachability problems. Solving both CFL problems along the same data-flow path is undecidable, which is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 17, Issue 6

Proceedings of the 1982 SIGPLAN symposium on Compiler construction

June 1982

347 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/872726

Issue’s Table of Contents

SIGPLAN '82: Proceedings of the 1982 SIGPLAN symposium on Compiler construction
June 1982
357 pages
ISBN:0897910745
DOI:10.1145/800230
Chairmen:
John R. White,
Frances E. Allen

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1982

Published in SIGPLAN Volume 17, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
439
Total Downloads

Downloads (Last 12 months)76
Downloads (Last 6 weeks)16

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Goharshady AZaher A(2023)Efficient Interprocedural Data-Flow Analysis Using Treedepth and TreewidthVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-24950-1_9(177-202)Online publication date: 17-Jan-2023
https://doi.org/10.1007/978-3-031-24950-1_9
Johnson H(2019)Data flow analysis for `intractable' system softwareACM SIGPLAN Notices10.1145/13310.1332221:7(109-117)Online publication date: 28-Jun-2019
https://dl.acm.org/doi/10.1145/13310.13322
Johnson H(1986)Data flow analysis for `intractable' system softwareProceedings of the 1986 SIGPLAN symposium on Compiler construction10.1145/12276.13322(109-117)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1145/12276.13322
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
Ruf E(1995)Context-insensitive alias analysis reconsideredACM SIGPLAN Notices10.1145/223428.20711230:6(13-22)Online publication date: 1-Jun-1995
https://dl.acm.org/doi/10.1145/223428.207112
Ruf EWall D(1995)Context-insensitive alias analysis reconsideredProceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation10.1145/207110.207112(13-22)Online publication date: 18-Jun-1995
https://dl.acm.org/doi/10.1145/207110.207112
Pande HLandi WRyder B(1994)Interprocedural Def-Use Associations for C Systems with Single Level PointersIEEE Transactions on Software Engineering10.1109/32.28641820:5(385-403)Online publication date: 1-May-1994
https://dl.acm.org/doi/10.1109/32.286418
Landi WRyder B(1992)A safe approximate algorithm for interprocedural aliasingACM SIGPLAN Notices10.1145/143103.14313727:7(235-248)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/143103.143137
Landi WRyder BFeldman S(1992)A safe approximate algorithm for interprocedural aliasingProceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation10.1145/143095.143137(235-248)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.1145/143095.143137
Landi WRyder BWise D(1991)Pointer-induced aliasing: a problem classificationProceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/99583.99599(93-103)Online publication date: 3-Jan-1991
https://dl.acm.org/doi/10.1145/99583.99599
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.

Abstract

References

Cited By

Index Terms

Recommendations