基于优先级动态二进制翻译寄存器分配算法戴 涛 ,单 征 ,卢帅兵,石 强 ,潭 捷 (解放军信息工程大学数学工程与先进计算国家重点实验室,河 南 郑 州 450002) 摘 要 :针对动态二进制翻译系统Q E M U 寄存器分配不 考 虑 基 本 块 之 间 对 寄 存 器 需 求 的 差 异 性 ,造成不必要寄存器溢出而导致重复访存开销的问题,提出高效的基于优先级线性扫描寄存器分配算法 .该算法基于中间表示与源平台寄存器之间的映射关系,获取每一次生成基本块中间指令预分配寄存器次数并统计排序确定寄存器的优先级 ,寄存器分配时动态调整寄存器分配顺序,减少寄存器溢出次数,降低生成本地代码指令数量.Q E M U 动态翻译 x86、m ip s及 a rm 平台的 nb ench测试集实验结果表明,该算法基于中间代码改进具有很好的跨平台性,有效减少了生成本地代码指令数目,比 Q E M U 优化前翻译性能分别提升了 6. 7 % 、6. 8 % 、4. 7%. 关 键 词 :动态二进制翻译;寄存器分配;Q E M U ;中间指令中图分类号: T P 314; T N 332 文献标志码: A 文章编号: 1008 - 973X(2016)07 - 1338 - 09 Register allocation algorithm of dynamic binary translation based on priority DAI Tao, SHAN Zheng, LU Shuai-bing, SHI Qiang, TAN Jie {State K ey Laboratory o f M athematical E ngineering and A dvanced Computing ? PL八 Inform ation E ngineering U niversity, Zhengzhou 450002, China) Abstract : QEMU uses a simple sequential allocation algorithm to deal with all the basic blocks without considering the difference between the basic block, which causes a lot of register overflow. A more efficient priority-based linear scan register allocation algorithm was presented based on the mapping between intermediate representation and the source platform register, dynamically adjusting register allocation sequence to reduce register spilling times and the number of generated native code instructions by counting and ordering the pre-allocated registers of a basic block. The improved algorithm has a good cross-platform based on intermediate code, effectively reducing the generation of local code instructions. Experimental results show that the algorithm is better than the performance of QEMU before optimization, which respectively upgrades about 6. 7 % , 6 . 8 % , 4. 7 % in x86 platform, mips platform and arm platform. Keywords: dynamic binary translation; register allocation ; Q EM U; intermediate code |