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

Subgraph Covering for Efficient Code Generation in Binary Translation

作　　者：陈顼颢[1] 郑重[1] 沈立[1] 王志英[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机科学与探索》2011年第7期613-623,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.60803041;国家重点基础研究发展规划(973)No.2007CB310901;国防科技大学优秀研究生创新项目No.S090606~~

摘　　要：二进制翻译技术能够有效解决二进制兼容问题,促进新型体系结构的发展,也是虚拟机技术的重要组成部分,具有重要的研究和应用价值,但是其效率仍然有待提升,特别是目标代码生成的效率。设计了一种高效的目标代码生成算法——代码生成的子图覆盖算法(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.

关 键 词：二进制翻译 数据流图(DFG) 子图覆盖 代码生成 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]