Improving register allocation for subscripted variables

ABSTRACT

Most conventional compilers fail to allocate array elements to registers because standard data-flow analysis treats arrays like scalars, making it impossible to analyze the definitions and uses of individual array elements. This deficiency is particularly troublesome for floating-point registers, which are most often used as temporary repositories for subscripted variables.In this paper, we present a source-to-source transformation, called scalar replacement, that finds opportunities for reuse of subscripted variables and replaces the references involved by references to temporary scalar variables. The objective is to increase the likelihood that these elements will be assigned to registers by the coloring-based register allocators found in most compilers. In addition, we present transformations to improve the overall effectiveness of scalar replacement and show how these transformations can be applied in a variety of loop nest types. Finally, we present experimental results showing that these techniques are extremely effective---capable of achieving integer factor speedups over code generated by good optimizing compilers of conventional design.

REFERENCES

• 1: Walid Abdul-Karim Abu-Sufah, Improving the performance of virtual memory computers., 1979
• 2: F. E. Allen and J. Cocke. A catalogue of optimizing transformations. In Design and Optimization of Compilers, pages 1--30. Prentice-Hall, 1972.
• 3: r. Allen , D. Callahan , K. Kennedy, Automatic decomposition of scientific programs for parallel execution, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.63-76, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41631]
• 4: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 5: Randy Allen , Ken Kennedy, Vector Register Allocation, IEEE Transactions on Computers, v.41 n.10, p.1290-1317, October 1992 [doi>10.1109/12.166606]
• 6: P. Briggs , K. D. Cooper , K. Kennedy , L. Torczon, Coloring heuristics for register allocation, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.275-284, June 19-23, 1989, Portland, Oregon, United States
• 7: David Callahan , John Cocke , Ken Kennedy, Estimating interlock and improving balance for pipelined architectures, Journal of Parallel and Distributed Computing, v.5 n.4, p.334-358, August 1988 [doi>10.1016/0743-7315(88)90002-0]
• 8: Steve Carr, Combining Optimization for Cache and Instruction-Level Parallelism, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.238, October 20-23, 1996
• 9: Steve Carr , Yiping Guan, Unroll-and-jam using uniformly generated sets, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.349-357, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 10: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 11: Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
• 12: G. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register allocation via coloring. Computer Languages, 6:45--57, Jan. 1981.
• 13: G. J. Chaitin, Register allocation & spilling via graph coloring, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.98-105, June 23-25, 1982, Boston, Massachusetts, United States
• 14: Frederick Chow , John Hennessy, Register allocation by priority-based coloring, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.222-232, June 17-22, 1984, Montreal, Canada
• 15: Karl-Heinz Drechsler , Manfred P. Stadel, A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.635-640, Oct. 1988 [doi>10.1145/48022.214509]
• 16: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, A practical data flow framework for array reference analysis and its use in optimizations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.68-77, June 21-25, 1993, Albuquerque, New Mexico, United States
• 17: D. Kuck, R. Kuhn, B. Leasure, and M. Wolfe. The structure of an advanced retargetable vectorizer. In Supercomputers: Design and Applications, pages 163--178. IEEE Computer Society Press, Silver Spring, MD., 1984.
• 18: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 19: D. Kuck, Y. Muraoka, and S. Chen. On the number of operations simultaneously executable in fortran-like programs and their resulting speedup. IEEE Transactions on Computers, C-21(12):1293--1310, Dec. 1972.
• 20: Leslie Lamport, The parallel execution of DO loops, Communications of the ACM, v.17 n.2, p.83-93, Feb. 1974 [doi>10.1145/360827.360844]
• 21: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 22: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 23: Yi Qian , Steve Carr , Philip H. Sweany, Optimizing Loop Performance for Clustered VLIW Architectures, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.271-280, September 22-25, 2002
• 24: Vivek Sarkar, Optimized unrolling of nested loops, Proceedings of the 14th international conference on Supercomputing, p.153-166, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335246]
• 25: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 26: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.274-286, December 02-04, 1996, Paris, France
• 27: M. Wolfe. Advanced loop interchange. In Proceedings of the 1986 International Conference on Parallel Processing, Aug. 1986.
• 28: Michael Wolfe, Loop skewing: the wavefront method revisited, International Journal of Parallel Programming, v.15 n.4, p.279-293, Oct. 1986 [doi>10.1007/BF01407876]
• 29: {AC72} F. E. Allen and J. Cocke. A catalogue of optimizing transformations. In Design and Optimization of Compilers, pages 1--30. Prentice-Hall, 1972.
• 30: John R. Allen , Ken Kennedy, Automatic loop interchange, ACM SIGPLAN Notices, v.19 n.6, p.233-246, June 1984
• 31: {AK84b} J. R. Allen and K. Kennedy. PFC: A program to convert fortran to parallel form. In Supercomputers: Design and Applications, pages 186--205. IEEE Computer Society Press, Silver Spring, MD., 1984.
• 32: {AK88} J. R. Allen and K. Kennedy. Vector register allocation. Technical report, Department of Computer Science, Rice University, 1988.
• 33: Alexander Aiken , Alexandru Nicolau, Loop Quantization: an Analysis and Algorithm, Cornell University, Ithaca, NY, 1987
• 34: {CAC+81} G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 6:45--57, January 1981.
• 35: {CCK87} D. Callahan, J. Cocke, and K. Kennedy. Estimating interlock and improving balance for pipelined machines. In Proceedings of the 1987 International Conference on Parallel Processing, August 1987.
• 36: Steve Carr , Ken Kennedy, Blocking Linear Algebra Codes for Memory Hierarchies, Proceedings of the Fourth SIAM Conference on Parallel Processing for Scientific Computing, p.400-405, December 11-13, 1989
• 37: {DBMS79} J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart. LINPACK User's Guide. SIAM Publications, Philadelphia, 1979.
• 38: D. Gannon , W. Jalby , K. Gallivan, Strategies for cache and local memory management by global program transformation, Proceedings of the 1st International Conference on Supercomputing, p.229-254, March 1988, Athens, Greece
• 39: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 40: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 41: Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
• 42: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982
• 43: {Wol86} M. Wolfe. Advanced loop interchange. In Proceedings of the 1986 International Conference on Parallel Processing, August 1986.
• 44: Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
• 45: M. Wolfe, More iteration space tiling, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.655-664, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76337]