Michael D. Smith
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.
- Andrew W. Appel and Lal George. 2001 (May). Optimal spilling for CISC machines with few registers. In 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 243--253. Google Scholar
Digital Library
- Andrew W. Appel and Jens Palsberg. 2002. Modern Compiler Implementation in Java. Cambridge University Press, 2nd edition. Google ScholarDigital Library
- Preston Briggs. 1992 (April). Register allocation via graph coloring. Technical Report TR92-183, Rice University, Department of Computer Science.Google Scholar
- Preston Briggs, Keith Cooper, and Linda Torczon. 1992 (March). Coloring register pairs. ACM Letters on Programming Languages and Systems, 1(1):3--13. Google ScholarDigital Library
- Preston Briggs, Keith Cooper, and Linda Torczon. 1994 (May). Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems, 16(3): 428--455. Google ScholarDigital Library
- Gregory J. Chaitin. 1982. Register allocation and spilling via graph coloring. In 1982 SIGPLAN Symposium on Compiler Construction, pages 98--105. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Keith Cooper and Linda Torczon. 2003. Engineering a Compiler. Morgan Kaufmann.Google Scholar
- Changqing Fu and Kent D. Wilken. 2002 (November). A faster optimal register allocator. In 35th ACM/IEEE International Symposium on Microarchitecture, pages 245--256. Google ScholarDigital Library
- Lal George and Andrew W. Appel. 1996 (May). Iterated register coalescing. ACMTransactions on Programming Languages and Systems, 18(3):300--324. Google ScholarDigital Library
- David W. Goodwin and Kent D. Wilken. 1996 (August). Optimal and near-optimal global register allocations using 0-1 integer programming. Software-Practice & Experience, 26(8):929--965. Google ScholarDigital Library
- 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.Google Scholar
- Richard E. Kessler, Edward J. McLellan, and David A. Webb. 1998 (October). The Alpha 21264 microprocessor architecture. In International Conference on Computer Design, pages 90--95. Google ScholarDigital Library
- Timothy Kong and Kent D. Wilken. 1998 (December). Precise register allocation for irregular architectures. In 31st ACM/IEEE International Symposium on Microarchitecture, pages 297--307. Google ScholarDigital Library
- Akira Koseki, Hideaki Komatsu, and Toshio Nakatani. 2002 (June). Preference-directed graph coloring. In 2002 ACM SIG-PLAN Conference on Programming Language Design and Implementation, pages 33--44. Google ScholarDigital Library
- Chunho Lee, Miodrag Potkonjak, and William H. Mangione-Smith. 1997 (December). MediaBench: a tool for evaluating and synthesizing multimedia and communications systems. In 30th ACM/IEEE International Symposium on Microarchitecture, pages 330--335. Google ScholarDigital Library
- Allen Leung and Lal George. 1998. A new MLRISC register allocator. Standard ML of New Jersey compiler implementation notes.Google Scholar
- Michael Matz. 2003 (May). Design and implementation of a graph coloring register allocator for GCC. In GCC Developers Summit, pages 151--170.Google Scholar
- Steven S. Muchnick. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann. Google ScholarDigital Library
- Brian R. Nickerson. 1990 (June). Graph coloring register allocation for processors with multi-register operands. In 1990 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 40--52. Google ScholarDigital Library
- 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.Google Scholar
- Bernhard Scholz and Erik Eckstein. 2002 (June). Register allocation for irregular architectures. In Proceedings of the Joint Conference on Languages, Compilers and Tools for Embedded Systems, pages 139--148. Google ScholarDigital Library
Index Terms
- A generalized algorithm for graph-coloring register allocation
Recommendations
A generalized algorithm for graph-coloring register allocation
PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementationGraph-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 ...
Improvements to graph coloring register allocation
We describe two improvements to Chaitin-style graph coloring register allocators. The first, optimistic coloring, uses a stronger heuristic to find a k-coloring for the interference graph. The second extends Chaitin's treatment of rematerialization to ...
Differential register allocation
PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementationMicro-architecture designers are very cautious about expanding the number of architected registers (also the register field), because increasing the register field adds to the code size, raises I-cache and memory pressure, complicates processor ...
Comments