Tetris: a new register pressure control technique for VLIW processors

ABSTRACT

The run-time performance of VLIW (very long instruction word) microprocessors depends heavily on the effectiveness of its associated optimizing compiler. Typical VLIW compiler phases include instruction scheduling, which maximizes instruction level parallelism (ILP), and register allocation, which minimizes data spills to external memory. If ILP is maximized without considering register constraints, high register pressure may result, leading to increased spill code and reduced run-time performance. In this paper, a new register pressure reduction technique for embedded VLIW processors is presented to control register pressure prior to instruction scheduling and register allocation. By modifying the relative ordering of operations, this technique restructures code to better reduce spills. Our technique has been implemented in Trimaran, an academic VLIW compiler, and evaluated using a series of VLIW benchmarks. Experimental results show that, on average, our algorithm reduces dynamic spills and improves overall cycle counts by 6% for a VLIW architecture with 8 functional units and 32 registers versus previous spill code reduction techniques.

REFERENCES

• 1: David A. Berson , Rajiv Gupta , Mary Lou Soffa, URSA: A Unified ReSource Allocator for Registers and Functional Units in VLIW Architectures, Proceedings of the IFIP WG10.3. Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism, p.243-254, January 20-22, 1993
• 2: David A. Berson , Rajiv Gupta , Mary Lou Soffa, Integrated Instruction Scheduling and Register Allocation Techniques, Proceedings of the 11th International Workshop on Languages and Compilers for Parallel Computing, p.247-262, August 07-09, 1998
• 3: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 4: 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
• 5: 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
• 6: L. N. Chakrapani, J. Gyllenhaal, W. W. Hwu, S. A. Mahlke, K. V. Palem, and R. M. Rabbah. Trimaran, An Infrastructure for Research in Instruction Level Parallelism. In International Workshop on Languages and Compilers for High Performance Computing, pages 32--41, Sept. 2004.
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: R. P. Dilworth. A Decomposition Theorem for Partially Ordered Sets. Annals of Mathematics, 51(1):161--166, Jan. 1950.
• 9: Freescale Semiconductor, Inc. MSC8101 Reference Manual, 2005.
• 10: S.M. Freudenberger and J. C. Ruttenberg. Phase Ordering of Register Allocation and Instruction Scheduling. In International Workshop on Code Generation, pages 146--172, May 1991.
• 11: J. R. Goodman , W.-C. Hsu, Code scheduling and register allocation in large basic blocks, Proceedings of the 2nd international conference on Supercomputing, p.442-452, June 1988, St. Malo, France [doi>10.1145/55364.55407]
• 12: R. Govindarajan , Hongbo Yang , José Nelson Amaral , Chihong Zhang , Guang R. Gao, Minimum Register Instruction Sequencing to Reduce Register Spills in Out-of-Order Issue Superscalar Architectures, IEEE Transactions on Computers, v.52 n.1, p.4-20, January 2003 [doi>10.1109/TC.2003.1159750]
• 13: Hansoo Kim , Krishna Palem, Region-based register allocation for epic architectures, New York University, New York, NY, 2000
• 14: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: C. Norris , L. L. Pollock, A schedular-sensitive global register allocator, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.804-813, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169839]
• 16: Shlomit S. Pinter, Register allocation with instruction scheduling, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.248-257, June 21-25, 1993, Albuquerque, New Mexico, United States
• 17: Texas Instruments, Inc. TMS320C6000 CPU and Instruction Set Reference Guide, 2000.
• 18: Sid Ahmed Ali Touati, Register Saturation in Superscalar and VLIW Codes, Proceedings of the 10th International Conference on Compiler Construction, p.213-228, April 02-06, 2001
• 19: Sid-Ahmed-Ali Touati, Register saturation in instruction level parallelism, International Journal of Parallel Programming, v.33 n.4, p.393-449, August 2005 [doi>10.1007/s10766-005-6466-x]
• 20: Transmeta, Inc. Transmeta Efficeon TM8820 Processor, 2005.

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

General Terms:
Algorithms, Performance

Keywords:
instruction level parallelism, register pressure control, very long instruction word (VLIW) processor