
\chapter{Previous Work}
\label{ch-prevwork}

{\small
\begin{flushright}
Documentation: Cristina [c.1996, 2001]
\end{flushright} 
}

Binary translation is a relatively new field of research, were the
techniques are derived from the compilation, emulation and decompilation areas. 
Nevertheless, the techniques are ad hoc in nature and little has been 
published about them (mainly driven by commercial interests of the parties
involved).  

In this chapter we describe the related work, which we have classified
into two main groups: works related to binary translation and interpreters 
(or emulators), and works related to binary-code manipulation tools that 
may aid in the process.


\section{Binary translators and interpreters} 
Binary translation techniques were developed from emulation
techniques at research labs in the late 1980s.  Projects
like the HP3000 emulation on HP Precision Architecture
computers~\cite{Berg87} and MIMIC, an IBM System/370 simulator on an
IBM RT (RISC) PC~\cite{May87} were the catalist for these techniques.
One of the goals of the HP project was to run existing MPE V binaries
on the new MPE XL operating system.  For this purpose, a compatibility
mode environment was provided, which was composed of two systems:
a HP 3000 emulator and a HP 3000 object code translator.  The emulator
duplicated the behavior of the legacy hardware, and the translator
provided efficient translated code which relied on the emulator
when indirect transfers of control where met.

Tandem developed an object code translator for TNS CISC binaries
to TNS/R (RISC) in order to provide a migration path for existing
vendor and user software~\cite{Andr92}.  This approach allowed
them to market their new RISC machines years earlier than if no
migration path was available.  Part of the rationale for the
project was also the fact that no reprogramming was involved and
that the techniques would provide faster code than emulation
techniques.  Less than 1\% of the time was spent on emulation.

Digital developed two translators, VEST and mx, to provide a migration
path from their OpenVMS VAX and Ultrix MIPS systems to their new
Alpha machine~\cite{Site92,Site93}.  Interestingly enough, they
decided to do careful static translation once instead of on-the-fly
dynamic translation at each execution time for performance issues.
In both their translators, the old and new environments were, by
design, quite similar, plus both provided similar operating system
services.  Some of the goals were to take full advantage of the
performance capabilities of the Alpha and avoiding the problem of
not having all the tools available to port a program to a new architecture
(because they are still not available on the new hardware).
This was seen as an interim solution, while the user's environment was
made available on the new machine and then code could be recompiled/rebuilt.

Up to 1992 all translators were made available by hardware                   
manufacturers to provide a migration path from their legacy
hardware platform (normally a CISC) to their new platform
(normally a RISC).

Back in 1994, AT\&T Bell Laboratories provided services to migrate
software in object code form from one platform to another through
the FlashPort binary translator~\cite{Att94}.
Translations of PDP 11, 680x0 and IBM 360 code was made to
platforms like MIPS, RS/6000, PowerPC and SPARC.  Translation
time was based on the type of application, with some large
applications being translated in 1 month, whereas others in
6 months; which means that manual changes were done to assure
consistency of the translation, plus to provide compatibility
libraries to cater for the differences in operating systems and
services.
The FlashPort technology was initially developed by Bell Laboratories
researchers and was commercialized through the 1991-formed Echo
Logic company.  The first production release of the technology
was provided to Apple Computers in 1993 to translate Macintosh
binaries to the then forthcoming PowerPC-based Macintosh computers.

In an attempt to make Alpha machines more appealing to existing
Unix users, Digital released FreePort Express, a SunOS SPARC
static binary translator to Digital Unix Alpha~\cite{Dec95};
particularly at a time when Sun was migrating customers to
their new Solaris OS and discontinuing support for SunOS.
The tool was advertised as a way of migrating to the Alpha even
when source code and compiler tools from the source machine
were not available; then do a native port at your own leisure.
Since the translated programs and libraries provided support for
Xview, OpenLook, Motif and other X11-based applications, this
migration path was suitable for users who did not want to be
trained in the use of new tools.

To improve Alpha's usability as a desktop alternative to Intel
PCs, Digital developed FX!32, an WindowsNT x86 to WindowsNT Alpha
translator~\cite{Thom96,Hook97}.  Emulation was used as it provided
a quick way to provide support for changes in WindowsNT.  However,
binary translation on the background was also used in order to
save the translations to a file and, over time, incrementally
build the new Alpha binary.  This hybrid translator uses profiling
information in order to optimize the code the next time it
is run.

The TIBBIT project looks at real-time applications that are to be
binary translated between processors of different speeds~\cite{Cogs95,Cogs95b}.
The translated software needs to retain the implicit time-dependency
of the old software in order to function correctly.

\begin{table*}[hbtp]
{\footnotesize
\begin{tabular}{|p{1.5cm}|p{1.3cm}|p{0.7cm}|p{5cm}|p{2cm}|p{2cm}|} \hline
Name & Affiliation & Ref & Purpose & Source Platform & Target Platform \\ \hline
Bergh et al (1987) & HP & \cite{Berg87} &
	Software emulation and object code translation. &
	(HP3000, MPE V) &
	(HP Precision Architecture, MPE XL) \\
Mimic (1987) & IBM & \cite{May87} &
	Software emulator with a 1:4 code expansion factor per 
	old machine instruction. &
	IBM System/370 &
	IBM RT PC \\
Johnson (1990) & Stardent & \cite{John90} &
	Postloading optimizations. &
	RISC &
	RISC \\
Bedichek et al (1990) & U.Wash & \cite{Bedi90} &
	Efficient architecture simulation and debugging. &
	Motorola 88000 &
	Motorola 88000 \\
Accelerator (1992) & Tandem & \cite{Andr92}        &
	Static binary translation for CISC to RISC migration.  
	Uses a fallback interpreter.    &
	TNS CISC        &
	TNS/R   \\
VEST, mx (1993) & Digital & \cite{Site93} &
	Static binary translation from Digital's VAX and MIPS machines
	to the 64-bit Alpha.  Uses a fallback interpreter. &
	(VAX, OpenVMS), (MIPS, Ultrix) &
	(Alpha, OpenVMS), (Alpha, OSF/1) \\
Wabi (1994) & Sun & \cite{Sun94} &
	Pretranslated Windows API to Unix API calls.  Dynamic execution of 
	programs. &
	(x86, Windows 3.x) &
	(SPARC, Solaris) \\
Flashport (1994) & AT\&T & \cite{Att94} &
	Binary translation across a variety of source and target platforms.
	Requires human intervention. & 
	680x0 Mac, IBM System/360, 370, 380 &
	PowerMac, IBM RS/6000, SPARC, HP, MIPS, Pentium \\
Shade (1994) & Sun & \cite{Cmel94} &
	Efficient instruction-set simulation and trace generation
	capability.  Dynamic compilation of code. &
	SPARC V8, V9 &
	SPARC V9, V8 \\
MAE (1994) & Apple & \cite{Apple94} &
	Macintosh environment in an XWindow, Unix RISC-based workstation. &
	680x0 &
	RISC-based Unix \\
Wahbe et al (1994) & CMU & \cite{Wahb94} &
	Adaptable binaries.  Binary transformations.&
	(MIPS, Ultrix4.2) &
	(MIPS, Ultrix4.2) \\
Chia (1995) & Purdue & \cite{Chia95} &
	Software emulation within the same platform, with a 1:100 code
	expansion factor per old machine instruction. &
	(SPARC, Solaris) &
	(SPARC, Solaris) \\
TIBBIT (1995) & CMU, UO & \cite{Cogs95,Cogs95b} &
	Binary translation of time-sensitive applications.&
	Motorola 68000 &
	(IBM RS/6000, AIX 3.2) \\
Then (1995) & Purdue & \cite{Then95} &
	Optimization of code within the same platform.&
	(SPARC, Solaris) &
	(SPARC, Solaris) \\
Freeport Express (1995) & Digital & \cite{Dec95} &
	Static binary translation and fallback interpreter.  Translates
	user mode programs. 32-bit to 64-bit translation. &
	(SPARC, SunOS4.1.x) &
	(Alpha, OSF/1) \\
FX!32 (1996) & Digital & \cite{Thom96,Hook97} &
	Hybrid emulator/binary translator of popular x86 32-bit applications 
	to Alpha.   &
	(x86, WindowsNT) &
	(Alpha, WindowsNT) \\
\hline
\end{tabular}
\caption{\label{tab-bintrans} {Summary of Binary Translators and
	Interpreters in Cronological Order.}}}
\end{table*}

We summarize the features of a variety of binary translators and
interpreters in Table~\ref{tab-bintrans}.  The column {\em Purpose\/} 
describes the general use of the tool, columns {\em Source Platform\/}
and {\em Target Platform\/} describe the nature of the translation supported
by the tool (i.e. multi-platform or within the one platform), 
column {\em Name\/} refers to the name of the software; if unnamed, then
it refers to the people that worked on it, and column {\it Affiliation}
refers to the affiliation of the authors of the software at the time
of development. 


\subsection{List of recent translators}
There has been a lot of work in the last few years (1998-2000) 
on dynamic techniques for doing binary manipulation of one sort of 
another.  The following is a list of projects and literature available: 

\begin{itemize}
\item HP Aries~\cite{Zhen00}: 
Aries is a hybrid interpreter/dynamic translator which
allows PA/RISC HP-UX binaries to run in an IA-64 HP-UX
environment transparently, without user intervention.

\item HP Labs Dynamo~\cite{Bala00}: 
Dynamo is a dynamic reoptimizer of PA-RISC binaries which
produces PA-RISC code.  It works well for some programs 
and not for others. 

\item IBM TJ Watson Research Center's DAISY~\cite{Ebci96} and 
BOA~\cite{Gsch00}: 
The DAISY and BOA projects have looked at dynamic binary translation 
from conventional architectures such as the PowerPC to VLIW or other
novel architectures.  Their work addresses precise exceptions, 
self-modifying code, and reordering of memory references; all of 
these from an architectural point of view. 

\item Transmeta's Crusoe~\cite{Gepp00}: 
The Crusoe chip is a VLIW chip which includes code morphing to 
dynamically binary translate from x86 to the VLIW instruction set. 
Some x86 instructions are supported by the hardware itself. 

\item Compaq's Wiggins/Redstone~\cite{Reev00}: 
Wiggins/Redstone was a dynamic reoptimizer of Alpha binary code. 
It was built based on Digital's DCPI infrastructure.  

\end{itemize}



\section{Binary-code manipulation tools}

\begin{table*}[hbtp]
{\small
\begin{tabular}{|p{2.0cm}|p{0.7cm}|p{7.8cm}|p{3.0cm}|} \hline
Name & Ref & Purpose & Platform \\ \hline
Silberman et al (1993) & \cite{Silb93} &
	Framework for supporting heterogeneous instruction set architectures. &
	CISC, RISC, VLIW \\
QPT (1994) & \cite{Laru94} &
	Rewrite executable files to measure program behavior. &
	MIPS, SPARC \\
Shade (1994) & \cite{Cmel94} &
	Execution profiling of application binaries. &
	SPARC V8, V9 \\
ATOM (1994) & \cite{Dec94,Eust95} &
	Sytem for building customized program analysis tools. &
	(DecStation, Ultrix), (Alpha, OSF/1) \\
NJMC (1994) & \cite{Rams95,Rams94,Rams97} & 
	Machine-independent encoding and decoding of machine instructions
	via the SLED language. &
	MIPS, SPARC, x86, PowerPC, Alpha \\
EEL (1995) & \cite{Laru95} &
	Library for editing binaries. &
	MIPS, SPARC \\
\hline
\end{tabular}
\caption{\label{tab-bintools} {Summary of Binary-code Manipulation  
	Tools in Cronological Order.}}
}
\end{table*}

Table~\ref{tab-bintools} summarizes the available tools for handling
machine binary code.  The column \emph{Name} lists the name of the
tool (or its author if no name was given to the tool), column 
\emph{Ref} lists the references in the literature to this tool,
column \emph{Purpose} describes the purpose of the tool, and column 
\emph{Platform} lists the platform(s) supported by these tools. 

ATOM is a tool-building system that provides a flexible and efficient
interface for the instrumentation of code and has been used for the
construction of an instruction profiler, cache simulator and compiler
auditing tool~\cite{Eust95}.  The user needs to write an instrumentation
file in terms of ATOM's abstractions (procedures and basic blocks),
and an analysis file (using a high-level language such as C) with the 
routines that are to be included for instrumentation purposes.  
The performance of the generated tools compare favourably with 
hand-crafted implementations of same the tools. 

Shade is an instruction-set simulator which optionally allows users to 
profile code that traces the execution of an application at runtime.  
Trace information on instruction addresses, instruction text, decoded
opcode values, and more can be collected by Shade~\cite{Cmel94}.
This tool works only on SPARC machines.

Both NJMC (New Jersey Machine-Code) toolkit~\cite{Rams95,Rams97} and EEL
(Executable Editing Library)~\cite{Laru95} provide support for
manipulating machine instructions.  The NJMC toolkit supports the 
encoding and decoding of machine instructions for a variety of 
RISC and CISC machines, by means of SLED specifications.  
The SLED language allows for the description of the syntax of machine 
instructions in a specification that resembles instruction descriptions 
found in architecture manuals.
The toolkit has successfully been used in a retargetable 
linker~\cite{Fern95} and a retargetable debugger~\cite{Rams92}.  
The EEL library was built based on the NJMC machine specifications, 
and introduced control flow support based on techniques developed in 
the QPT~\cite{Laru94} profiler.  EEL also introduced limited
support for describing the semantics of machine instructions.
The tool is not fully portable to non RISC environments.


