In computing, binary translation is a form of binary recompilation where sequences of instructions are translated from a source instruction set (ISA) to a target instruction set with respect to the operating system for which the binary was compiled. In some cases, such as instruction set simulation, the target instruction set may be the same as the source instruction set, providing testing and debugging features such as instruction tracing, conditional breakpoints and hot spot detection.
The two main types are static and dynamic binary translation. Binary translation is commonly implemented in software using static or dynamic translation techniques.[1]
Motivation
Binary translation can allow software compiled for one instruction set architecture to execute on another without recompiling the original source code, and has been used to migrate existing software between incompatible architectures.[1]
Statically recompiled binaries can avoid the runtime translation overhead incurred by dynamic translation, although the performance of a translated program depends on the translator, source and target architectures, and opportunities for optimization. This is similar to the difference in performance between interpreted and compiled programs in general.[1]
Static binary translation
A translator using static binary translation aims to convert the code of an executable file into code that runs on the target architecture and platform without having to run the code first, as is done in dynamic binary translation. This can be very difficult to do correctly, since not all code can be discovered by the translator. For example, some parts of the executable may be reachable only through indirect branches, whose value is known only at run-time.[2]
One such static binary translator uses universal superoptimizer peephole technology (developed by Sorav Bansal and Alex Aiken from Stanford University) to perform efficient translation between possibly many source and target pairs, with considerably low development costs and high performance of the target binary. In experiments of PowerPC-to-x86 translations, some binaries even outperformed native versions, but on average they ran at two-thirds of native speed.[3]
Examples for static binary translations
In the 1960s Honeywell provided a program called the Liberator for their Honeywell 200 series of computers; it could translate programs for the IBM 1400 series of computers into programs for the Honeywell 200 series.[4]
In 1995 Norman Ramsey at Bell Communications Research and Mary F. Fernandez at Department of Computer Science, Princeton University developed The New Jersey Machine-Code Toolkit that had the basic tools for static assembly translation.[5]
In 2004 Scott Elliott and Phillip R. Hutchinson at Nintendo developed a tool to generate "C" code from Game Boy binary that could then be compiled for a new platform and linked against a hardware library for use in airline entertainment systems.[6]
In 2014, an ARM architecture version of the 1998 video game StarCraft was generated by static recompilation and additional reverse engineering of the original x86 version.[7][8] The Pandora handheld community was capable of developing the required tools[9] on their own and achieving such translations successfully several times.[10][11]
Another example is the NES-to-x86 statically recompiled version of the videogame Super Mario Bros. which was generated under usage of LLVM in 2013.[12]
For instance, a successful x86-to-x64 static recompilation was generated for the procedural terrain generator of the video game Cube World in 2014.[13]
Dynamic binary translation
Dynamic binary translation (DBT) translates binary code during program execution. A common implementation translates source code in units such as basic blocks and stores the generated target code in a code cache so that previously translated blocks can be reused.[14]
Dynamic binary translation differs from simple emulation because translated target instructions can subsequently execute directly from the code cache. Translation itself imposes a run-time cost, and DBT systems attempt to amortize this overhead by reusing translated code, particularly for frequently executed regions.[14]
More advanced dynamic translators employ dynamic recompilation, using execution information to identify frequently executed regions and apply additional optimization. This approach is similar to just-in-time compilation, although binary translators operate on already compiled machine code rather than source code or a language-level intermediate representation.
Examples for dynamic binary translations in software
- Apple Computer implemented a dynamic translating emulator for M68K code in their PowerPC line of Macintoshes,[15] which achieved a very high level of reliability, performance and compatibility (see Mac 68K emulator). This allowed Apple to bring the machines to market with only a partially native operating system, and end users could adopt the new, faster architecture without risking their investment in software. Partly because the emulator was so successful, many parts of the operating system remained emulated. A full transition to a PowerPC native operating system (OS) was not made until the release of Mac OS X (10.0) in 2001. (The Mac OS X "Classic" runtime environment continued to offer this emulation capability on PowerPC Macs until Mac OS X 10.5.)
- Mac OS X 10.4.4 for Intel-based Macs introduced the Rosetta dynamic translation layer to ease Apple's transition from PPC-based hardware to x86. Developed for Apple by Transitive Corporation, the Rosetta software is an implementation of Transitive's QuickTransit solution.
- QuickTransit during its product lifespan also provided SPARC→x86, x86→PowerPC and MIPS→Itanium 2 translation support.
- DEC achieved similar success with its translation tools to help users migrate from the CISC VAX architecture to the Alpha RISC architecture.[citation needed]
- HP ARIES (Automatic Re-translation and Integrated Environment Simulation) is a software[16] dynamic binary translation system that combines fast code interpretation with two phase dynamic translation to transparently and accurately execute HP 9000 HP-UX applications on HP-UX 11i for HPE Integrity Servers.[17] The ARIES fast interpreter emulates a complete set of non-privileged PA-RISC instructions with no user intervention. During interpretation, it monitors the application's execution pattern and translates only the frequently executed code into native Itanium code at runtime. ARIES implements two phase dynamic translation, a technique in which translated code in first phase collects runtime profile information which is used during second phase translation to further optimize the translated code. ARIES stores the dynamically translated code in memory buffer called code cache. Further references to translated basic blocks execute directly in the code cache and do not require additional interpretation or translation. The targets of translated code blocks are back-patched to ensure execution takes place in code cache most of the time. At the end of the emulation, ARIES discards all the translated code without modifying the original application. The ARIES emulation engine also implements Environment Emulation which emulates an HP 9000 HP-UX application's system calls, signal delivery, exception management, threads management, emulation of HP GDB for debugging, and core file creation for the application.
- DEC created the FX!32 binary translator for converting x86 applications to Alpha applications.[15]
- Sun Microsystems' Wabi software included dynamic translation from x86 to SPARC instructions.
- In January 2000, Transmeta Corporation announced a novel processor design named Crusoe.[18][19] From the FAQ[20] on their web site,
The smart microprocessor consists of a hardware VLIW core as its engine and a software layer called Code Morphing software. The Code Morphing software acts as a shell […] morphing or translating x86 instructions to native Crusoe instructions. In addition, the Code Morphing software contains a dynamic compiler and code optimizer […] The result is increased performance at the least amount of power. […] [This] allows Transmeta to evolve the VLIW hardware and Code Morphing software separately without affecting the huge base of software applications.
- Intel Corporation developed and implemented an IA-32 Execution Layer - a dynamic binary translator designed to support IA-32 applications on Itanium-based systems, which was included in Microsoft Windows Server for Itanium architecture, as well as in several flavors of Linux, including Red Hat and Suse. It allowed IA-32 applications to run faster than they would using the native IA-32 mode on Itanium processors.
- Dolphin (an emulator for the GameCube/Wii) performs JIT recompilation of PowerPC code to x86 and AArch64.
- Microsoft Virtual PC supports binary translation for 32-bit guest operating systems.
- VMware Workstation 12 or earlier are known to support binary translation for 32-bit guest operating systems.
Examples for dynamic binary translations in hardware
- Nvidia Tegra K1 Denver translates ARM instructions over a slow hardware decoder to its native microcode instructions and uses a software binary translator for hot code.[citation needed]
See also
References
- 1 2 3 Cifuentes, Cristina; Malhotra, Vishv Mohan (1996). "Binary translation: static, dynamic, retargetable?". Proceedings of the International Conference on Software Maintenance. pp. 340–349. doi:10.1109/ICSM.1996.565037.
- ↑ Shen, Bor-Yeh; Hsu, Wei-Chung; Yang, Wuu (2014). "A Retargetable Static Binary Translator for the ARM Architecture". ACM Transactions on Architecture and Code Optimization. 11 (2). doi:10.1145/2629335.
- ↑ Bansal, Sorav; Aiken, Alex (December 2008). "Binary Translation Using Peephole Superoptimizers" (PDF). Proceedings of the 8th USENIX conference on Operating systems design and implementation. pp. 177–192.
- ↑ Honeywell Series 200 Summary Description (PDF). Honeywell. February 1966. p. 11.
For example, the instruction repertoire of Series 200 processors is similar enough to those of several other processing systcms, viz., the IBM 1400 series, to allow automated, one-time translation of programs written for these competitive systems to a form suitable for execution on higher-performance Series 200 systems.
- ↑ Ramsey, Norman; Fernandez, Mary F. (1995). "The New Jersey Machine-Code Toolkit". Proceeding TCON'95 Proceedings of the USENIX 1995 Technical Conference Proceedings. USENIX Association Berkeley, CA, USA. p. 24.
- ↑ US 7765539, Elliott, Scott & Hutchinson, Phillip, "System and method for trans-compiling video games", issued 2010
- ↑ Steinlechner, Peter (2014-03-10). "Starcraft für ARM-Handheld kompiliert" (in German). golem.de. Retrieved 2014-03-25.
- ↑ notaz (2014-03-04). "StarCraft". repo.openpandora.org. Retrieved 2014-03-26.
- ↑ notaz (2014-03-01). "ia32rtools/". GitHub. Retrieved 2015-01-09.
- ↑ notaz (2014-03-04). "Starcraft". openpandora.org. Retrieved 2014-03-29.
The "no source, no port" rule is not completely true, you can get something similar (but not the same) as a port through static recompilation. Similar stuff was done several times by M-HT for some DOS games. The game was also converted for Android with somewhat similar approach.
- ↑ M-HT. "Warcraft: Orcs & Humans". repo.openpandora.org.
- ↑ Kelley, Andrew (2013-07-07). "Statically Recompiling NES Games into Native Executables with LLVM and Go". Retrieved 2013-08-08.
This article presents original research regarding the possibility of statically disassembling and recompiling Nintendo Entertainment System games into native executables.
- ↑ Kærlev, Mathias (2014-04-14). "Practical and Portable X86 Recompilation". Retrieved 2014-08-08.
but then the idea of somehow using the original x86 machine code presented itself. However, for our open server, we need to support x86-64 as well, and in that case, we absolutely need emulation or recompilation. […] Static recompilation to assembler seemed like a much better option, but to keep it portable, we would need to write backends for x86, x86-64, and possibly ARM/PowerPC.
- 1 2 Wang, Wenwen; Yew, Pen-Chung; Zhai, Antonia; McCamant, Stephen (2016). "A General Persistent Code Caching Framework for Dynamic Binary Translation (DBT)". 2016 USENIX Annual Technical Conference. USENIX Association. pp. 591–603.
- 1 2 Wharton, John Harrison (1994-08-01). "Gary Kildall, industry pioneer, dead at 52: created first microcomputer languages, disk operating systems". Microprocessor Report. 8 (10). MicroDesign Resources Inc. (MDR). Archived from the original on 2016-11-18. Retrieved 2016-11-18.
[…] Ironically, many of the techniques Gary pioneered are being rediscovered now, ten years later. Apple and DEC are touting binary recompilation as a "new" technology for porting existing software to the PowerPC or Alpha architecture. Actually, DRI introduced an 8080-to-8086 binary recompiler in the early 1980s. […]
- ↑ Carlson, Jim; Huck, Jerry (2003). Itanium Rising: Breaking Through Moore's Second Law of Computing Power. Prentice Hall PTR. ISBN 978-0-13046415-6. Retrieved 2015-01-09.
- ↑ "HP ARIES Dynamic Binary Translator". HP. Archived from the original on 2015-01-10. Retrieved 2015-01-09.
- ↑ Stokes, Jon. "Transmeta Crusoe Explored". Ars Technica. Retrieved 2015-01-09.
- ↑ Hughes, Rob (2000-01-20). "Transmeta's Crusoe Microprocessor". geek.com. Archived from the original on 2007-09-27.
- ↑ "Transmeta Crusoe Processor Frequently Asked Questions FAQ". Transmeta. 2007. Archived from the original on 2007-01-10.
Further reading
- Haber, Gadi (2010). "Introduction to Binary Translation" (PDF). Intel. Archived from the original (PDF) on 2016-03-09. Retrieved 2014-03-30.
- Bansal, Sorav; Aiken, Alex (December 2008). "Binary Translation Using Peephole Superoptimizers". Department of Computer Science and Engineering. Indian Institute of Technology Delhi. Retrieved 2014-03-30.
- Baraz, Leonid; Devor, Tevi; Etzion, Orna; Goldenberg, Shalom; Skaletsky, Alex; Wang, Yun; Zemach, Yigal (2003). "IA-32 Execution Layer: a two-phase dynamic translator designed to support IA-32 applications on Itanium-based systems". Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture. MICRO 36. Washington, DC, USA: IEEE Computer Society. pp. 191–. ISBN 978-0-7695-2043-8.
- Toal, Graham. "An Emulator Writer's HOWTO for Static Binary Translation".
- Chernoff, Anton; Herdeg, Mark; Hookway, Ray; Reeve, Chris; Rubin, Norman; Tye, Tony; Yadavalli, S. Bharadwaj; Yates, John (1998). "FX!32: A Profile-Directed Binary Translator". IEEE Micro. 18 (2): 56–64. doi:10.1109/40.671403. ISSN 0272-1732.
- Souza, Maxwell; Nicácio, Daniel; Araújo, Guido (2010-06-23) [2010-06-19]. ISAMAP: Instruction Mapping Driven by Dynamic Translation. Computer Architecture - ISCA 2010 International Workshops. Saint-Malo, France. pp. 117–. ISBN 9783642243226.
- Chen, Yu-hsin (2009-06-20) [2009-06-18]. "Dynamic Binary Translation from x86-32 code to x86-64 code for Virtualization" (PDF). Massachusetts Institute of Technology.