Related Work on Binary Translation Software

4.8Related Work on Binary Translation Software

The original version of IBM DAISY [41] used a single-stage translation system that translated all PowerPC (architected ISA) instructions in a given physical page when an untranslated code page was executed . This pioneering work addressed the issues of precise exceptions, and page and address mapping mechanisms to maintain 100% architecture compatibility. Later versions of IBM DAISY [3, 42] adopted an adaptive/staged translation strategy, i.e. first interpret PowerPC instructions before they reach certain threshold. Once the hot threshold is reached, a hotspot is identified and a translation unit, tree region/group, is formed, followed by optimizing translation.

The Transmeta Crusoe processor [54, 82] also uses staged emulation with a software interpreter first emulating x86 code, followed by translation and optimization of hotspots. The initial interpretation process also performs software online profiling. Each code region is interpreted multiple times up to a given threshold, and then translation to native VLIW code is performed. The Crusoe Code Morphing Software [36] systematically addressed the issue of x86 self-modifying and self-referencing code, which are quite frequent in x86 device drivers, legacy software, and security related software. The CMS system features specific approaches for different scenarios to maintain efficiency and 100% compatibility.

The Transmeta Efficeon processor emloys a unique 4-stage translation strategy (including the initial interpretation [83]) to reach the right level of optimization for different code regions. The translation unit is a tree region.

All the discussed IBM and Transmeta co-designed virtual machines happened to use VLIW engines as the co-designed microarchitecture. With the in-order VLIW approach, considerable software optimizations are required for scheduling/reordering instructions, especially if speculation is implemented via the instruction set [70]. The optimization overhead for VLIW engines are quite heavy, 4000+ native operation per PowerPC [41]. The data for Transmeta CMS is estimated to be similar. The Transmeta processors provide checkpoint and fenced store-buffer mechanisms to support such reordering.

Of course, the processor for a co-designed VM does not necessarily have to be a VLIW. The co-designed ILDP (Instruction Level Distributed Processing) VM [76, 78] explored translation algorithms for its superscalar-like processor. In that approach, the DBT software forms strands (chains of dependent instructions) for a co-designed ILDP microarchitecture. As with our macro-op execution engine, the ILDP processor microarchitecture is fully capable of dynamic instruction scheduling. For such out-of-order architectures, the optimization software is anticipated to be significantly simpler than that for the VLIW implementations.

Besides those that use the co-designed VM paradigm, there are other VM systems that emulate program binaries. These systems run software distributed in source ISA on top of target ISA platforms. The interface these VM systems handle is ABI (Application Binary Interface), which includes user-mode part of the source and target ISA(s), OS system calls and certain exceptions.

The Intel IA-32 EL [15], for example, dynamically translates x86 instructions into IA-64 [70] VLIW instructions on-the-fly for user-mode code only. IA-32 EL is a two-stage translation system that does not interpret. All x86 code is translated (when first executed) with a simple and fast BBT translator. The BBT translator instruments its translations to collect execution profiles. The BBT translator also applies certain rules when generating code so that the precise state can be recovered easily should an exception occurs anywhere within the basic block translation. For example, for each x86 instruction, no x86 architected state is modified until all operations performed by the instruction finish without exception. Later, after hot code is detected, a heavy-duty optimizing translator is applied to generate optimized code for the target Intel IPF processors.

The DEC FX!32 [24, 60] implements a high performance x86 interpreter and a profile-guided static binary translator for running the x86 Windows applications on DEC Alpha Windows platforms. The interpretation overhead is rather low for the x86 – less than 50 Alpha instructions per x86 instruction. To strive for performance, FX!32 does not maintain intrinsic binary compatibility. For example, it does not emulate x87 floating point faithfully, and it cannot materialize the precise x86 state at an arbitrary point within its translation.

There are also binary translators for RISC ISAs, for example, PA-RISC to IA-64 [130], VEST/ TIE for Alpha and mx for MIPS [113]. RISC instruction sets have much lower software decode and interpretation overhead when compared with a CISC instruction set such as the x86.

References [4, 5] provide excellent surveys regarding the state-of-the-art of dynamic binary translation and important issues such as precise exception handling. Le [85] shows how to extend register live range to support precise exception handling for out-of-order scheduling in DBT.