Translator Disclaimer
Paper
8 March 2005 An improved approach of register allocation via graph coloring
Author Affiliations +
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.
© (2005) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
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
PROCEEDINGS
11 PAGES


SHARE
Advertisement
Advertisement
RELATED CONTENT


Back to Top