A retargetable register allocation framework for embedded processors

ABSTRACT

This paper describes the FlexCC2 register allocation framework. FlexCC2 is an optimizing retargetable C compiler for embedded processors, and in particular for DSP processors. Embedded processors often contain features such as irregular and constrained register sets that complicate register allocation, making traditional methods inefficient. In this paper, we present a register allocation framework specifically tailored for embedded processor specificities. This framework has been integrated in the FlexCC2 production compiler and is used by FlexCC2 customers.

REFERENCES

• 1: ACE Associated Compiler Expert bv. The CoSy Framework, a Compiler Construction System. Ref. CoSy-8006-fw, 2000.
• 2: A. Appel, J. Davidson, and N. Ramsey. The Zephyr Compiler Infrastructure. Internal Report, http://www.cs.virginia.edu/zephyr, University of Virginia, 1998.
• 3: Peter Bergner , Peter Dahl , David Engebretsen , Matthew O'Keefe, Spill code minimization via interference region spilling, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.287-295, June 16-18, 1997, Las Vegas, Nevada, United States
• 4: Valérie Bertin , Jean-Marc Daveau , Philippe Guillaume , Thierry Lepley , Denis Pilat , Claire Richard , Miguel Santana , Thomas Thery, FlexCC2: An Optimizing Retargetable C Compiler for DSP Processors, Proceedings of the Second International Conference on Embedded Software, p.382-398, October 07-09, 2002
• 5: Preston Briggs, Register allocation via graph coloring, Rice University, Houston, TX, 1992
• 6: Preston Briggs , Keith D. Cooper , Linda Torczon, Coloring register pairs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.3-13, March 1992 [doi>10.1145/130616.130617]
• 7: 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
• 8: David Callahan , Brian Koblenz, Register allocation via hierarchical graph coloring, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.192-203, June 24-28, 1991, Toronto, Ontario, Canada
• 9: 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
• 10: Keith D. Cooper , L. Taylor Simpson, Live Range Splitting in a Graph Coloring Register Allocator, Proceedings of the 7th International Conference on Compiler Construction, p.174-187, March 28-April 04, 1998
• 11: Lal George , Andrew W. Appel, Iterated register coalescing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.300-324, May 1996 [doi>10.1145/229542.229546]
• 12: Sungjoon Jung , Yunheung Paek, The very portable optimizer for digital signal processors, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502230]
• 13: Daniel Kästner, PROPAN: A Retargetable System for Postpass Optimisations and Analyses, Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems, p.63-80, June 18, 2000
• 14: Daniel Kästner, TDL: a hardware description language for retargetable postpass optimizations and analyses, Proceedings of the second international conference on Generative programming and component engineering, p.18-36, September 22-25, 2003, Erfurt, Germany
• 15: Timothy Kong , Kent D. Wilken, Precise register allocation for irregular architectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.297-307, November 1998, Dallas, Texas, United States
• 16: Guei-Yuan Lueh , Thomas Gross , Ali-Reza Adl-Tabatabai, Fusion-based register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.431-470, May 2000 [doi>10.1145/353926.353929]
• 17: E. Rohou, F. Bodin, A. Seznec. SALTO: System for Assembly Language Transformation and Optimization. Technical report 1032, IRISA, September 1996.
• 18: J. Runeson, S-O Nyström. Retargetable Graph-Coloring Register Allocation for Irregular Architectures. Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems (SCOPES'03), September 2003, Pages 240--254.

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
embedded processors, register allocation