Please wait a minute...
浙江大学学报(工学版)
计算机技术、信息工程     
基于优先级动态二进制翻译寄存器分配算法
戴涛,单征,卢帅兵,石强,潭捷
解放军信息工程大学 数学工程与先进计算国家重点实验室,河南 郑州 450002
Register allocation algorithm of dynamic binary translation based on priority
DAI Tao, SHAN Zheng, LU Shuai bing, SHI Qiang, TAN Jie
State Key Laboratory of Mathematical Engineering and Advanced Computing, PLA Information Engineering University, Zhengzhou 450002, China
 全文: PDF(997 KB)   HTML
摘要:

针对动态二进制翻译系统QEMU寄存器分配不考虑基本块之间对寄存器需求的差异性,造成不必要寄存器溢出而导致重复访存开销的问题,提出高效的基于优先级线性扫描寄存器分配算法.该算法基于中间表示与源平台寄存器之间的映射关系,获取每一次生成基本块中间指令预分配寄存器次数并统计排序确定寄存器的优先级,寄存器分配时动态调整寄存器分配顺序,减少寄存器溢出次数,降低生成本地代码指令数量.QEMU动态翻译x86、mips及arm平台的nbench测试集实验结果表明,该算法基于中间代码改进具有很好的跨平台性,有效减少了生成本地代码指令数目,比QEMU优化前翻译性能分别提升了6.7%、6.8%、4.7%.

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.

出版日期: 2016-07-23
:  TP 314  
基金资助:

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

通讯作者: 单征,男,副教授. ORCID:0000-0001-9618-8551.     E-mail: zzzhengming@163.com
作者简介: 戴涛(1990-),男,硕士生,从事二进制翻译及软件逆向研究.ORCID:0000-0001-7009-9227.E-mail: daitworld@126.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

戴涛,单征,卢帅兵,石强,潭捷. 基于优先级动态二进制翻译寄存器分配算法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2016.07.016.

DAI Tao, SHAN Zheng, LU Shuai bing, SHI Qiang, TAN Jie. Register allocation algorithm of dynamic binary translation based on priority. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2016.07.016.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2016.07.016        http://www.zjujournals.com/eng/CN/Y2016/V50/I7/1338

[1] PENNEMAN N,  KUDINSKAS D,  RAWSTHORNE A, et al. Evaluation of dynamic binary translation techniques for full system virtualisation on ARMv7A [J]. Journal of Systems Architecture, 2016, 65: 30-45.
[2] 马湘宁. 二进制翻译关键技术研究[D]. 北京:中国科学院计算技术研究所, 2004.
MA Xiangning. Research on key technology to binary translation [D]. Beijing: Institute of Computing Technology Chinese Academy of Sciences, 2004.
[3] HAWKINS B, DEMSKY B, BRUENING D, et al. Optimizing binary translation of dynamically generated code [C]∥Proceedings of the 13th Annual IEEE/ACM International Symposium on Code Generation and Optimization. IEEE/ACM International Symposium on Code Generation and Optimization, 2015: 68-78.
[4] GSCHWIND M, ALLMAN E R, SATHAYE S. et al. Dynamic and transparent binary translation [J]. IEEE Computer, 2000, 33(3): 54-59.
[5] WEGMAN M N, ZADECK F K. Constant propagation with conditional branches [J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1991, 13(2): 181-210.
[6] MUTH R. Register liveness analysis of executable code\[EB/OL\].\[20150707\].www.cs.arizona.edu/alto/papers/liveness.ps.
[7] 马湘宁, 武成岗, 唐锋, 等. 二进制翻译中的标志位优化技术 [J]. 计算机研究与发展, 2005, 42(2): 329-337.
MA Xiangning, WU Chenggang, TANG Feng, et al. Two condition code optimization approaches in binary translation [J]. Journal of Computer Research and Development,2005, 42(2): 329-337.
[8] EBCIOGLU K, ALTMAN E, GSCHWIND M, et al. Dynamic binary translation and optimization [J]. IEEE Transactions on Computers, 2001, 50(6): 529-548.
[9] CHAITIN G J, AUSLANDER M A, CHANDRA A K, et al. Register allocation via coloring [J]. Computer Languages, 1981, 6(1): 47-57.
[10] CHAITIN G J. Register allocation and spilling via graph coloring [J]. ACM Sigplan Notices, 1982, 17(6): 98-101.
[11] TRAUB O, HOLLOWAY G, SMITH M D. Quality and speed in linearscan register allocation  [J]. Acm Sigplan Notices, 2010, 33(5):142-151.
[12] POLETTO M, SARKAR V. Linear scan register allocation [J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1999, 21(5): 895-913.
[13] ALEI Liang, GUAN Haibing, LI Zengxing. A research on register mapping strategies of QEMU [C]∥Proceedings of the 2nd International Symposium on Intelligence Computation and Applications (ISICA'2007). Wuhan: [s. n.], 2007: 168-172.
[14] 吴浩. 二进制翻译系统QEMU中的优化技术[D]. 上海:上海交通大学, 2007.
WU Hao. Optimization technology of QEMU[D]. Shanghai: Shanghai Jiao Tong University, 2007.
[15] 文延华, 唐大国, 漆锋滨. 二进制翻译中的寄存器映射与剪裁的实现 [J]. 软件学报, 2009, 20(2): 17.
WEN Yanhua,TANG Daguo,QI Fengbin. Register mapping and register function cutting out implementation in binary translation [J]. Journal of Software, 2009, 20(2): 17.
[16] 廖银, 孙广中, 姜海涛, 等. 动态二进制翻译中全寄存器直接映射方法 [J]. 计算机应用与软件, 2011, 28(11): 21-24.
LIAO Yin, SUN Guangzhong, JIANG Haitao, et al. All registers direct mapping method in dynamic binary translation [J]. Computer Applications and Software, 2011, 28(11): 21-24.
[17] CAI Z, LIANG A, QI Z, et al. Performance comparison of register allocation algorithms in dynamic binary translation [C]∥International Conference on Knowledge and Systems Engineering. Hanoi: IEEE, 2009: 113-119.
[18] LIANG Y, SHAO Y, YANG G, et al. Register allocation for QEMU dynamic binary translation systems [J]. International Journal of Hybrid Information Technology, 2015, 8(2): 199-210.
[19] FABRICE B. QEMU, a fast and portable dynamic translator [C]∥ Atec 05: Conference on Usenix Technical Conference.\[S.l.\]:Usenix,2005.
[20] 张西超,郭向英,赵雷,等. TCG动态二进制翻译技术研究 [J]. 计算机应用与研究,2013,30(11):34-37.
ZHANG Xichao, GUO Xiangying, ZHAO Lei, et al. Study on TCG dynamic binary translation technique [J]. Computer Application and Software, 2013, 30(11): 34-37.

[1] 卢帅兵,庞建民,单征,岳峰. 基于QEMU的跨平台静态二进制翻译系统[J]. 浙江大学学报(工学版), 2016, 50(1): 158-165.
[2] 王荣华, 孟建熠, 陈志坚, 严晓浪. 基于访问区域特征的高速地址翻译方法[J]. J4, 2014, 48(2): 348-353.
[3] 王荣华,孟建熠,陈志坚,严晓浪. 动态二进制翻译中的标志位优化算法[J]. J4, 2014, 48(1): 124-129.
[4] 任坤, 严晓浪, 孙玲玲, 翁延玲. 基于改进图染色算法的ASIP寄存器分配器[J]. J4, 2010, 44(12): 2309-2313.
[5] 付剑晶, 王珂. 基于交叉控制流混淆技术的编译方法[J]. J4, 2010, 44(5): 903-909.