A linear time algorithm for placing &phgr;-nodes

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 &fgr;-nodes. In this paper, we present a surprisingly simple algorithm for computing &fgr;-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 &fgr;-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

• AWZ88: B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
• BMO90: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• Bri92: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• CCF91: Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99594]
• CF87: 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.
• CF93: Ron Cytron , Jeanne Ferrante, Efficiently Computing phi-Nodes On-The-Fly (Extended Abstract), Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.461-476, August 12-14, 1993
• CFR+89: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• CFR+91: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• CFS90: Ron Cytron , Jeanne Ferrante , V. Sarkar, Compact representations for control dependence, ACM SIGPLAN Notices, v.25 n.6, p.337-351, Jun. 1990
• CLZ86: Ron Cytron , Andy Lowry , F. Kenneth Zadeck, Code motion of control structures in high-level languages, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.70-85, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512651]
• Har85a: D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22166]
• Har85b: William Harrison. An overview of the structure of Parafrase. Technical Report 501, PR-85-2 UILU-ENG-85-8002, UIUC, July 1985.
• JP93: Richard Johnson , Keshav Pingali, Dependence-based program analysis, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.78-89, June 21-25, 1993, Albuquerque, New Mexico, United States
• JPP94: Richard Johnson , David Pearson , Keshav Pingali, The program structure tree: computing control regions in linear time, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.171-185, June 20-24, 1994, Orlando, Florida, United States
• RT82: J.H. Reif and Robert Tarjan. Symbolic program analysis in almost linear time. SIAM Journal of Computing, 11(1):81-93, February 1982.
• RWZ88: B. K. Rosen , M. N. Wegman , F. K. Zadeck, Global value numbers and redundant computations, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-27, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73562]
• SG94: 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.
• SGL94a: 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.
• SGL94b: 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.
• SS70: R.M. Shapiro and H. Saint. The representation of algorithm. Technical Report CA-7002-1432, MCA, 1970.
• WCES94: Daniel Weise , Roger F. Crew , Michael Ernst , Bjarne Steensgaard, Value dependence graphs: representation without taxation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.297-310, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177907]
• Wei92: Michael Weiss, The transitive closure of control dependence: the iterated join, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.2, p.178-190, June 1992 [doi>10.1145/151333.151337]
• Wol92: Michael Wolfe, Beyond induction variables, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.162-174, June 15-19, 1992, San Francisco, California, United States
• WZ85: Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Flow charts

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Experimentation, Performance, Theory