research-article

Graph-coloring and treescan register allocation using repairing

Authors:

Quentin Colombet,

Benoit Boissinot,

Sebastian Hack,

Fabrice RastelloAuthors Info & Claims

CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems

Pages 45 - 54

https://doi.org/10.1145/2038698.2038708

Published: 09 October 2011 Publication History

Abstract

Graph coloring and linear scan are two appealing techniques for register allocation as the underlying formalism are extremely clean and simple. This paper advocates a decoupled approach that first lowers the register pressure by spilling variables, and then performs live ranges splitting/coalescing/coloring in a separate phase; this enables the design of simpler, cleaner, and more efficient register allocators.

This paper gives a new and more general approach to deal with register constraints. This approach called repairing does not require pre live range splitting and does not introduce additional spill code. It ignores register constraints during coloring/coalescing, and repairs violated constraints afterwards.

We applied this method to both graph based and scan based allocators into a decoupled approach. Here, the Iterated Register Coalescer (IRC) and a scan algorithm that uses Static Single Assignment (SSA) properties, the treescan. Moreover, this paper provides a survey on existing and new techniques of bias coloring during scan approaches.

Our experimental evaluation shows for the graph based approach, that we reduced the number of vertices (edges) in the interference graph by 26% (33%) without compromising the quality of the generated code. The treescan algorithm improved the compile time of the allocation process by 6.97x over IRC while providing comparable results for the quality of the generated code.

References

[1]

Andrew W. Appel and Lal George. Optimal spilling for CISC machines with few registers. In ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01), pages 243--253. ACM Press, 2001.

Digital Library

[2]

Thomas Ball and James R. Larus. Branch prediction for free. SIGPLAN Notices, 28(6):300--313, 1993.

[3]

Benoit Boissinot, Alain Darte, Benoît Dupont de Dinechin, Christophe Guillon, and Fabrice Rastello. Revisiting out-of-SSA translation for correctness, code quality, and efficiency. In International Symposium on Code Generation and Optimization (CGO'09). IEEE Computer Society Press, March 2009.

Digital Library

[4]

Benoit Boissinot, Sebastian Hack, Daniel Grund, Benoît Dupont de Dinechin, and Fabrice Rastello. Fast liveness checking for SSA-form programs. In CGO'08: proceedings of the sixth annual ieee/acm international symposium on code generation and optimization, pages 35--44, New York, NY, USA, 2008. ACM.

Digital Library

[5]

Florent Bouchez. A Study of Spilling and Coalescing in Register Allocation as Two Separate Phases. PhD thesis, ENS Lyon, France, apr 2009.

[6]

Florent Bouchez, Alain Darte, and Fabrice Rastello. On the complexity of register coalescing. In CGO '07: Proceedings of the International Symposium on Code Generation and Optimization, pages 102--114, Washington, DC, USA, mar 2007. IEEE Computer Society Press. Best paper award.

Digital Library

[7]

Florent Bouchez, Alain Darte, and Fabrice Rastello. On the complexity of spill everywhere under ssa form. SIGPLAN Not., 42:103--112, June 2007.

Digital Library

[8]

Florent Bouchez, Alain Darte, and Fabrice Rastello. Advanced conservative and optimistic register coalescing. In CASES'08: Proceedings of the 2008 international conference on Compilers, +Architectures and Synthesis for Embedded Systems, pages 147--156, New York, NY, USA, 2008. ACM.

Digital Library

[9]

Matthias Braun and Sebastian Hack. Register Spilling and Live-Range Splitting for SSA-Form Programs. In Compiler Construction 2009, volume 5501 of Lecture Notes In Computer Science, pages 174--189. Springer, 2009.

Digital Library

[10]

Matthias Braun, Christoph Mallon, and Sebastian Hack. Preference-Guided Register Assignment. In Compiler Construction 2010, volume 6011 of Lecture Notes In Computer Science, pages 205--223. Springer, 2010.

Digital Library

[11]

Preston Briggs. Register allocation via graph coloring. PhD thesis, Rice university, April 1992.

Digital Library

[12]

Preston Briggs, Keith D. Cooper, and Linda Torczon. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems, 16(3):428--455, May 1994.

Digital Library

[13]

Philip Brisk, Foad Dabiri, Jamie Macbeth, and Majid Sarrafzadeh. Polynomial time graph coloring register allocation. In 14th International Workshop on Logic and Synthesis, June 2005.

[14]

Zoran Budimlić, Keith Cooper, Tim Harvey, Ken Kennedy, Tim Oberg, and Steve Reeves. Fast copy coalescing and live range identification. In Proceedings of the ACM Sigplan Conference on Programming Language Design and Implementation (PLDI'02), pages 25--32, Berlin, Germany, June 2002. ACM Press.

Digital Library

[15]

G. J. Chaitin. Register allocation & spilling via graph coloring. In ACM SIGPLAN Symposium on Compiler Construction (CC'82), volume 17(6) of SIGPLAN Notices, pages 98--105, 1982.

Digital Library

[16]

Gregory J. Chaitin, Marc A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. Register allocation via coloring. Computer Languages, 6:47--57, January 1981.

Digital Library

[17]

Fred C. Chow and John L. Hennessy. The priority-based coloring approach to register allocation. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(4):501--536, Oct. 1990.

Digital Library

[18]

Paolo Faraboschi, Geoffrey Brown, Joseph A. Fisher, Giuseppe Desoli, and Fred Homewood. Lx: A technology platform for customizable VLIW embedded processing. In Proceedings of the 27th International Symposium on Computer Architecture, pages 203--213. ACM, June 2000.

Digital Library

[19]

G. Gao, J. Amaral, J. Dehnert, and R. Towle. The SGI Pro64 compiler infrastructure. In Tutorial, International Conference on Parallel Architectures and Compilation Techniques, 2000.

[20]

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

Digital Library

[21]

Sebastian Hack. Register Allocation for Programs in SSA Form. PhD thesis, Universität Karlsruhe, October 2007.

[22]

Sebastian Hack, Daniel Grund, and Gerhard Goos. Register allocation for programs in SSA form. In International Conference on Compiler Construction (CC'06), volume 3923 of LNCS. Springer, 2006.

Digital Library

[23]

Allen Leung and Lal George. Static single assignment form for machine code. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'99), pages 204--214. ACM Press, 1999.

Digital Library

[24]

Hanspeter Mössenböck and Michael Pfeiffer. Linear scan register allocation in the context of SSA form and register constraints. In International Conference on Compiler Construction (CC'02), volume 2304 of LNCS, pages 229--246. Springer, 2002.

Digital Library

[25]

Rei Odaira, Takuya Nakaike, Tatsushi Inagaki, Hideaki Komatsu, and Toshio Nakatani. Coloring-based coalescing for graph coloring register allocation. In Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization, CGO '10, pages 160--169, New York, NY, USA, 2010. ACM.

Digital Library

[26]

Jinpyo Park and Soo-Mook Moon. Optimistic register coalescing. In Proceedings of the International Conference on Parallel Architecture and Compilation Techniques (PACT'98), pages 196--204. IEEE Press, 1998.

Digital Library

[27]

Jinpyo Park and Soo-Mook Moon. Optimistic register coalescing. ACM Transactions on Programming Languages and Systems (ACM TOPLAS), 26(4), 2004.

Digital Library

[28]

Fernando Magno Quintão Pereira and Jens Palsberg. Register allocation by puzzle solving. In PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, pages 216--226, New York, NY, USA, 2008. ACM.

Digital Library

[29]

Massimiliano Poletto and Vivek Sarkar. Linear scan register allocation. ACM Transactions on Programming Languages and Systems, 21(5):895--913, 1999.

Digital Library

[30]

Hongbo Rong. Tree Register Allocation. In Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 67--77. ACM, 2009.

Digital Library

[31]

Vivek Sarkar and Rajkishore Barik. Extended linear scan: An alternate foundation for global register allocation. In International Conference on Compiler Construction (CC'07), volume 4420 of LNCS, pages 141--155. Springer, 2007.

Digital Library

[32]

Michael D. Smith, Norman Ramsey, and Glenn Holloway. A generalized algorithm for graph-coloring register allocation. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 277--288, New York, NY, USA, 2004. ACM.

Digital Library

[33]

Omri Traub, Glenn Holloway, and Michael D. Smith. Quality and speed in linear-scan register allocation. SIGPLAN Not., 33(5):142--151, 1998.

Digital Library

[34]

C. Wimmer and M. Franz. Linear scan register allocation on ssa form. In Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization, pages 170--179. ACM, 2010.

Digital Library

[35]

Christian Wimmer and Hanspeter Mössenböck. Optimized interval splitting in a linear scan register allocator. In 1st ACM/USENIX International Conference on Virtual Execution Environments (VEE), pages 132--141, 2005.

Digital Library

Cited By

Chen WHao PLiu DBai Y(2022)Compilation of Parallel Data Access for Vector Processor in Radio Base StationsIEEE Embedded Systems Letters10.1109/LES.2021.308566414:1(11-14)Online publication date: Mar-2022
https://doi.org/10.1109/LES.2021.3085664
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
Miri MDarmani YMohamedpour KYaghoubi MSarkar M(2020)DRAGON: A Dynamic Distributed Resource Allocation Algorithm for Wireless NetworksIEEE Communications Letters10.1109/LCOMM.2020.298833424:8(1780-1783)Online publication date: Aug-2020
https://doi.org/10.1109/LCOMM.2020.2988334
Show More Cited By

Recommendations

Linear scan register allocation on SSA form
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization

The linear scan algorithm for register allocation provides a good register assignment with a low compilation overhead and is thus frequently used for just-in-time compilers. Although most of these compilers use static single assignment (SSA) form, the ...
Coloring-based coalescing for graph coloring register allocation
CGO '10: Proceedings of the 8th annual IEEE/ACM international symposium on Code generation and optimization

Graph coloring register allocation tries to minimize the total cost of spilled live ranges of variables. Live-range splitting and coalescing are often performed before the coloring to further reduce the total cost. Coalescing of split live ranges, ...
Optimistic chordal coloring: a coalescing heuristic for SSA form programs

The interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the k -colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CASES '11: Proceedings of the 14th international conference on Compilers, architectures and synthesis for embedded systems

October 2011

250 pages

ISBN:9781450307130

DOI:10.1145/2038698

Program Chairs:
Rajesh Gupta
University of California at San Diego
,
Vincent Mooney
Georgia Tech. & Nanyang Tech. U.

Copyright © 2011 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 October 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESWeek '11

Sponsor:

ESWeek '11: Seventh Embedded Systems Week

October 9 - 14, 2011

Taipei, Taiwan

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
290
Total Downloads

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

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen WHao PLiu DBai Y(2022)Compilation of Parallel Data Access for Vector Processor in Radio Base StationsIEEE Embedded Systems Letters10.1109/LES.2021.308566414:1(11-14)Online publication date: Mar-2022
https://doi.org/10.1109/LES.2021.3085664
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
Miri MDarmani YMohamedpour KYaghoubi MSarkar M(2020)DRAGON: A Dynamic Distributed Resource Allocation Algorithm for Wireless NetworksIEEE Communications Letters10.1109/LCOMM.2020.298833424:8(1780-1783)Online publication date: Aug-2020
https://doi.org/10.1109/LCOMM.2020.2988334
Miri MMohamedpour KDarmani YSarkar M(2019)DIAMOND: a distributed algorithm for vertex coloring problems and resource allocationIET Networks10.1049/iet-net.2018.52048:6(381-389)Online publication date: Nov-2019
https://doi.org/10.1049/iet-net.2018.5204
Rawat PRastello FSukumaran-Rajam APouchet LRountev ASadayappan P(2018)Register optimizations for stencils on GPUsACM SIGPLAN Notices10.1145/3200691.317850053:1(168-182)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178500
Rawat PRastello FSukumaran-Rajam APouchet LRountev ASadayappan PKrall AGross T(2018)Register optimizations for stencils on GPUsProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178500(168-182)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178500
Chen WLueh GAshar PChen KCheng BKnoop JSchordan MJohnson TO'Boyle M(2018)Register allocation for Intel processor graphicsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168806(352-364)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168806
Kananizadeh SKononenko K(2018)Improving on Linear Scan Register AllocationInternational Journal of Automation and Computing10.1007/s11633-017-1100-015:2(228-238)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11633-017-1100-0
Li GHu YQiu YHuang W(2017)Investigation on the Optimization for Storage Space in Register-SpillingCollaborate Computing: Networking, Applications and Worksharing10.1007/978-3-319-59288-6_63(627-633)Online publication date: 5-Jul-2017
https://doi.org/10.1007/978-3-319-59288-6_63
Krause PCorporaal HStuijk S(2015)Bytewise Register AllocationProceedings of the 18th International Workshop on Software and Compilers for Embedded Systems10.1145/2764967.2764971(22-27)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1145/2764967.2764971
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.

Media

Figures

Other

Tables

View Table of Contents