Article

Free access

A linear time algorithm for placing φ-nodes

Authors:

Vugranam C. Sreedhar,

Guang R. GaoAuthors Info & Claims

POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 62 - 73

https://doi.org/10.1145/199448.199464

Published: 25 January 1995 Publication History

Abstract

Dataflow analysis framework based on Static Single Assignment (SSA) form and Sparse Evaluation Graphs (SEGs) demand fast computation of program points where data flow information must be merged, the so-called φ-nodes. In this paper, we present a surprisingly simple algorithm for computing φ-nodes for arbitrary flowgraphs (reducible or irreducible) that runs in linear time. We employ a novel program representation—the DJ graph—by augmenting the dominator tree of a flowgraph with edges which may lead to a potential “merge” of dataflow information. In searching for φ-nodes we never visit an edge in the DJ-graph more than once by guiding the search of nodes by their levels in the dominator tree.

The algorithm has been implemented and the results are compared with the well known algorithm due to Cytron et al. A consistent and significant speedup has been observed over a range of 46 Fortran procedures taken from a number of benchmark programs. We also ran experiments on increasingly taller ladder graphs and confirmed the linear time complexity of our algorithm.

References

[1]

Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equality of variables in programs. In Conference Record of the 15th Annual A CM Symposium on Principles of Programming Languages, pages 1-11,1988.

Digital Library

[2]

Robert A. Ballance, Arthur B. Maccabe, and Karl J. Ottenstein. The program dependence web: A representation supporting control-, and demand-driven interpretation of imperative languages. In Proceedings of the SIGPLAN'90 Conference on Programming Language Design and Implementation, pages 257-271,1990.

Digital Library

[3]

Preston Briggs. Register Allocation via Graph Coloring. PhD thesis, Rice University, Houston, Texas, April 1992.

Digital Library

[4]

Jong-Deok Choi, Ron Cytron, and Jeanne Ferrante. Automatic construction of sparse data flow evaluation graphs. In Conference Record of the 18th Annual ACM Symposium on Principles of Programming Languages, 1991.

Digital Library

[5]

Ron Cytron and Jeanne Ferrante. What's in a name? or the value of renaming for parallelism detection and storage allocation. In Proceedings of the 1987 International Conference on Parallel Processing, pages 19-27, St. Charles, Illinois, August 17-21,1987.

[6]

Ron Cytron and Jeanne Ferrante. Efficiently computing #-nodes on-the-fly. In Languagesand Compilers for Parallel Computing, 1993.

Digital Library

[7]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and Fo Kenneth Zadeck. An efficient method for computing static singleassignment form. In Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, pages 25-35, Austin, Texas, January 11-13, 1989. ACM SIGACT and SIGPLAN.

Digital Library

[8]

Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignemnt form and control dependence graph.ACM Transactions on Programming Languages and Systems, 13(4):452- 490, October 1991.

Digital Library

[9]

Ron Cytron, Jeanne Ferrante, and Vivek Sarkar. Compact representations for control dependence. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation, pages 337-351, White Plains, New York, June 20-22,1990. ACM SIGPLAN. Also in SIGPLAN Notices, 25(6), June 1990.

Digital Library

[10]

Ron Cytron, Andy Lowry, and Kenneth Zadeck. Code motion of control structures in high-level languages. In Conference Record of the Thirteenth Annual ACM Symposium on Principles of Programming Languages, pages 70-85, St. Petersburg Beach, Florida, January 13-15, 1986. ACM SIGACT and SIGPLAN.

Digital Library

[11]

Dov Harel. A linear time algorithm for finding dominators in flow graphs and related problems. In Symposium on Theory of Computing. ACM, May 1985.

Digital Library

[12]

William Harrison. An overview of the structure of Parafrase. Technical Report 501, PR-85-2 UILU-ENG-85-8002, UIUC, July 1985.

[13]

R. Johnson and K. Pingali. Dependence-based program ananlysis. In Proceedings of the SIG- PLAN'93 Conference on Programming Language Design and Implementation, pages 78-89,1993.

Digital Library

[14]

R. Johnson, D. Pearson, and K. Pingali. The program tree structure: Computing control regions in linear time. In Proceedings of the SIGPLAN'94 Conference on Programming Language Design and Implementation, pages 171-185,1994.

Digital Library

[15]

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

[16]

Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Global value numbers and redundant computations. In Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages, pages 12-27, San Diego, California, january 13-15, 1988. ACM SIGACT and SIGPLAN.

Digital Library

[17]

Vugranam C. Sreedhar and Guang R. Gao. Computing #b-nodes in linear time using DJ-graphs. Technical Report ACAPS Memo 75, School of Computer Science, McGill University, january 1994. Submitted for publication.

[18]

Vugranam C. Sreedhar, Guang R. Gao, and Yongfong Lee. DJ-graphs and their applications to flowgraph analyses. Technical Report ACAPS Memo 70, McGill University, May 1994. Submitted for publication.

[19]

Vugranam C. Sreedhar, Guang R. Gao, and Yongfong Lee. An efficient incremental algorithm for maintaining dominator trees and its application to C-nodes update. Technical Report ACAPS Memo 77, McGill University, July 1994. Submitted for publication.

[20]

R.M. Shapiro and H. Saint. The representation of algorithm. Technical Report CA-7002-1432, MCA, 1970.

[21]

Daniel Weise, Roger F. Crew, Michael Ernst, and Bjarne Steensgaard. Value dependence graphs: Representation without taxation. In Conference Record of the 21st Annual ACM Symposium on Principles of Programming Languages, 1994.

Digital Library

[22]

Michael Weiss. The transitive closure of control dependence: the iterated join. ACM Letters on Programming Languages and Systems, 1(2), June 1992.

Digital Library

[23]

Michael Wolfe. Beyond induction variables. In Proceedings of the SIGPLAN'92 Conference on Programming Language Design and Implementation, pages 161-174,1992.

Digital Library

[24]

Mark Wegman and Ken Zadeck. Constant propagation with conditional branches. In Conference Record of the Twelfth Annual ACM Symposium on Principles of Programming Languages, pages 291- 299. ACM SIGACT and SIGPLAN, January 1985.

Digital Library

Cited By

Umann KHorváth GPorkoláb Z(2024)Uncovering Hidden Dependencies: Constructing Intelligible Path Witnesses using Dataflow AnalysesActa Cybernetica10.14232/actacyb.29980526:3(713-747)Online publication date: 4-Mar-2024
https://doi.org/10.14232/actacyb.299805
Lesbre DLemerre M(2024)Compiling with Abstract InterpretationProceedings of the ACM on Programming Languages10.1145/36563928:PLDI(368-393)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656392
Lu KLow DTomb A(2023)Constructing Structured SSA from FJProceedings of the 25th ACM International Workshop on Formal Techniques for Java-like Programs10.1145/3605156.3606457(58-64)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3605156.3606457
Show More Cited By

Index Terms

A linear time algorithm for placing φ-nodes
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Flowcharts
  2. Software notations and tools
    1. Compilers
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Randomness, geometry and discrete structures

Recommendations

A linear-time algorithm for semitotal domination in strongly chordal graphs
Abstract
In a graph, G = ( V , E ) without an isolated vertex, a dominating set D ⊆ V, is called a semitotal dominating set if for every vertex u ∈ D there is another vertex v ∈ D such that distance between u and v is at most two in G. Given a graph G = ( ...
A linear time algorithm for liar's domination problem in proper interval graphs

Let G=(V,E) be a graph without isolated vertices and having at least 3 vertices. A set L@?V(G) is a liar@?s dominating set if (1) |N"G[v]@?L|>=2 for all v@?V(G), and (2) |(N"G[u]@?N"G[v])@?L|>=3 for every pair u,v@?V(G) of distinct vertices in G, where ...
A linear-time algorithm for clique-coloring planar graphs
Abstract
A clique of a graph G is a set of pairwise adjacent vertices of G. A clique-coloring of G is an assignment of colors to the vertices of G such that no inclusion-wise maximal clique of size at least 2 is monochromatic. Mohar and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 1995

415 pages

ISBN:0897916921

DOI:10.1145/199448

Chairmen:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Peter Lee
Carnegie Mellon Univ., Pittsburgh, PA

Copyright © 1995 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: 25 January 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL95

Sponsor:

POPL95: 22nd ACM Symposium on Principles of Programming Languages

January 23 - 25, 1995

California, San Francisco, USA

Acceptance Rates

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

73
Total Citations
View Citations
1,604
Total Downloads

Downloads (Last 12 months)352
Downloads (Last 6 weeks)22

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Umann KHorváth GPorkoláb Z(2024)Uncovering Hidden Dependencies: Constructing Intelligible Path Witnesses using Dataflow AnalysesActa Cybernetica10.14232/actacyb.29980526:3(713-747)Online publication date: 4-Mar-2024
https://doi.org/10.14232/actacyb.299805
Lesbre DLemerre M(2024)Compiling with Abstract InterpretationProceedings of the ACM on Programming Languages10.1145/36563928:PLDI(368-393)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656392
Lu KLow DTomb A(2023)Constructing Structured SSA from FJProceedings of the 25th ACM International Workshop on Formal Techniques for Java-like Programs10.1145/3605156.3606457(58-64)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3605156.3606457
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
Subotić PBojanić UStojić MGonnord LTitolo L(2022)Statically detecting data leakages in data science codeProceedings of the 11th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis10.1145/3520313.3534657(16-22)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3520313.3534657
Guimarães BMagalhães Jda Silva APereira F(2019)Synthesis of Benchmarks for the C Programming Language by Mining Software RepositoriesProceedings of the XXIII Brazilian Symposium on Programming Languages10.1145/3355378.3355380(62-69)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1145/3355378.3355380
Masud ACiccozzi F(2019)Towards Constructing the SSA form using Reaching Definitions Over Dominance Frontiers2019 19th International Working Conference on Source Code Analysis and Manipulation (SCAM)10.1109/SCAM.2019.00012(23-33)Online publication date: Sep-2019
https://doi.org/10.1109/SCAM.2019.00012
Ben-Nun TJakobovits AHoefler T(2018)Neural code comprehensionProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327144.3327276(3589-3601)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327144.3327276
Chen QWan YZhang XLei YZobel JVerspoor K(2018)Comparative Analysis of Sequence Clustering Methods for Deduplication of Biological DatabasesJournal of Data and Information Quality10.1145/31316119:3(1-27)Online publication date: 27-Jan-2018
https://dl.acm.org/doi/10.1145/3131611
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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