二进制翻译中代码生成的子图覆盖算法

Subgraph Covering for Efficient Code Generation in Binary Translation

二进制翻译技术能够有效解决二进制兼容问题,促进新型体系结构的发展,也是虚拟机技术的重要组成部分,具有重要的研究和应用价值,但是其效率仍然有待提升,特别是目标代码生成的效率。设计了一种高效的目标代码生成算法——代码生成的子图覆盖算法(subgraph covering for code generation,SCCG),能够以尽可能少的代价生成精简的目标代码。该算法应用数据流图对二进制代码中的基本块进行建模,获取指令间的数据相关,并采用基于子图覆盖的贪心算法得到目标代码。在TransARM原型系统中进行了实现和测试,结果表明该算法获得了更优质的目标代码,并且成本得到了有效控制。

As an efficient way to solve binary compatibility problem, binary translation can promote the development of novel architecture, and is an important part of virtual machine. Although it has great value in research and appli- cation, its efficiency is a bottleneck, especially the efficiency of its target code generation procedure. This paper designs an efficient code generation algorithm -- subgraph covering for code generation （SCCG）, which can gen- erate reduced code with as less cost as possible. It employs data flow graph （DFG） to model basic blocks in binary code and find the dependency between instructions, and applies a greedy algorithm based on subgraph covering to obtain target code. This algorithm is implemented and tested in TransARM prototype system, the results show that it obtains better target code and limits its cost well.