Toward efficient flow-sensitive induction variable analysis and dependence testing for loop optimization

ABSTRACT

This paper presents a new approach to improve flow-sensitive induction variable analysis and data dependence testing on intermediate program representations, such as control-flow graphs with low-level operations representations in single static assignment forms. Current compiler techniques have difficulties optimizing loops that exhibit irregular control flow patterns. The inaccuracy of loop analysis results in conservative estimations of array-based data dependences in loops, which negatively affects the speedup of the loop via parallelization and vectorization. Our approach is based on a novel CR# (CR-sharp) algebra that effectively represents the value progressions of (conditionally) updated variables in loops. The CR# forms of induction variables are constructed with a new flow-sensitive induction variable recognition algorithm. We also developed a new CR#-based nonlinear data dependence test that enables loops to be more effectively optimized.

REFERENCES

• 1: Alfred V. Aho , Monica S. Lam , Ravi Sethi , Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools (2nd Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2006
• 2: O. Bachmann. Chains of Recurrences. PhD thesis, Kent State University, College of Arts and Sciences, 1996.
• 3: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• 4: D. Berlin, D. Edelsohn, and S. Pop. High-level loop optimizations for gcc. In Proceedings of the 2004 GCC Developers Summit, pages 37--54, 2004.
• 5: Michael P. Gerlek , Eric Stoltz , Michael Wolfe, Beyond induction variables: detecting and classifying sequences using a demand-driven SSA form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.1, p.85-122, Jan. 1995 [doi>10.1145/200994.201003]
• 6: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.15-29, June 24-28, 1991, Toronto, Ontario, Canada
• 7: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic analysis for parallelizing compilers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.477-518, July 1996 [doi>10.1145/233561.233568]
• 8: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 9: D. Novillo. Tree SSA: A new optimization infrastructure for gcc. In Proceedings of the 2003 GCC Developers Summit, pages 181--193, 2003.
• 10: Program analysis techniques for transforming programs for parallel execution, Parallel Computing, v.28 n.3, p.455-469, March 2002 [doi>10.1016/S0167-8191(01)00132-6]
• 11: Z. Shen, Z. Li, and P.-C. Yew. An empirical study on array subscripts and data dependencies. In proceedings of the International Conference on Parallel Processing, volume 2, pages 145--152, 1989.
• 12: R. Tarjan. Depth first search and linear graph algorithms. SIAM Journal of Computing, 1(2):146--160, 1972.
• 13: Peng Tu , David Padua, Gated SSA-based demand-driven symbolic analysis for parallelizing compilers, Proceedings of the 9th international conference on Supercomputing, p.414-423, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224648]
• 14: Robert van Engelen, Efficient Symbolic Analysis for Optimizing Compilers, Proceedings of the 10th International Conference on Compiler Construction, p.118-132, April 02-06, 2001
• 15: R. van Engelen. The CR# algebra and its application in loop analysis and optimization. Technical report, Computer Science Dept., Florida State University, 2004.
• 16: Robert A. van Engelen , Johnnie Birch , Kyle A. Gallivan, Array Data Dependence Testing with the Chains of Recurrences Algebra, Proceedings of the Innovative Architecture for Future Generation High-Performance Processors and Systems (IWIA'04), p.70-81, January 12-14, 2004
• 17: Robert A. van Engelen , J. Birch , Y. Shou , B. Walsh , Kyle A. Gallivan, A unified framework for nonlinear dependence testing and symbolic analysis, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006226]
• 18: Michael Wolfe, Beyond induction variables, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.162-174, June 15-19, 1992, San Francisco, California, United States
• 19: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 20: Peng Wu , Albert Cohen , Jay Hoeflinger , David Padua, Monotonic evolution: an alternative to induction variable substitution for dependence analysis, Proceedings of the 15th international conference on Supercomputing, p.78-91, June 2001, Sorrento, Italy [doi>10.1145/377792.377809]
• 21: Eugene V. Zima, Recurrent Relations and Speed-up of Computations Using Computer Algebra Systems, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.152-161, April 13-15, 1992
• 22: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

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

Keywords:
compiler algorithms, induction variables, loop parallelization, recurrences