一种基于分区域优先级的寄存器分配算法

doi:10.3724/SP.J.1146.2012.01382

摘要
图/表
参考文献
相关文章 (1)

全文: PDF (287 KB)
输出: BibTeX | EndNote (RIS)

摘要编译器速度和生成代码质量是衡量寄存器分配阶段性能的两个关键因素，现代的即时编译器要求在尽可能短的时间内编译出高质量的代码。传统的基于图着色的算法和线性扫描算法均不能很好地满足这个要求，该文提出一种基于矩阵填充的区域优先级寄存器分配算法，不追求理论上完美的寄存器分配，而采用贪婪式的方法，对程序循环区域进行分割，按区域内生命域的长度和溢出权重两种优先级排序方法进行物理寄存器分配，再扩展到整个程序段。算法在保留线性分配时间的同时产生了高质量的代码，应用于编译SSA形式的PTX指令到多核平台的过程中，基于该编译平台的实验证明了该文改进算法的有效性。

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	岳峰
	庞建民
	赵荣彩

关键词 ：编译器, 寄存器分配, 循环区域分割, 贪婪法, 生命域长度优先级, 溢出权重优先级

Abstract：Compiling speed and code quality are two key factors to evaluate the performance of register allocation. Modern Just In Time (JIT) compilers desire the best code in least time. Neither traditional graph coloring algorithm nor linear scan algorithm can satisfy the condition perfectly. A regions priority algorithm is proposed in this paper, which does not pursue the perfect register allocation in theory but takes greedy design method. The program is divided by loop region, on which physical register allocation is implemented by dealing lifetime length priority queue and spill weight priority queue. Then the allocation extends to the whole program. This algorithm creates high quality code in linear time and is applied to the compiler which compiles PTX instructions in SSA to traditional multicore platform. The experiment based on this compiler verifies the effectiveness of the algorithm.

Key words： Compiler Register allocation Loop region divide Greedy Lifetime length priority Spill weight priority

收稿日期: 2012-10-26

PACS:

TP314

基金资助:

国家高技术研究发展计划(2009AA012201)，国家核高基重大专项(2009ZX01036-001-001)和河南省重大科技攻关专项(092101210501)资助课题

通讯作者: 岳峰 E-mail: firstchoiceyf@sina.com

引用本文:

岳峰, 庞建民, 赵荣彩. 一种基于分区域优先级的寄存器分配算法[J]. 电子与信息学报, 2013, 35(12): 3005-3010. Yue Feng, Pang Jian-Min, Zhao Rong-Cai. A Register Allocation Algorithm Based on Regions Priority. , 2013, 35(12): 3005-3010.

链接本文:

http://jeit.ie.ac.cn/CN/10.3724/SP.J.1146.2012.01382 或 http://jeit.ie.ac.cn/CN/Y2013/V35/I12/3005