Identifying loops using DJ graphs

ABSTRACT

Loop identification is a necessary step in loop transformations for high-performance architectures. One classical technique for detecting loops is Tarjan's interval-finding algorithm. The intervals identified by Tarjan's method are single-entry, strongly connected subgraphs that closely reflect a program's loop structure. We present a simple algorithm for identifying both reducible and irreducible loops using DJ graphs. Our method is a generalization of Tarjan's method, as it identifies nested intervals (or loops) even in the presence of irreducibility.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• 3: M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
• 4: Vugranam C. Sreedhar, Efficient program analysis using DJ graphs, McGill University, Montreal, Que., Canada, 1996
• 5: 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]
• 6: Vugranam C. Sreedhar , Guang R. Gao , Yong-fong Lee, Incremental computation of dominator trees, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.1-12, January 23-25, 1995, San Francisco, California, United States
• 7: Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, A new framework for exhaustive and incremental data flow analysis using DJ graphs, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.278-290, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 8: STEENSGARD, B. 1993. Sequentializing program dependence graphs for irreducible programs. Tech. Rep. MSR-TR-93-14, Microsoft Research. Oct.
• 9: TARJAN, R. E. 1974. Testing flow graph reducibility. J Comput. Syst. Sci. 9, 355-365.
• 10: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• 11: WOLFE, ~/{. 1992. Flow graph anomalies: What's in a loop? Tech. Rep. CS/E 92-012, Oregon Graduate Inst. for Science and Technology, Portland, Oreg.

INDEX TERMS

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

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

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

General Terms:
Algorithms, Theory

Keywords:
DJ graphs, Tarjan's interval, dominator trees, irreducible flowgraphs, reducible flowgraphs