More Web Proxy on the site http://driver.im/

Article

On the Complexity of Register Coalescing

Authors:

Florent Bouchez,

Fabrice RastelloAuthors Info & Claims

CGO '07: Proceedings of the International Symposium on Code Generation and Optimization

Pages 102 - 114

https://doi.org/10.1109/CGO.2007.26

Published: 11 March 2007 Publication History

Abstract

Memory transfers are becoming more important to optimize, for both performance and power consumption. With this goal in mind, new register allocation schemes are developed, which revisit not only the spilling problem but also the coalescing problem. Indeed, a more aggressive strategy to avoid load/store instructions may increase the constraints to suppress (coalesce) move instructions. This paper is devoted to the complexity of the coalescing phase, in particular in the light of recent developments on the SSA form. We distinguish several optimizations that occur in coalescing heuristics: a) aggressive coalescing removes as many moves as possible, regardless of the colorability of the resulting interference graph; b) conservative coalescing removes as many moves as possible while keeping the colorability of the graph; c) incremental conservative coalescing removes one particular move while keeping the colorability of the graph; d) optimistic coalescing coalesces moves aggressively, then gives up about as few moves as possible so that the graph becomes colorable again. We almost completely classify the NP-completeness of these problems, discussing also on the structure of the interference graph: arbitrary, chordal, or k-colorable in a greedy fashion. We believe that such a study is a necessary step for designing new coalescing strategies.

References

[1]

{1} A. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.

Digital Library

[2]

{2} A. Appel and L. George. Coalescing challenge. http:// www.cs.princeton.edu/~appel/coalesce, 2000.

[3]

{3} A. W. Appel and L. George. Optimal spilling for CISC machines with few registers. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'01), pages 243-253, Snowbird, Utah, United States, June 2001. ACM Press.

Digital Library

[4]

{4} F. Bouchez, A. Darte, C. Guillon, and F. Rastello. Register allocation and spill complexity under SSA. Technical Report RR2005-33, LIP, ENS-Lyon, France, Aug. 2005.

[5]

{5} F. Bouchez, A. Darte, C. Guillon, and F. Rastello. Register allocation: What does the NP-completeness proof of Chaitin et al. really prove? In WDDD 2006, Fifth Annual Workshop on Duplicating, Deconstructing, and Debunking, part of ISCA-33, Boston, MA, June 2006.

[6]

{6} P. Briggs. Register allocation via graph coloring. PhD Thesis Rice COMP TR92-183, Department of Computer Science, Rice University, 1992.

Digital Library

[7]

{7} P. Briggs, K. Cooper, and L. Torczon. Improvements to graph coloring register allocation. ACM Transactions on Programming Languages and Systems, 16(3):428-455, May 1994.

Digital Library

[8]

{8} P. Briggs, K. D. Cooper, T. J. Harvey, and L. T. Simpson. Practical improvements to the construction and destruction of static single assignment form. Software: Practice and Experience, 28(8):859-881, 1998.

Digital Library

[9]

{9} P. Brisk, F. Dabiri, J. Macbeth, and M. Sarrafzadeh. Polynomial time graph coloring register allocation. In 14th International Workshop on Logic and Synthesis, June 2005.

[10]

{10} Z. Budimlic, K. Cooper, T. Harvey, K. Kennedy, T. Oberg, and S. 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, 2002. ACM Press.

Digital Library

[11]

{11} G. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein. Register allocation via coloring. Computer Languages, 6:47-57, January 1981.

Digital Library

[12]

{12} G. J. Chaitin. Register allocation & spilling via graph coloring. In Proceedings of the 1982 ACM SIGPLAN Symposium on Compiler Construction, volume 17(6) of SIGPLAN Notices , pages 98-105, 1982.

Digital Library

[13]

{13} K. D. Cooper and L. T. Simpson. Live range splitting in a graph coloring register allocator. In Compiler Construction, volume 1383 of Lecture Notes in Computer Science, pages 174-187. Springer Verlag, 1998.

Digital Library

[14]

{14} T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press and McGraw-Hill Book Company, 1989.

Digital Library

[15]

{15} R. Cytron and J. Ferrante. What's in a name? Or the value of renaming for parallelism detection and storage allocation. In Proceedings of the 1987 International Conference on Parallel Processing, pages 19-27. IEEE Computer Society Press, Aug. 1987.

[16]

{16} R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4): 451-490, 1991.

Digital Library

[17]

{17} R. Cytron and R. Gershbein. Efficient accommodation of may-alias information in SSA form. In PLDI'93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, pages 36-45, New York, NY, USA, 1993. ACM Press.

Digital Library

[18]

{18} E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiway cuts. In 24th Annual ACM STOC, pages 241-251, Victoria, Canada, 1992. ACM Press.

Digital Library

[19]

{19} M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

Digital Library

[20]

{20} M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237-267, 1976.

[21]

{21} L. George and A. W. Appel. Iterated register coalescing. ACM Transactions on Programming Languages and Systems , 18(3):300-324, May 1996.

Digital Library

[22]

{22} M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

Digital Library

[23]

{23} S. Hack, D. Grund, and G. Goos. Towards register allocation for programs in SSA-form. Technical Report RR2005-27, Universität Karlsruhe, Sept. 2005.

[24]

{24} S. Hack, D. Grund, and G. Goos. Register allocation for programs in SSA-form. In Compiler Construction 2006, volume 3923 of LNCS. Springer Verlag, 2006.

Digital Library

[25]

{25} T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., 1995.

[26]

{26} A. Leung and L. 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

[27]

{27} V. Liberatore, M. Farach-Colton, and U. Kremer. Evaluation of algorithms for local register allocation. In 8th International Conference on Compiler Construction, volume 1575 of Lecture Notes in Computer Science, pages 137-152, Amsterdam, The Netherlands, Mar. 1999. Springer Verlag.

Digital Library

[28]

{28} G.-Y. Lueh, T. Gross, and A.-R. Adl-Tabatabai. Fusion-based register allocation. ACM Transactions on Programming Languages and Systems, 22(3):431-470, 2000.

Digital Library

[29]

{29} J. Park and S.-M. 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

[30]

{30} J. Park and S.-M. Moon. Optimistic register coalescing. ACM Transactions on Programming Languages and Systems (ACM TOPLAS), 26(4), 2004.

Digital Library

[31]

{31} F. M. Q. Pereira and J. Palsberg. Register allocation via coloring of chordal graphs. In Proceedings of APLAS'05, Asian Symposium on Programming Languages and Systems, pages 315-329, Tsukuba, Japan, Nov. 2005.

Digital Library

[32]

{32} F. M. Q. Pereira and J. Palsberg. Register allocation after classical SSA elimination is NP-complete. In Proceedings of FOSSACS'06, Foundations of Software Science and Computation Structures, Vienna, Austria, Mar. 2006.

Digital Library

[33]

{33} F. Rastello, F. de Ferrière, and C. Guillon. Optimizing the translation out-of-SSA with renaming constraints. Technical Report RR2005-34, LIP, ENS Lyon, France, august 2005.

[34]

{34} F. Rastello, F. de Ferrière, and C. Guillon. Optimizing translation out of SSA using renaming constraints. In Proceedings of the International Symposium on Code Generation and Optimization (CGO'04), pages 265-278. IEEE Computer Society, 2004.

Digital Library

[35]

{35} V. C. Sreedhar, R. D. Ju, D. M. Gillies, and V. Santhanam. Translating out of static single assignment form. In A. Cortesi and G. Filé, editors, Proceedings of the 6th international Symposium on Static Analysis, volume 1694 of Lecturem Notes in Computer Science, pages 194-210. Springer Verlag, 1999.

Digital Library

[36]

{36} S. R. Vegdahl. Using node merging to enhance graph coloring. In Proceedings of the ACM SIGPLAN conference on Programming language design and implementation (PLDI'99), pages 150-154, New York, NY, USA, 1999. ACM Press.

Digital Library

[37]

{37} H. Yang, W. Hu, R. Qiao, and Z. Zhang. Approaches to enhance graph coloring register allocation. In Proceedings of 1998 International Symposium for Future Software Technology (ISFST'98), 1998.

Cited By

Chandrasekhar AChen GChen PChen WGu JGuo PKumar SLueh GMistry PPan WRaoux TTrifunovic KKandemir MJimborean AMoseley T(2019)IGC: the open source Intel graphics compilerProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314902(254-265)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314902
Eisl JMarr SWürthinger TMössenböck H(2017)Trace Register Allocation PoliciesProceedings of the 14th International Conference on Managed Languages and Runtimes10.1145/3132190.3132209(92-104)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3132190.3132209
Colombet QBrandner FDarte A(2015)Studying Optimal Spilling in the Light of SSAACM Transactions on Architecture and Code Optimization10.1145/268539211:4(1-26)Online publication date: 9-Jan-2015
https://dl.acm.org/doi/10.1145/2685392
Show More Cited By

Index Terms

On the Complexity of Register Coalescing
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Incremental compilers

Recommendations

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 ...
Optimistic coalescing for heterogeneous register architectures
LCTES '07: Proceedings of the 2007 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

In this paper, Optimistic coalescing has been proven as an elegant and effective technique that provides better chances of safely coloring more registers in register allocation than other coalescing techniques. Its algorithm originally assumes ...
Iterated register coalescing

An important function of any register allocator is to target registers so as to eliminate copy instructions. Graph-coloring register allocation is an elegant approach to this problem. If the source and destination of a move instruction do not interfere, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CGO '07: Proceedings of the International Symposium on Code Generation and Optimization

March 2007

346 pages

ISBN:0769527647

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 11 March 2007

Check for updates

Qualifiers

Article

Conference

CGO07

Sponsor:

CGO07: 5th Annual IEEE / ACM International Symposium on Code Generation and Optimization

March 11 - 14, 2007

Acceptance Rates

CGO '07 Paper Acceptance Rate 27 of 84 submissions, 32%;

Overall Acceptance Rate 312 of 1,061 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
327
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chandrasekhar AChen GChen PChen WGu JGuo PKumar SLueh GMistry PPan WRaoux TTrifunovic KKandemir MJimborean AMoseley T(2019)IGC: the open source Intel graphics compilerProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314902(254-265)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314902
Eisl JMarr SWürthinger TMössenböck H(2017)Trace Register Allocation PoliciesProceedings of the 14th International Conference on Managed Languages and Runtimes10.1145/3132190.3132209(92-104)Online publication date: 27-Sep-2017
https://dl.acm.org/doi/10.1145/3132190.3132209
Colombet QBrandner FDarte A(2015)Studying Optimal Spilling in the Light of SSAACM Transactions on Architecture and Code Optimization10.1145/268539211:4(1-26)Online publication date: 9-Jan-2015
https://dl.acm.org/doi/10.1145/2685392
Mohr MGrudnitsky AModschiedler TBauer LHack SHenkel JRabbah RRaghunathan A(2013)Hardware acceleration for programs in SSA formProceedings of the 2013 International Conference on Compilers, Architectures and Synthesis for Embedded Systems10.5555/2555729.2555743(1-10)Online publication date: 29-Sep-2013
https://dl.acm.org/doi/10.5555/2555729.2555743
Barik RZhao JSarkar V(2013)A decoupled non-SSA global register allocation using bipartite liveness graphsACM Transactions on Architecture and Code Optimization10.1145/254410110:4(1-24)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1145/2544101
Nandivada VBarik R(2013)Improved bitwidth-aware variable packingACM Transactions on Architecture and Code Optimization10.1145/2509420.250942710:3(1-22)Online publication date: 16-Sep-2013
https://dl.acm.org/doi/10.1145/2509420.2509427
Diouf BHantaş CCohen AÖzturk ÖPalsberg J(2013)A decoupled local memory allocatorACM Transactions on Architecture and Code Optimization10.1145/2400682.24006939:4(1-22)Online publication date: 20-Jan-2013
https://dl.acm.org/doi/10.1145/2400682.2400693
Rastello FDiouf BCohen A(2013)A polynomial spilling heuristicProceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2013.6495005(1-10)Online publication date: 23-Feb-2013
https://dl.acm.org/doi/10.1109/CGO.2013.6495005
Brandner FColombet Q(2013)Elimination of parallel copies using code motion on data dependence graphsComputer Languages, Systems and Structures10.1016/j.cl.2012.09.00139:1(25-47)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1016/j.cl.2012.09.001
Krause P(2013)Optimal register allocation in polynomial timeProceedings of the 22nd international conference on Compiler Construction10.1007/978-3-642-37051-9_1(1-20)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-37051-9_1
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