Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This article explores the concept of loops and loop nesting forests of control-flow graphs, using the problem of constructing the dominator tree of a graph and the problem of computing the iterated dominance frontier of a set of vertices in a graph as guiding applications. The contributions of this article include: (1) An axiomatic characterization, as well as a constructive characterization, of a family of loop nesting forests that includes various specific loop nesting forests that have been previously defined. (2) The definition of a new loop nesting forest, as well as an efficient, almost linear-time, algorithm for constructing this forest. (3) An illustration of how loop nesting forests can be used to transform arbitrary (potentially irreducible) problem instances into equivalent acylic graph problem instances in the case of the two problems of (a) constructing the dominator tree of a graph, and (b) computing the iterated dominance frontier of a set of vertices in a graph, leading to new, almost linear-time, algorithms for these problems.

REFERENCES

• 1: Stephen Alstrup , Dov Harel , Peter W. Lauridsen , Mikkel Thorup, Dominators in Linear Time, SIAM Journal on Computing, v.28 n.6, p.2117-2132, Dec. 1999 [doi>10.1137/S0097539797317263]
• 2: Alstrup, S., Lauridsen, P. W., and Thorup, M. 1996. Dominators in linear time. Tech. Rep. 96/35, Department of Computer Science, Univ. Copenhagen, Copenhagen, Denmark.
• 3: Alstrup, S. and Lauridsen, P. W. 1996. A simple and optimal algorithm for finding immediate dominators in reducible graphs. Tech. Rep. D-261/96, TOPPS Bibliography.
• 4: Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998 [doi>10.1145/295656.295663]
• 5: 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]
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: 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]
• 8: 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]
• 9: Harold N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 22-24, 1990, San Francisco, California, United States
• 10: 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]
• 11: Paul Havlak, Nesting of reducible and irreducible loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.4, p.557-567, July 1997 [doi>10.1145/262004.262005]
• 12: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 13: K. Mehlhorn , A. Tsakalidis, Data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 14: Robert Morgan, Building an optimizing compiler, Digital Press, Newton, MA, 1998
• 15: Keshav Pingali , Gianfranco Bilardi, Optimal control dependence computation and the Roman chariots problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.462-491, May 1997 [doi>10.1145/256167.256217]
• 16: G. Ramalingam, Identifying loops in almost linear time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.175-188, March 1999 [doi>10.1145/316686.316687]
• 17: G. Ramalingam , Thomas Reps, An incremental algorithm for maintaining the dominator tree of a reducible flowgraph, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.287-296, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177905]
• 18: John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512961]
• 19: Vugranam C. Sreedhar, Efficient program analysis using DJ graphs, McGill University, Montreal, Que., Canada, 1996
• 20: Vugranam C. Sreedhar , Guang R. Gao, A linear time algorithm for placing &phgr;-nodes, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.62-73, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199464]
• 21: Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, Identifying loops using DJ graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.6, p.649-658, Nov. 1996 [doi>10.1145/236114.236115]
• 22: Steensgaard, B. 1993. Sequentializing program dependence graphs for irreducible programs. Tech. Rep. MSR-TR-93-14, Microsoft Research, Redmond, Wash.
• 23: Tarjan, R. E. 1974. Testing flow graph reducibility. J. Comput. Syst. Sci. 9, 355--365.
• 24: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
• 25: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 26: 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]

INDEX TERMS

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Incremental compilers; Interpreters; Optimization; Compilers

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks; Trees

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Graph algorithms

General Terms:
Algorithms, Languages, Theory, Verification

Keywords:
Dominator, graph transformation, irreducible graph, iterated dominance frontier, least common ancestor, loop, loop nesting forest, sparse evaluation