A new, simpler linear-time dominators algorithm

ABSTRACT

We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data structures, we combine the use of microtrees and memoization with new observations on a restricted class of path compressions. We have implemented our algorithm, and we report experimental results that show that the constant factors are low. Compared to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flowgraphs of reasonable size and only a few percent slower on very large flowgraphs.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 3: ALSTRUP, S., HAREL, D., LAURIDSEN, P. W., AND THORUP, M. 1997. Dominators in linear time. Manuscript available at ftp ://ftp. diku. dk/pub/diku/users/stephen/dom, ps.
• 4: AMARASINGHE, S. P., ANDERSON, J. M., LAM, M. S., AND TSENG, C. W. 1995. The SUIF compiler for scalable parallel machines. In Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Philadelphia, Pa.
• 5: Andrew W. Appel, Modern compiler implementation in Java, Cambridge University Press, New York, NY, 1997
• 6: Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.279-288, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276764]
• 7: Adam L. Buchsbaum , Rajamani Sundar , Robert E. Tarjan, Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues, SIAM Journal on Computing, v.24 n.6, p.1190-1206, Dec. 1995 [doi>10.1137/S0097539792242144]
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: 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]
• 10: DIXON, B. AND TARJAN, R. E. 1997. Optimal parallel verification of minimum spanning trees in logarithmic time. Algorithmiea 17, 11-8.
• 11: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 12: Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
• 13: GABOW, H. N. AND TARJAN, R. E. 1985. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sei. 30, 2, 209-21.
• 14: 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]
• 15: HOLLOWAY, G. AND YOUNG, C. 1997. The flow analysis and transformation libraries of Machine SUIF. In Proceedings of the 2rid SUIF Compiler Workshop. Stanford University, Stanford, Calif.
• 16: 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]
• 17: Martin Loebl , Jaroslav Nešetřil, Linearity and unprovability of set union problem strategies I: linearity of strong postorder, Journal of Algorithms, v.23 n.2, p.207-220, May. 1997 [doi>10.1006/jagm.1996.0815]
• 18: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 19: Joan M. Lucas, Postorder disjoint set union is linear, SIAM Journal on Computing, v.19 n.5, p.868-882, Oct. 1990 [doi>10.1137/0219060]
• 20: PEREIRA, F. AND RILEY, M. 1997. Speech recognition by composition of weighted finite automata. In Finite-State Language Processing. MIT Press, Cambridge, Mass.
• 21: Fernando Pereira , Michael Riley , Richard Sproat, Weighted rational transductions and their application to human language processing, Proceedings of the workshop on Human Language Technology, March 08-11, 1994, Plainsboro, NJ [doi>10.3115/1075812.1075870]
• 22: 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]
• 23: Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972 [doi>10.1145/361532.361566]
• 24: SPEC. 1995. The SPEC95 Benchmark Suite. The Standard Performance Evaluation Corp., Manassas, Va. http ://www. specbench, org.
• 25: TARJAN, R. E. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2, 146-59.
• 26: TARJAN, R. E. 1974. Finding dominators in directed graphs. SIAM J. Comput. 3, 1, 62-89.
• 27: 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]
• 28: TARJAN, R. E. 1979b. A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. Syst. Sci. 18, 2, 110-27.
• 29: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]

INDEX TERMS

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

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

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

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

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
compilers, dominators, flowgraphs, microtrees, path compression