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

Abstract: 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 application, 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 generate 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.

Key words: binary translation, data flow graph (DFG), subgraph covering, code generation