A practical interprocedural dominance algorithm

ABSTRACT

Existing algorithms for computing dominators are formulated for control flow graphs of single procedures. With the rise of computing power, and the viability of whole-program analyses and optimizations, there is a growing need to extend the dominator computation algorithms to context-sensitive interprocedural dominators. Because the transitive reduction of the interprocedural dominator graph is not a tree, as in the intraprocedural case, it is not possible to extend existing algorithms directly. In this article, we propose a new algorithm for computing interprocedural dominators. Although the theoretical complexity of this new algorithm is as high as that of a straightforward iterative solution of the data flow equations, our experimental evaluation demonstrates that the algorithm is practically viable, even for programs consisting of several hundred thousands of basic blocks.

REFERENCES

• 1: Hira Agrawal, Efficient coverage testing using global dominator graphs, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.11-20, September 06-06, 1999, Toulouse, France
• 2: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 3: Frances E. Allen, Control flow analysis, Proceedings of a symposium on Compiler optimization, p.1-19, July 27-28, 1970, Urbana-Champaign, Illinois
• 4: Allen, F. E. and Cocke, J. 1972. Graph-theoretic constructs for program control flow analysis. Tech. Rep. RC 3923, IBM T.J. Watson Research Center.
• 5: 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]
• 6: Dominique Chanet , Bjorn De Sutter , Bruno De Bus , Ludo Van Put , Koen De Bosschere, Automated reduction of the memory footprint of the Linux kernel, ACM Transactions on Embedded Computing Systems (TECS), v.6 n.4, p.23-es, September 2007 [doi>10.1145/1274858.1274861]
• 7: Cooper, K. D., Harvey, T. J., and Kennedy, K. 2001. A simple, fast dominance algorithm. Available on-line at: http://www.hipersoft.rice.edu/grads/publications/dom14.pdf.
• 8: 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]
• 9: Bruno De Bus , Bjorn De Sutter , Ludo Van Put , Dominique Chanet , Koen De Bosschere, Link-time optimization of ARM binaries, ACM SIGPLAN Notices, v.39 n.7, July 2004
• 10: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Link-time binary rewriting techniques for program compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.882-945, September 2005 [doi>10.1145/1086642.1086645]
• 11: Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 12: Georgiadis, L., Werneck, R., Tarjan, R., Triantafyllis, S., and August, D. 2004. Finding dominators in practice. Lecture Notes in Computer Science 3221, 677--688.
• 13: 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]
• 14: 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]
• 15: 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]
• 16: Robert Muth , Saumya K. Debray , Scott Watterson , Koen De Bosschere, Alto: a link-time optimizer for the Compaq alpha, Software—Practice & Experience, v.31 n.1, p.67-101, Jan. 2001 [doi>10.1002/1097-024X(200101)31:1<67::AID-SPE357>3.0.CO;2-A]
• 17: Prosser, R. T. 1959. Applications of Boolean matrices to the analysis of flow diagrams. In Proceedings of the Eastern Joint Computer Conference. Spartan Books, New York, 133--138.
• 18: 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]
• 19: On loops, dominators, and dominance frontiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.5, p.455-490, September 2002 [doi>10.1145/570886.570887]
• 20: Spyridon Triantafyllis , Matthew J. Bridges , Easwaran Raman , Guilherme Ottoni , David I. August, A framework for unrestricted whole-program optimization, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 21: David W. Wall, Global register allocation at link time, Proceedings of the 1986 SIGPLAN symposium on Compiler construction, p.264-275, June 25-27, 1986, Palo Alto, California, United States

INDEX TERMS

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

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

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Graph algorithms

General Terms:
Algorithms, Languages

Keywords:
Interprocedural control flow graph, dominators, interprocedural analysis