A generalized algorithm for graph-coloring register allocation

ABSTRACT

Graph-coloring register allocation is an elegant and extremely popular optimization for modern machines. But as currently formulated, it does not handle two characteristics commonly found in commercial architectures. First, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Second, multiple register names may be aliases for a single hardware register. We present a generalization of graph-coloring register allocation that handles these problematic characteristics while preserving the elegance and practicality of traditional graph coloring. Our generalization adapts easily to a new target machine, requiring only the sets of names in the register classes and a map of the register aliases. It also drops easily into a well-known graph-coloring allocator, is efficient at compile time, and produces high-quality code.

REFERENCES

• 1: Andrew W. Appel , Lal George, Optimal spilling for CISC machines with few registers, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.243-253, June 2001, Snowbird, Utah, United States
• 2: Andrew W. Appel , Jens Palsberg, Modern Compiler Implementation in Java, Cambridge University Press, New York, NY, 2003
• 3: Preston Briggs. 1992 (April). Register allocation via graph coloring. Technical Report TR92-183, Rice University, Department of Computer Science.
• 4: 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]
• 5: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 6: 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
• 7: Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. 1981. Register allocation via coloring. Computer Languages, 6(1):47--57.
• 8: Keith Cooper and Linda Torczon. 2003. Engineering a Compiler. Morgan Kaufmann.
• 9: Changqing Fu , Kent Wilken, A faster optimal register allocator, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 10: 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]
• 11: David W. Goodwin , Kent D. Wilken, Optimal and near-optimal global register allocations using 0–1 integer programming, Software—Practice & Experience, v.26 n.8, p.929-965, Aug. 1996 [doi>10.1002/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K]
• 12: Ulrich Hirnschrott, Andreas Krall, and Bernhard Scholz. 2003 (August). Graph coloring vs. optimal register allocation for optimizing compilers. In Joint Modular Languages Conference, volume 2789 of Lecture Notes in Computer Science, pages 202--213. Springer Press, Klagenfurt, Austria.
• 13: E. J. McLellan , D. A. Webb, The Alpha 21264 Microprocessor Architecture, Proceedings of the International Conference on Computer Design, p.90, October 05-05, 1998
• 14: 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
• 15: Akira Koseki , Hideaki Komatsu , Toshio Nakatani, Preference-directed graph coloring, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 16: 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
• 17: Allen Leung and Lal George. 1998. A new MLRISC register allocator. Standard ML of New Jersey compiler implementation notes.
• 18: Michael Matz. 2003 (May). Design and implementation of a graph coloring register allocator for GCC. In GCC Developers Summit, pages 151--170.
• 19: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 20: Brian R. Nickerson, Graph coloring register allocation for processors with multi-register operands, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.40-52, June 1990, White Plains, New York, United States
• 21: Johan Runeson and Sven-Olof Nystrom. 2003 (September). Re-targetable graph-coloring register allocation for irregular archi-tectures. In Software and Compilers for Embedded Systems (SCOPES), volume 2826 of Lecture Notes in Computer Science, pages 240--254. Springer Press, Klagenfurt, Austria.
• 22: Bernhard Scholz , Erik Eckstein, Register allocation for irregular architectures, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany

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; Retargetable compilers

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Languages

Keywords:
graph coloring, register allocation