Please wait a minute...
浙江大学学报(工学版)
J4  2010, Vol. 44 Issue (12): 2309-2313    DOI: 10.3785/j.issn.1008-973X.2010.12.012
自动化技术、计算机技术     
基于改进图染色算法的ASIP寄存器分配器
任坤, 严晓浪, 孙玲玲, 翁延玲
浙江大学 超大规模集成电路设计研究所, 浙江 杭州 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
摘要：

针对传统的图染色算法很难为不规则结构的专用指令处理器（ASIP）生成优化代码的问题,提出一种能描述ASIP寄存器复杂约束关系的数学模型；改进了传统图染色算法,通过生命周期分析,将各种分配约束限制在一张有向数据相关图中,将寄存器分配问题转化为对有向数据相关图的简化问题；应用改进图染色算法构造了一个ASIP编译器.测试表明：和传统的图染色算法相比,改进图染色算法能充分地考虑寄存器之间的相互约束,降低了目标代码的空间尺寸,减少了寄存器的溢出.
Abstract:

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  
基金资助:

国家“863”高技术研究发展计划资助项目（2005AA1Z1271）.
通讯作者: 严晓浪,男,教授.     E-mail: yan@vlsi.zju.edu.cn
作者简介: 任坤（1979—）,男,河北邢台人,博士生,从事编译技术研究.E-mail: renk@vlsi.zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

任坤, 严晓浪, 孙玲玲, 翁延玲. 基于改进图染色算法的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.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2010.12.012    或    http://www.zjujournals.com/eng/CN/Y2010/V44/I12/2309

［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!