An improved approach of register allocation via graph coloring

Lei Gao; Ce Shi

doi:10.1117/12.586295

8 March 2005 An improved approach of register allocation via graph coloring

Lei Gao, Ce Shi

Proceedings Volume 5683, Embedded Processors for Multimedia and Communications II; (2005) https://doi.org/10.1117/12.586295
Event: Electronic Imaging 2005, 2005, San Jose, California, United States

Abstract

Register allocation is an important part of optimizing compiler. The algorithm of register allocation via graph coloring is implemented by Chaitin and his colleagues firstly and improved by Briggs and others. By abstracting register allocation to graph coloring, the allocation process is simplified. As the physical register number is limited, coloring of the interference graph can’t succeed for every node. The uncolored nodes must be spilled. There is an assumption that almost all the allocation method obeys: when a register is allocated to a variable v, it can’t be used by others before v quit even if v is not used for a long time. This may causes a waste of register resource. The authors relax this restriction under certain conditions and make some improvement. In this method, one register can be mapped to two or more interfered “living” live ranges at the same time if they satisfy some requirements. An operation named merge is defined which can arrange two interfered nodes occupy the same register with some cost. Thus, the resource of register can be used more effectively and the cost of memory access can be reduced greatly.

Citation Download Citation

Lei Gao and Ce Shi "An improved approach of register allocation via graph coloring", Proc. SPIE 5683, Embedded Processors for Multimedia and Communications II, (8 March 2005); https://doi.org/10.1117/12.586295

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available