基于优先级动态二进制翻译寄存器分配算法  

Register allocation algorithm of dynamic binary translation based on priority

作　　者：戴涛[1] 单征[1] 卢帅兵[1] 石强[1] 潭捷 

机构地区：[1]解放军信息工程大学数学工程与先进计算国家重点实验室,河南郑州450002

出　　处：《浙江大学学报（工学版）》2016年第7期1338-1346,共9页Journal of Zhejiang University：Engineering Science

基　　金：国家自然科学基金资助项目(61472447)

摘　　要：针对动态二进制翻译系统QEMU寄存器分配不考虑基本块之间对寄存器需求的差异性,造成不必要寄存器溢出而导致重复访存开销的问题,提出高效的基于优先级线性扫描寄存器分配算法.该算法基于中间表示与源平台寄存器之间的映射关系,获取每一次生成基本块中间指令预分配寄存器次数并统计排序确定寄存器的优先级,寄存器分配时动态调整寄存器分配顺序,减少寄存器溢出次数,降低生成本地代码指令数量.QEMU动态翻译x86、mips及arm平台的nbench测试集实验结果表明,该算法基于中间代码改进具有很好的跨平台性,有效减少了生成本地代码指令数目,比QEMU优化前翻译性能分别提升了6.7%、6.8%、4.7%.QEMU uses a simple sequential allocation algorithm to deal with all the basic blocks withoutconsidering the difference between the basic block, which causes a lot of register overflow. A more efficientpriority-based linear scan register allocation algorithm was presented based on the mapping betweenintermediate representation and the source platform register, dynamically adjusting register allocationsequence to reduce register spilling times and the number of generated native code instructions by countingand ordering the pre-allocated registers of a basic block. The improved algorithm has a good cross-platformbased on intermediate code, effectively reducing the generation of local code instructions. Experimentalresults show that the algorithm is better than the performance of QEMU before optimization, which respectivelyupgrades about 6. 7 % , 6 . 8 % , 4. 7 % in x86 platform, mips platform and arm platform.

关 键 词：动态二进制翻译 寄存器分配 QEMU 中间指令 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论] TN332[自动化与计算机技术—计算机科学与技术]