Binary translation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computing, binary translation (or (binary) recompilation) is the emulation of one instruction set by another through translation of binary code. Sequences of instructions are translated from the source to the target instruction set. 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 trace, conditional breakpoints and hot spot detection.

The two main types are static and dynamic binary translation. Translation can be done in hardware (for example, by circuits in a CPU) or in software (e.g. run-time engines, statical recompiler, emulators).

Motivation[edit]

Motivation for using the complex process of binary translation is either that a compilation of the source code to the destination platform or instruction set is not available (or technically problematic) or when the source code is plainly not available anymore (Abandonware).

Performance wise static recompilations have the potential to achieve a better performance than real emulation approaches as in optimal case one overhead introducing interface is removed.

Static binary translation[edit]

A translator using static binary translation aims to convert all of the code of an executable file into code that runs on the target architecture without having to run the code first, as is done in dynamic binary translation. This is very difficult to do correctly, since not all the 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.

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.

Examples for static binary translations[edit]

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.[1][2] The Pandora handheld community was capable of developing the required tools on their own and achieving such translations successfully several times.[3][4]

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.[5]

For instance, a successful x86-to-x64 statical recompilation was generated for the procedural terrain generator of the video game Cube World in 2014.[6]

Dynamic binary translation[edit]

Dynamic binary translation looks at a short sequence of code—typically on the order of a single basic block—then translates it and caches the resulting sequence. Code is only translated as it is discovered and when possible, and branch instructions are made to point to already translated and saved code (memoization).

Dynamic binary translation differs from simple emulation (eliminating the emulator's main read-decode-execute loop—a major performance bottleneck), paying for this by large overhead during translation time. This overhead is hopefully amortized as translated code sequences are executed multiple times.

More advanced dynamic translators employ dynamic recompilation where the translated code is instrumented to find out what portions are executed a large number of times, and these portions are optimized aggressively. This technique is reminiscent of a JIT compiler, and in fact such compilers (e.g. Sun's HotSpot technology) can be viewed as dynamic translators from a virtual instruction set (the bytecode) to a real one.

Examples for dynamic binary translations in software[edit]

  • Apple Computer implemented a dynamic translating emulator for M68K code in their PowerPC line of Macintoshes, 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 OS X "Classic" runtime environment continued to offer this emulation capability on PowerPC Macs until OS X 10.5.)
  • HP ARIES (Automatic Re-translation and Integrated Environment Simulation) is a software[7] 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 HP Integrity servers.[8] 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.
  • In January 2000, Transmeta Corporation announced a novel processor design named Crusoe.[9][10] From the FAQ[11] 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.

Examples for dynamic binary translations in hardware[edit]

See also[edit]

References[edit]

  1. ^ Steinlechner, Peter (March 10, 2014). "Starcraft für ARM-Handheld kompiliert" (in German). golem.de. Retrieved March 25, 2014. 
  2. ^ notaz (March 4, 2014). "StarCraft". repo.openpandora.org. Retrieved March 26, 2014. 
  3. ^ notaz (March 4, 2014). "Starcraft". openpandora.org. Retrieved March 29, 2014. 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. 
  4. ^ "Warcraft: Orcs & Humans". repo.openpandora.org. 
  5. ^ 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. 
  6. ^ 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. 
  7. ^ Itanium Rising: Breaking Through Moore's Second Law of Computing Power by Jim Carlson, Jerry Huck
  8. ^ "HP ARIES Dynamic Binary Translator". HP. 
  9. ^ Stokes, Jon. "Transmeta Crusoe Explored". Ars Technica. 
  10. ^ Hughes, Rob (January 20, 2000). "Transmeta's Crusoe Microprocessor". geek.com. Archived from geek.com the original on April 17, 2008. 
  11. ^ FAQ

Further reading[edit]