article

Free access

Register allocation via hierarchical graph coloring

Authors:

David Callahan,

Brian KoblenzAuthors Info & Claims

ACM SIGPLAN Notices, Volume 26, Issue 6

Pages 192 - 203

https://doi.org/10.1145/113446.113462

Published: 01 May 1991 Publication History

PDF eReader

References

[1]

F. E. Allen. Control Flow Analysis. In Proceedings of the SIGPLAN '70 Symposium on Compiler Construction, pages 1-19, July 1970.

Digital Library

Google Scholar

[2]

D. Bernstein, D. Goldin, M. Golumbic, H. Krawczyk, Y. Mansour, I. Nahshon, and R. Pinter. Spill code minimization techniques for optimizing compilers. In Proceedings of the A CM SIGPLAN 89 Conference on Program Language Design and Implementation, pages 258- 263, June 1989.

Digital Library

Google Scholar

[3]

P. Briggs, K. Cooper, K. Kennedy, and L. Torczon. Coloring Heuristics for Register Allocation. In Proceedings of the A CM $IGPLAN 89 Conference on Program Language Design and Implementation, pages 275-284, June 1989.

Digital Library

Google Scholar

[4]

P. Briggs, K. Cooper, and L. Torczon. Aggressive Live range Splitting. Technical report, Rice University, 1991.

Google Scholar

[5]

D. Callahan, S. Carr, and K. Kennedy. Improving Register Allocation for Subscripted Variables. In Proceedings of the A CM SiGPLAN 90 Conference on Program Language Design and Implementation, pages 53-65, June 1990.

Digital Library

Google Scholar

[6]

G. Chaitin. Register Allocation and Spilling via Graph Coloring. in Proceedings of the $IGPLAN '82 Symposium on Compiler Construction, pages 98-105, June 1982.

Digital Library

Google Scholar

[7]

F. Chow. Minimizing Register Usage Penalty at Procedure Calls. In Proceedings of the A CM ${GPLAN 88 Conference on Program Language Design and Implementation, pages 85-94, June 1988.

Digital Library

Google Scholar

[8]

F. Chow and J. Hennessy. Register Allocation by Priority-based Coloring. In Proceedings of lh~ SIGPLAN '84 Symposium on Compiler Construction, SIGPLAN Notices Vol. 19, No. 6, pages 222-232, June 1984.

Digital Library

Google Scholar

[9]

R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. An Efficient Method of Computing Static Single Assignment Form. In Conference Record of the Sixteenth A CM Symposium on the Principles of Programming Languages, pages 25-35, January 1989.

Digital Library

Google Scholar

[10]

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The Program Dependence Graph and Its Use in Optimization. A CM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987.

Digital Library

Google Scholar

[11]

1~. Gupta, M. L. Sofia, and T. Steele. Register Allocation via Clique Separators. In Proceedings of the A CM SIGPLAN 89 Conference on Program Language Design and Implementation, pages 264-274, June 1989.

Digital Library

Google Scholar

[12]

K. Knobe and A. Meltzer. Control Tree based Register Allocation. Technical report, COM- PASS, 1990.

Google Scholar

[13]

J. Larus and P. Hilfinger. Register Allocation in the SPUR Lisp Compiler. In Proceedings of the $iGPLAN '86 Symposium on Compiler Construction, SIGPLAN Notices Vol. 21, No. 7, pages 255-263, June 1986.

Digital Library

Google Scholar

[14]

M. Sharir. Structural Analysis: A New Approach to Flow Analysis in Optimizing Compilers. Computer Languages, 5:151-153, 1980.

Google Scholar

[15]

R. E. Tarjan. Testing Flow Graph Reducibility. Journal of Computer and Sysiem Sciences, 9:355-365, 1974.

Digital Library

Google Scholar

Cited By

View all

(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
Shin YSung H(2021)Hybrid Register Allocation with Spill Cost and Pattern Guided OptimizationLanguages and Compilers for Parallel Computing10.1007/978-3-030-99372-6_3(33-49)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-99372-6_3
Show More Cited By

Index Terms

Recommendations

Register allocation and spilling via graph coloring
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to ...
Register allocation & spilling via graph coloring
Proceedings of the 1982 SIGPLAN symposium on Compiler construction

In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGPLAN Notices Volume 26, Issue 6

June 1991

352 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/113446

Editor:
Richard L. Wexelblat
IDA/CSED, Alexandria, VA

Issue’s Table of Contents

PLDI '91: Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation
May 1991
356 pages
ISBN:0897914287
DOI:10.1145/113445
Chairman:
David S. Wise
Indiana Univ., Bloomington

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: 01 May 1991

Published in SIGPLAN Volume 26, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

144
Total Citations
View Citations
1,538
Total Downloads

Downloads (Last 12 months)197
Downloads (Last 6 weeks)33

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

(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
Shin YSung H(2021)Hybrid Register Allocation with Spill Cost and Pattern Guided OptimizationLanguages and Compilers for Parallel Computing10.1007/978-3-030-99372-6_3(33-49)Online publication date: 13-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-99372-6_3
Eisl JLeopoldseder DMössenböck HTilevich EMössenböck H(2018)Parallel trace register allocationProceedings of the 15th International Conference on Managed Languages & Runtimes10.1145/3237009.3237010(1-7)Online publication date: 12-Sep-2018
https://dl.acm.org/doi/10.1145/3237009.3237010
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
Gopinath K(2010)Register AllocationThe Compiler Design Handbook10.1201/9781420040579.ch13Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch13
Bouchez FColombet QDarte ARastello FGuillon CDeprettere EStefanov T(2010)Parallel copy motionProceedings of the 13th International Workshop on Software & Compilers for Embedded Systems10.1145/1811212.1811214(1-10)Online publication date: 28-Jun-2010
https://dl.acm.org/doi/10.1145/1811212.1811214
Krishna Nandivada V(2009)Advances in Register Allocation TechniquesThe Compiler Design Handbook10.1201/9781420043839.ch21(21-1-21-27)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch21
Rong HAlbonesi DMartonosi MAugust DMartínez J(2009)Tree register allocationProceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/1669112.1669123(67-77)Online publication date: 12-Dec-2009
https://dl.acm.org/doi/10.1145/1669112.1669123
Carroll DMeyerson ATagiku B(2009)Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal GraphsProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_3(29-41)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03685-9_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

References

Cited By

Index Terms

Recommendations

Register allocation and spilling via graph coloring

Register allocation & spilling via graph coloring

Improvements to graph coloring register allocation

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations