GSM: An Efficient Code Generation Algorithm for Dynamic Binary Translator

Dynamic binary translation is an effective way to address binary compatibility problem. Embedded systems and other novel RISC ISAs are developing fast without consideration of the binary compatibility with off-the-shelf x86 applications, making dynamic binary translator (DBT) from CISC to RISC more important. However, dynamic code generation is still inefficient due to the code expansion. Conventional code generators in DBTs use one-to-many mapping scheme between source and target code which cannot take full advantage of the target ISA. We propose a novel lightweight code generation algorithm GSM (Greedy Sub graph Mapping), which can generate compact code with low overhead using many-to-one mapping. GSM is implemented and evaluated in a DBT prototype system called TransARM. Experimental results demonstrate that GSM generates higher quality target code compared to a conventional implementation, which brings code expansion rate close to 1.3. Moreover, GSM causes slightly extra overhead and negligible slowdown of translation, and enables 10% performance improvement for target code execution.