Post-pass periodic register allocation to minimise loop unrolling degree

ABSTRACT

This paper solves an open problem regarding loop unrolling after periodic register allocation. Although software pipelining is a powerful technique to extract fine-grain parallelism, it generates reuse circuits spanning multiple loop iterations. These circuits require periodic register allocation, which in turn yield a code generation challenge, generally addressed through: (1) hardware support --- rotating register files --- deemed too expensive for embedded processors, (2) insertion of register moves with a high risk of reducing the computation throughput --- initiation interval (II) --- of software pipelining, and (3) post-pass loop unrolling that does not compromise throughput but often leads to unpractical code growth. The latter approach relies on the proof that MAXLIVE registers are sufficient for periodic register allocation (2; 3; 5); yet the only heuristic to control the amount of post-pass loop unrolling does not achieve this bound and leads to undesired register spills (4; 7).

We propose a periodic register allocation technique allowing a software-only code generation that does not trade the optimality of the II for compactness of the generated code. Our idea is based on using the remaining registers: calling R_arch the number of architectural registers of the target processor, then the number of remaining registers that can be used for minimising the unrolling degree is equal to R_arch-MAXLIVE.

We provide a complete formalisation of the problem and algorithm, followed by extensive experiments. We achieve practical loop unrolling degrees in most cases --- with no increase of the II --- while state-of-the-art techniques would either induce register spilling, degrade the II or lead to unacceptable code growth.

REFERENCES

• 1: D. de Werra , Ch. Eisenbeis , S. Lelait , B. Marmol, On a graph-theoretical model for cyclic register allocation, Discrete Applied Mathematics, v.93 n.2-3, p.191-203, July 20, 1999 [doi>10.1016/S0166-218X(99)00105-5]
• 2: S.A.A. Touati and C. Eisenbeis. Early Periodic Register Allocation on ILP Processors.Parallel Processing Letters, Vol. 14, No. 2, June 2004. World Scientific.
• 3: Laurie J. Hendren , Guang R. Gao , Erik R. Altman , Chandrika Mukerji, A Register Allocation Framework Based on Hierarchical Cyclic Interval Graphs, Proceedings of the 4th International Conference on Compiler Construction, p.176-191, October 05-07, 1992
• 4: M. Lam, Software pipelining: an effective scheduling technique for VLIW machines, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.318-328, June 20-24, 1988, Atlanta, Georgia, United States
• 5: Christine Eisenbeis , Sylvain Lelait , Bruno Marmol, The meeting graph: a new model for loop cyclic register allocation, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.264-267, June 27-29, 1995, Limassol, Cyprus
• 6: James C. Dehnert , Peter Y.-T. Hsu , Joseph P. Bratt, Overlapped loop support in the Cydra 5, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.26-38, April 03-06, 1989, Boston, Massachusetts, United States
• 7: Sylvain Lelait. Contribution à l'Allocation de Registres dans les Boucles. PhD thesis, Université d'Orléans, France, January 1996.
• 8: S.A.A. Touati. Register Pressure in Instruction Level Parallelism. PhD thesis, Université de Versailles, France, June 2002.
• 9: Benoît Dupont de Dinechin, A Unified Software Pipeline Construction Scheme for Modulo Scheduled Loops, Proceedings of the 4th International Conference on Parallel Computing Technologies, p.189-200, September 08-12, 1997
• 10: R. Cytron and J. Ferrante. What's in a Name? or the Value of Renaming for Parallelism Detection and Storage Allocation, Proceedings of the 1987 International Conference on Parallel Processing, pages 19--27, Pennsylvanie, August 1987.
• 11: Alexandru Nicolau , Roni Potasman , Haigeng Wang, Register Allocation, Renaming and Their Impact on Fine-Grain Parallelism, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.218-235, August 07-09, 1991
• 12: Richard A. Huff, Lifetime-sensitive modulo scheduling, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.258-267, June 21-25, 1993, Albuquerque, New Mexico, United States
• 13: J. A. Fisher, P. Faraboschi and C. Young.Embedded Computing: a VLIW Approach to Architecture, Compilers and Tools, Book, Morgan Kaufmann Publishers, 2005

INDEX TERMS

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

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

General Terms:
Algorithms, Performance

Keywords:
embedded code optimisation, loop unrolling, periodic register allocation, software pipelining