Please wait a minute...
J4  2010, Vol. 44 Issue (12): 2309-2313    DOI: 10.3785/j.issn.1008-973X.2010.12.012
任坤, 严晓浪, 孙玲玲, 翁延玲
浙江大学 超大规模集成电路设计研究所, 浙江 杭州 310027
ASIP register allocator based on improved graph-coloring algorithm
REN Kun, YAN Xiao-lang, SUN Ling-ling, WENG Yan-ling
Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China
 全文: PDF  HTML



A model was presented to describe the complicated restrictions among registers of application specific instruction processor (ASIP) register file, considering that the traditional graph-coloring register allocation cannot produce optimal code for ASIP with irregular structure. The traditional graph-coloring algorithm was improved to be adapted to ASIP according to this model. In the new algorithm, a directed interference graph was built by analyzing the variables‘live range and register constraints. The register allocation was translated into how to simplify this graph. At last the algorithm was applied to an ASIP compiler. Experimental results show that the improved algorithm has better performance of codegeneration and less register spilling than the traditional code-generation algorithm.

出版日期: 2010-12-01
:  TP 314  


通讯作者: 严晓浪,男,教授.     E-mail:
作者简介: 任坤(1979—),男,河北邢台人,博士生,从事编译技术研究.E-mail:
E-mail Alert


任坤, 严晓浪, 孙玲玲, 翁延玲. 基于改进图染色算法的ASIP寄存器分配器[J]. J4, 2010, 44(12): 2309-2313.

REN Kun, YAN Xiao-lang, SUN Ling-ling, WENG Yan-ling. ASIP register allocator based on improved graph-coloring algorithm. J4, 2010, 44(12): 2309-2313.


[1] AHO A V, SETHI R, ULLMAN J D, et al. Compiler: principles, techniques and tools[M]. Boston: AddisonWesley Longman Publishing Co., Inc, 1986.
[2] BRUNO J, SETHI R. Register allocation for an oneregister machine[R]. Pennsylvania: Pennsylvania State University, 1974.
[3] CHAITIN G J. Register allocation and spilling via graph coloring[J]. ACM SIGPLAN Notices, 1982, 17(6): 98-105.
[4] BRIGGS P, COOPER K D, TOREZON L. Improvements to graph coloring register allocation[J]. ACM Transactions on Programming Languages and Systems, 1994, 16(3): 428-455.
[5] LIAO S, DEVADAS S, KEUTZER K, et al. Code optimization techniques for embedded DSP microprocessors[C]∥ Design Automation Conference. [S.l.]: [s.n.], 1995: 599-604.
[6] LEUPERS R. Code optimization techniques for embedded processors[M]. Norwell: Kluwer Academic Publishers, 2000.
[7] KUDRIAVTSEV A, KOGGE P. Generation of permutations for SIMD processors[C]∥ Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, Compilers, and Tools for Embedded Systems. [S.l.]: [s.n.], 2005: 147-156.
[8] BRIGGS P. Register allocation via graph coloring [D]. Houston, USA: RICE University, 1992: 23-32.
[9] PEREIRA F M, PALSBERG J. Register allocation via coloring of Chordal graphs[C]∥ Proceedings of the 3rd Asian Symposium on Programming Languages and Systems. [S.l.]: [s.n.], 2005: 128-145.

No related articles found!