An improved approach of register allocation via graph coloring

Lei Gao; Ce Shi

doi:10.1117/12.586295

Translator Disclaimer

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

Lei Gao, Ce Shi

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.

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