Article

Free access

Automatic construction of sparse data flow evaluation graphs

Authors:

Jong-Deok Choi,

Ron Cytron,

Jeanne FerranteAuthors Info & Claims

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

Pages 55 - 66

https://doi.org/10.1145/99583.99594

Published: 03 January 1991 Publication History

PDF eReader

References

[1]

A.V. Aho, R. Sethi, and J.D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.

Digital Library

Google Scholar

[2]

Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equality of variables in programs. Fifteenth A CM Principles of Programming Languages Symposium, 1-11, January 1988. San Diego, CA.

Digital Library

Google Scholar

[3]

Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. On the efficient treatment of preserving definitions. In preparation.

Google Scholar

[4]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. An efficient method for computing static single assignment form. Sixteenth Annual A CM Symposium on Principles of Programming Languages, 25-35, January 1989.

Digital Library

Google Scholar

[5]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. Submitted to A CM Transactions on Programming Languages and Sysgems, June 1989.

Digital Library

Google Scholar

[6]

Ron Cytron, Andy Lowry, and Ken Zadeck. Code motion of control structures in highlevel languages. Conf. Rec. of ihe A CM Syrup. on Principles of Compiler Construction, 1986.

Digital Library

Google Scholar

[7]

J. Ferrante, K. Ottenstein, and J. Warren. The program dependence graph and its use in optimization. A CM Transactions on Programming Languages and Systems, 319- 349, July 1987.

Digital Library

Google Scholar

[8]

Matthew S. Hecht. Flow Analysis of Computer Programs. Elsevier North-Holland, Inc., 1977.

Digital Library

Google Scholar

[9]

Ken Kennedy. A survey of data flow analysis techniques. Program Flow Analysis: Theory and Applications, 1981.

Google Scholar

[10]

G. Kildall. A unified approach to global program optimization. Conference Record of Firs~ A CM Symposium on Principles of Programming Languages, 194-206, January 1973.

Digital Library

Google Scholar

[11]

T. Lengauer and Robert Tarjan. A fast algorithm for finding dominators in a flowgraph. TOPLAS, July 1979.

Digital Library

Google Scholar

[12]

Thomas J. Marlowe. Data Flow Analysis and Incremental Iteration. PhD thesis, Rutgers University, October 1989.

Digital Library

Google Scholar

[13]

J.H. Reif and H. R. Lewis. Symbolic evaluation and the global value graph. Conf. Rec. Fourfh A CM Symposium on Principles of Programming Languages, 1977.

Digital Library

Google Scholar

[14]

Barry K. Rosen. Data flow analysis for procedural languages. JACM, 26(2):322- 344, April 1979.

Digital Library

Google Scholar

[15]

Barry K. Rosen. Degrees of availability as an introduction to the general theory of data flow analysis. Program Flow Analysis: Theory and Applications, 1981.

Google Scholar

[16]

j.H. Reif and Robert Tarjan. Symbohc program analysis in almost linear time. SIAM Journal of Computing, 11(1):81-93, February 1982.

Crossref

Google Scholar

[17]

Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Global value numbers and redundant computations. Fifteenth A CM Principles of Programming Languages Symposium, 12-27, January 1988. San Diego, CA.

Digital Library

Google Scholar

[18]

Robert Tarjan. Fast algorithms for solving path problems. Journal of the Association for Computing Machinery, 28(3):594-614, 1981.

Digital Library

Google Scholar

[19]

Mark Wegman and Ken Zadeck. Constant propagation with conditional branches. Conf. Rec. Twelfth A CM Symposium on Principles of Programming Languages, 291- 299, january 1985.

Digital Library

Google Scholar

[20]

Wuu Yang, Susan Horwitz, and Thomas Reps. De~ec~ing Program Components With Equivalen~ Behaviors. Technical Report, University of Wisconsin, Madison, April 1989. Computer Sciences Technical Report Number 840.

Google Scholar

[21]

Frank Kenneth Zadeck. Incremental data flow analysis in a structured program editor. Proceedings o/ lhe SIGPLAN '84 Symposium on Compiler Conslruclion, 19(6):132- 143, June 1984.

Digital Library

Google Scholar

Cited By

View all

OBrien DDyer RNguyen TRajan HRoychoudhury APaiva AAbreu RStorey M(2024)Data-Driven Evidence-Based Syntactic Sugar DesignProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639580(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639580
Karakaya KBodden ERoychoudhury APaiva AAbreu RStorey M(2024)Symbol-Specific Sparsification of Interprocedural Distributive Environment ProblemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639092(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639092
Sun ZXu DZhang YQi YWang YZuo ZWang ZLi YLi XLu QPeng WGuo SChandra SBlincoe KTonella P(2023)BigDataflow: A Distributed Interprocedural Dataflow Analysis FrameworkProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616348(1431-1443)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616348
Show More Cited By

Index Terms

Automatic construction of sparse data flow evaluation graphs

Recommendations

Sparse Kneser graphs are Hamiltonian
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,…,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. ...
Acyclic edge coloring of sparse graphs

Let Δ denote the maximum degree of a graph. Fiamčík first, Alon, Sudakov and Zaks later conjectured that every graph is acyclically edge ( Δ + 2 ) -colorable. In this paper, we prove this conjecture for graphs with maximum average degree less than 4. As ...
k-forested choosability of planar graphs and sparse graphs

A proper vertex coloring of a simple graph G is k-forested if the subgraph induced by the vertices of any two color classes is a k-forest, i.e. a forest with maximum degree at most k. The 2-forested coloring is also known as linear coloring, which has ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

January 1991

366 pages

ISBN:0897914198

DOI:10.1145/99583

Chairman:
David Wise
Indiana Univ., Bloomington

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: 03 January 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL91

Sponsor:

POPL91: 18th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages

January 21 - 23, 1991

Florida, Orlando, USA

Acceptance Rates

POPL '91 Paper Acceptance Rate 31 of 152 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

150
Total Citations
View Citations
1,346
Total Downloads

Downloads (Last 12 months)152
Downloads (Last 6 weeks)21

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

OBrien DDyer RNguyen TRajan HRoychoudhury APaiva AAbreu RStorey M(2024)Data-Driven Evidence-Based Syntactic Sugar DesignProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639580(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639580
Karakaya KBodden ERoychoudhury APaiva AAbreu RStorey M(2024)Symbol-Specific Sparsification of Interprocedural Distributive Environment ProblemsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639092(1-12)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3639092
Sun ZXu DZhang YQi YWang YZuo ZWang ZLi YLi XLu QPeng WGuo SChandra SBlincoe KTonella P(2023)BigDataflow: A Distributed Interprocedural Dataflow Analysis FrameworkProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616348(1431-1443)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616348
Lemerre M(2023)SSA Translation Is an Abstract InterpretationProceedings of the ACM on Programming Languages10.1145/35712587:POPL(1895-1924)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571258
Masud A(2023)The Duality in Computing SSA Programs and Control DependencyIEEE Transactions on Software Engineering10.1109/TSE.2022.319224949:4(1766-1781)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TSE.2022.3192249
Karakaya KBodden E(2023)Two Sparsification Strategies for Accelerating Demand-Driven Pointer Analysis2023 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST57152.2023.00036(305-316)Online publication date: Apr-2023
https://doi.org/10.1109/ICST57152.2023.00036
Zhang RBond MZhang YEgger BSmith A(2022)Cape: compiler-aided program transformation for HTM-based cache side-channel defenseProceedings of the 31st ACM SIGPLAN International Conference on Compiler Construction10.1145/3497776.3517778(181-193)Online publication date: 19-Mar-2022
https://dl.acm.org/doi/10.1145/3497776.3517778
Shi QYao PWu RZhang CFreund SYahav E(2021)Path-sensitive sparse analysis without path conditionsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454086(930-943)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454086
Zuo ZZhang YPan QLu SLi YWang LLi XXu GFreund SYahav E(2021)Chianina: an evolving graph system for flow- and context-sensitive analyses of million lines of C codeProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454085(914-929)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454085
Barbar MSui YChen SLee J(2021)Object versioning for flow-sensitive pointer analysisProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370334(222-235)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370334
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Sparse Kneser graphs are Hamiltonian

Acyclic edge coloring of sparse graphs

k-forested choosability of planar graphs and sparse graphs