Share Email Print

Proceedings Paper

An improved approach of register allocation via graph coloring
Author(s): Lei Gao; Ce Shi
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 8 March 2005
PDF: 11 pages
Proc. SPIE 5683, Embedded Processors for Multimedia and Communications II, (8 March 2005); doi: 10.1117/12.586295
Show Author Affiliations
Lei Gao, Zhejiang Univ. (China)
Ce Shi, Zhejiang Univ. (China)

Published in SPIE Proceedings Vol. 5683:
Embedded Processors for Multimedia and Communications II
Subramania Sudharsanan; V. Michael Bove Jr.; Sethuraman Panchanathan, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?