ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (9): 1931-1944.doi: 10.7544/issn1000-1239.2017.20151110

• 软件技术 • 上一篇    下一篇

二进制翻译中冗余指令优化算法

谭捷,庞建民,单征,岳峰,卢帅兵,戴涛   

  1. (数学工程与先进计算国家重点实验室 郑州 450002) (jessie_tanjie@hotmail.com)
  • 出版日期: 2017-09-01
  • 基金资助: 
    国家自然科学基金项目(61472447);国家“八六三”高技术研究发展计划基金项目(2009AA012201);“核高基”国家科技重大专项基金项目(2009ZX01036-001-001)

Redundant Instruction Optimization Algorithm in Binary Translation

Tan Jie, Pang Jianmin, Shan Zheng, Yue Feng, Lu Shuaibing, Dai Tao   

  1. (State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450002)
  • Online: 2017-09-01

摘要: 二进制翻译是实现软件移植的主要方法.动态二进制翻译受动态执行限制而不能深度优化导致效率较低而传统的静态二进制翻译难以处理间接分支,且现有的优化方法大部分集中在中间代码层,对目标码中存在的大量冗余指令较少关注.针对这一现状,提出一种静态二进制翻译框架SQEMU,基于该框架提出了一种对目标码冗余指令进行删除的优化算法.该算法通过分析目标码生成指令特定数据依赖图(instruction-specific data dependence graph, IDDG),再利用该图将活性分析和窥孔优化的2种理论相结合,有效删除目标码中的冗余指令.实验结果表明,利用该算法对目标码优化后,其执行效率得到显著提升,最大提升可达42%,整体性能测试表明,优化后nbench测试集翻译效率提高约20%,SPEC CINT2006测试集翻译效率提高约17%.

关键词: 二进制翻译, 冗余指令, 活性分析, 窥孔优化, SQEMU框架

Abstract: Binary translation is a main method to implement software migration. Dynamic binary translation is limited by dynamic execution and cannot be deeply optimized, resulting in low efficiency. Traditional static binary translation has difficulty to deal with indirect branch, and conventional optimization methods mostly affect in the intermediate code layer, paying less attention to a large number of redundant instructions that exist in the target code. According to this situation, this paper presents a static binary translation framework SQEMU and a target code optimization algorithm to delete redundant instructions based on the framework. The algorithm generates an instruction-specific data dependence graph(IDDG) based on the analysis of target codes, then combines liveness analysis with peephole optimization using IDDG, and effectively removes redundant instructions in target codes. Experimental results show that using the optimization algorithm for target codes, the execution efficiency is significantly increased, the maximal increase up to 42%, and the overall performance test shows that the optimized translation efficiency of nbench is increased by about 20% on average, and it is increased about 17% of SPEC CINT2006 on average.

Key words: binary translation, redundant instruction, liveness analysis, peephole optimization, SQEMU frame

中图分类号: