An incremental algorithm for maintaining the dominator tree of a reducible flowgraph

ABSTRACT

We present a new incremental algorithm for the problem of maintaining the dominator tree of a reducible flowgraph as the flowgraph undergoes changes such as the insertion and deletion of edges. Such an algorithm has applications in incremental dataflow analysis and incremental compilation.

REFERENCES

• Aho86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Alp90: Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
• Car88: M. D. Carroll , B. G. Ryder, Incremental data flow analysis via dominator and attribute update, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.274-284, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73584]
• Car88a: Martin Donald Carroll , Barbara Ryder, Data flow update via dominator and attribute updates, 1988
• Coh92a: Robert F. Cohen, Combine and conquer, Brown University, Providence, RI, 1992
• Coh92: Robert F. Cohen , Roberto Tamassia, Combine and Conquer, Brown University, Providence, RI, 1992
• Cyt89: 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]
• Cyt91: 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]
• Har85: 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]
• Len79: 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]
• Och83: Renata Ochranová, Finding Dominators, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.328-334, August 21-27, 1983
• Rep82: Thomas Reps, Optimal-time incremental semantic analysis for syntax-directed editors, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.169-176, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582172]
• Rep83: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• Sle83: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory