article

A generalized algorithm for graph-coloring register allocation

Authors:

Michael D. Smith,

Glenn HollowayAuthors Info & Claims

ACM SIGPLAN Notices, Volume 39, Issue 6

Pages 277 - 288

https://doi.org/10.1145/996893.996875

Published: 09 June 2004 Publication History

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 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.

Digital Library

[2]

Andrew W. Appel and Jens Palsberg. 2002. Modern Compiler Implementation in Java. Cambridge University Press, 2nd edition.

Digital Library

[3]

Preston Briggs. 1992 (April). Register allocation via graph coloring. Technical Report TR92-183, Rice University, Department of Computer Science.

[4]

Preston Briggs, Keith Cooper, and Linda Torczon. 1992 (March). Coloring register pairs. ACM Letters on Programming Languages and Systems, 1(1):3--13.

Digital Library

[5]

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.

Digital Library

[6]

Gregory J. Chaitin. 1982. Register allocation and spilling via graph coloring. In 1982 SIGPLAN Symposium on Compiler Construction, pages 98--105.

Digital Library

[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 and Kent D. Wilken. 2002 (November). A faster optimal register allocator. In 35th ACM/IEEE International Symposium on Microarchitecture, pages 245--256.

Digital Library

[10]

Lal George and Andrew W. Appel. 1996 (May). Iterated register coalescing. ACMTransactions on Programming Languages and Systems, 18(3):300--324.

Digital Library

[11]

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.

Digital Library

[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]

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.

Digital Library

[14]

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.

Digital Library

[15]

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.

Digital Library

[16]

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.

Digital Library

[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. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann.

Digital Library

[20]

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.

Digital Library

[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 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.

Digital Library

Cited By

Yue WZhang TJing ZWu KYang YYang ZWu YBu WZheng KKang JLin YTao YYan BHuang RYang Y(2024)A scalable universal Ising machine based on interaction-centric storage and compute-in-memoryNature Electronics10.1038/s41928-024-01228-7Online publication date: 13-Aug-2024
https://doi.org/10.1038/s41928-024-01228-7
Loitzl AZuleger F(2024)Modeling Register Pairs in CompCertIntegrated Formal Methods10.1007/978-3-031-76554-4_8(128-147)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1007/978-3-031-76554-4_8
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Show More Cited By

Index Terms

A generalized algorithm for graph-coloring register allocation
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Retargetable compilers
      2. Source code generation

Recommendations

A generalized algorithm for graph-coloring register allocation
PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation

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 ...
Optimistic register coalescing

Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a ...
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 ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 39, Issue 6

PLDI '04

May 2004

299 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/996893

Issue’s Table of Contents

PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation
June 2004
310 pages
ISBN:1581138075
DOI:10.1145/996841
General Chair:
William Pugh
University of Maryland, College Park
,
Program Chair:
Craig Chambers
University of Washington

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2004

Published in SIGPLAN Volume 39, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

98
Total Citations
View Citations
2,055
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)1

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yue WZhang TJing ZWu KYang YYang ZWu YBu WZheng KKang JLin YTao YYan BHuang RYang Y(2024)A scalable universal Ising machine based on interaction-centric storage and compute-in-memoryNature Electronics10.1038/s41928-024-01228-7Online publication date: 13-Aug-2024
https://doi.org/10.1038/s41928-024-01228-7
Loitzl AZuleger F(2024)Modeling Register Pairs in CompCertIntegrated Formal Methods10.1007/978-3-031-76554-4_8(128-147)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1007/978-3-031-76554-4_8
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)Register AllocationEngineering a Compiler10.1016/B978-0-12-815412-0.00019-X(663-712)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00019-X
Tichadou FRastello F(2021)Register AllocationSSA-based Compiler Design10.1007/978-3-030-80515-9_22(303-328)Online publication date: 12-Jun-2021
https://doi.org/10.1007/978-3-030-80515-9_22
Blunck HArmbruster DBendul JHütt M(2018)The balance of autonomous and centralized control in scheduling problemsApplied Network Science10.1007/s41109-018-0071-63:1Online publication date: 9-Jul-2018
https://doi.org/10.1007/s41109-018-0071-6
Kelefouras V(2017)A methodology pruning the search space of six compiler transformations by addressing them together as one problem and by exploiting the hardware architecture detailsComputing10.1007/s00607-016-0535-499:9(865-888)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s00607-016-0535-4
Eisl JGrimmer MSimon DWürthinger TMössenböck HZheng YBinder WTůma P(2016)Trace-based Register Allocation in a JIT CompilerProceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools10.1145/2972206.2972211(1-11)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.1145/2972206.2972211
Eisl JAldrich JEugster P(2015)Trace register allocationCompanion Proceedings of the 2015 ACM SIGPLAN International Conference on Systems, Programming, Languages and Applications: Software for Humanity10.1145/2814189.2814199(21-23)Online publication date: 25-Oct-2015
https://dl.acm.org/doi/10.1145/2814189.2814199
Kelefouras VKritikakou AGoutis C(2015)A methodology for speeding up loop kernels by exploiting the software information and the memory architectureComputer Languages, Systems and Structures10.1016/j.cl.2015.01.00341:C(21-41)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1016/j.cl.2015.01.003
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents