
\chapter{Results}
\label{ch-results}

{\small
\begin{flushright}
Documentation: Cristina, Mike [Sep 99]
\end{flushright}
}

This chapter provides current preliminary results in the use of
the \uqbt\ framework in 5 instantiations of the framework. 
The results were reported in 1999 at the Workshop on 
Binary Translation, Oct 99, and have not been updated since. 

After these results were reported, there has been progress
such that all the SPARC to SPARC and Pentium to SPARC tests in
the distribution file \texttt{test/regression.test} pass. Note 
that some of these passes are in fact rather forced---in some 
cases the generated C code is edited with a sed script. 
These are all due to limitations that we acknowledge, and which 
could be fixed if and when some things get implemented, such as 
endianness analysis for library function parameters. Of the Spec95 
integer benchmarks, only \texttt{compress} and \texttt{go} actually 
translate correctly, as far as we know, and only \texttt{compress} 
translates Pentium to SPARC. We have attempted to translate a few others, 
but it's tedious work due to lack of better debugging infrastructure. 
This illustrates the need for a debugging system, as discussed
elsewhere.

The following translators were used for experimentation and 
data collection: 

\begin{itemize}
\item uqbtss: static SPARC to SPARC
\item uqbtsp: static SPARC to Pentium
\item uqbtps: static Pentium to SPARC
\item uqbtpp: static Pentium to Pentium
\item uqbtsj: static SPARC to Java bytecode
\end{itemize}

A SPARC to SPARC and a Pentium to Pentium translators are useful
to test the adequacy of the internal representation, as translated
programs should not slow down when translating from machine M to 
machine M using the same optimizer compiler.  
Further, as seen in the results in this section, a binary translator 
can be used as an optimizer of binary code.  

The UQBT framework currently decodes and partially analyzes 
SPEC95 benchmark programs, such as compress, ijpeg, and gcc.
The largest of such programs is gcc with 1Mb of binary code (1.6Mb 
executable on SPARC and 1.2Mb on Pentium).
Our type analysis implementation is not complete, therefore we
currently only translate programs that take integer and pointer to
data parameters.
This limits the size of the programs that can currently be translated 
to the ones presented in Figure~\ref{fig-results}.
Further, our resourceable interpreter is not fully implemented yet,
hence we do not support programs that require runtime interpretation.
This has not been a problem for the programs presented herein, but
will be required for larger programs.

\begin{figure*}[htp]
{\small
\begin{minipage}[b]{\linewidth}
\begin{center}
\begin{tabular}{|r|r|r|r|r|} \hline
        & \multicolumn{2}{c|}{Translated Code} &
        \multicolumn{2}{c|}{Native Code} \\
Program & gcc opt & cc opt & -O0 & -O4 \\ \hline
Fibo(40) sec & 18.2  & 21.3 & 41.0  & 23.0 \\
       bytes & 24,924  & 6,700 & 24,628 & 24,564 \\ \hline
Sieve(3000) sec & 23.7 & 24.1 & 29.3 & 24.5 \\
       bytes & 24,732 & 6,316 & 24,552 & 24,452 \\ \hline
Mbanner(500K) sec & 25.8 & 22.2 & 63.7 & 26.6\\
       bytes & 30,500 & 12,248 & 30,652 & 30,268 \\ \hline
\end{tabular}
\end{center}
%\vspace*{0.1cm} 
\center{Static SPARC to SPARC Translation}
\end{minipage}\hfill
\vspace*{0.4cm}

\begin{minipage}[b]{\linewidth}
\begin{center}
\begin{tabular}{|r|r|r|r|r|} \hline
        & \multicolumn{2}{c|}{Translated Code} &
        \multicolumn{2}{c|}{Native Code} \\
Program & gcc opt & cc opt & -O0 & -O4 \\ \hline
Fibo(40) sec & 23.0 & 24.3 & 41.0 & 23.0 \\
       bytes & 24,916 & 6,680 & 24,628 & 24,564 \\ \hline
Sieve(3000) sec & 26.9 & 23.9 & 29.3 & 24.5 \\
       bytes & 24,776 & 6,312 & 24,552 & 24,452 \\ \hline
Mbanner(500K) sec & 53.3 & 36.9 & 63.7 & 26.6 \\
       bytes & 34,188 & 21,448 & 30,652 & 30,268 \\ \hline
\end{tabular}
\end{center}
%\vspace*{0.1cm} 
\center{Static Pentium to SPARC Translation}
\end{minipage}\hfill
\vspace*{0.4cm}

\begin{minipage}[b]{\linewidth}
\begin{center}
\begin{tabular}{|r|r|r|r|r|} \hline
        & \multicolumn{2}{c|}{Translated Code} &
        \multicolumn{2}{c|}{Native Code} \\
Program & gcc opt & cc opt & -O0 & -O4 \\ \hline
Fibo(40) sec & 27.7 & 28.5 & 28.6 & 25.9 \\
       bytes & 16,512 & 7,292 & 16,144 & 16,152 \\ \hline
Sieve(3000) sec & 17.8 & 17.4 & 18.9 & 18.6 \\
       bytes & 16,244 & 6,548 & 15,964 & 15,944 \\ \hline
Mbanner(500K) sec & 42.5 & n/a & 80.5 & 44.8 \\
       bytes & 22,240 & & 21,524 & 25,436 \\ \hline
%~\footnote{4,096 bytes added to executable to adjust data page size} \\ \hline
\end{tabular}
\end{center}
%\vspace*{0.1cm} 
\center{Static SPARC to Pentium Translation}
\end{minipage}\hfill
\vspace*{0.4cm}

\begin{minipage}[b]{\linewidth}
\begin{center}
\begin{tabular}{|r|r|r|r|r|} \hline
        & \multicolumn{2}{c|}{Translated Code} &
        \multicolumn{2}{c|}{Native Code} \\
Program & gcc opt & cc opt & -O0 & -O4 \\ \hline
Fibo(40) sec & 25.8 & 24.5 & 28.6 & 25.9 \\
       bytes & 16,496 & 7,268 & 16,144 & 16,152 \\ \hline
Sieve(3000) sec & 18.6 & 17.1 & 18.9 & 18.6 \\
       bytes & 16,228 & 6,536 & 15,964 & 15,944 \\ \hline
Mbanner(500K) sec & 48.7 & 46.5 & 80.5 & 44.8 \\
       bytes & 25,664 & 16,016 & 21,524 & 25,436 \\ \hline
%~\footnote{4,096 bytes added to executable to adjust data page size} \\ \hline
\end{tabular}
\end{center}
%\vspace*{0.1cm} 
\center{Static Pentium to Pentium Translation}
\end{minipage}\hfill
\vspace*{0.4cm}

%\begin{minipage}[b]{.46\linewidth}
%\begin{tabular}{|r|r|r|r|} \hline
%        & \multicolumn{1}{c|}{Generated Code} & 
%	\multicolumn{2}{c|}{Native Code} \\ 
%Program & Total & -O0 & -O4 \\ \hline
%Fibo(40) sec & 179.27 & 41.0 & 23.0 \\
%	byte & & 24,628 & 24,565 \\ \hline 
%Sieve(3000) sec & 83.00 & 29.3 & 24.5 \\
%	byte & & 24,552 & 24,452 \\ \hline 
%Mbanner(500K) sec & & & \\ 
%	byte & & & \\ \hline
%\end{tabular}
%\vspace*{0.1cm} \center{Dynamic SPARC to SPARC Translation}
%\end{minipage}\hfill
%\begin{minipage}[b]{.50\linewidth}
%\begin{tabular}{|r|r|r|r|r|r|} \hline
%        & \multicolumn{3}{c|}{Translated Code} & 
%        \multicolumn{2}{c|}{Native Code} \\
%Program & startup & dispatch & gen code & -O0 & -O4 \\ \hline
%Fibo(40) sec & 0.48 & 0.03 & 191.39 & 41.0 & 23.0 \\
%        bytes & & & 1,208 & 24,628 & 24,564 \\ \hline
%Sieve(3000) sec & 0.52 & 0.08 & 80.85 & 29.3 & 24.5 \\
%        bytes & & & 1,556 & 24,552 & 24,452 \\ \hline
%Mbanner(500K) sec & & & & & \\
%        bytes & & & & & \\ \hline
%\end{tabular}
%\vspace*{0.1cm} \center{Dynamic Pentium to SPARC Translation}
%\end{minipage}\hfill
%\vspace*{0.4cm}
%
%\begin{minipage}[b]{.42\linewidth}
\begin{minipage}[b]{\linewidth}
\begin{center}
\begin{tabular}{|r|r|r|r|r|} \hline
        & \multicolumn{2}{c|}{Translated Code} & 
        \multicolumn{2}{c|}{Native Code} \\
Program & Interpreter & JIT & -O0 & -O4 \\ \hline
Fibo(40) sec & 421.64 & 58.02 & 41.0 & 23.0 \\  
	bytes & 739 & 739 & 24,628 & 24,565 \\ \hline  
Sieve(3000) sec & 103.66 & 20.52 & 29.3 & 24.5 \\ 
	bytes & 677 & 677 & 24,552 & 24,452 \\ \hline
%Mbanner(500K) sec & & 10m16.06 & 22.11 & 10.01 \\ 
% 	bytes & & & & \\ \hline
\end{tabular}
\end{center}
%\vspace*{0.1cm} 
\center{Static SPARC to Java Bytecode Translation}
\end{minipage}\hfill
%\begin{minipage}[b]{.46\linewidth}
%\begin{tabular}{|r|r|r|r|r|} \hline
%         & \multicolumn{2}{c|}{Generated Code} & 
%         \multicolumn{2}{c|}{Native Code} \\
%Program & interpreted & JIT & -O0 & -O4 \\ \hline
%Fibo(40) sec & & & & \\  
% 	bytes & & & & \\ \hline  
%Sieve(3000) sec & & & & \\
% 	bytes & & & &  \\ \hline
%MBanner(500K) sec & & & & \\ 
% 	bytes & & & & \\ \hline
%\end{tabular}
%\vspace*{0.1cm} \center{Static Pentium to Java Bytecode Translation}
%\end{minipage}\hfill

\label{fig-results} \caption{Running Times and Code Sizes for Static
	Translators Instantiated from the UQBT Framework}
}
\end{figure*}

%%Figure~\ref{fig-results} presents results for 6 different
%%Figure~7 presents results for 5 different instantiations of the UQBT 
Figure~\ref{fig-results} presents results for 5 different instantiations of 
the UQBT framework.  The test programs are: 

\begin{itemize}
\item Fibo(40), which calculates the fibonacci of 40 and has 63 lines 
of assembly code, 
\item Sieve(3000), which calculates the first 3000 primes and has 
61 lines of assembly code, and
\item Mbanner(500K), a modified version of banner(1), which loops 
500,000 times to display argv[1] (``1234567890'' in this case) and 
has 204 lines of assembly code and a read-only data section 
of 336 bytes.
\end{itemize}

For all programs, we measured the time in seconds to execute
the program on the target machine and compared that to the
time measurement produced by a native compiler on that target
machine; this allows us to see the quality of the translation.
Each test program also lists on the second row the size in bytes
of the executable file for comparison purposes.
SPARC results were obtained on an UltraSPARC II, 250MHz machine
with 320Mb RAM running Solaris 2.6.
Pentium results were obtained on a Pentium MMX, 250 MHz machine
with 128Mb RAM running Solaris 2.6.
The source binary programs (input to the translator) were all compiled 
with gcc 2.8.1 -O4.  
Translated code programs used two different optimizing C 
compilers; gcc 2.8.1 and cc 4.2, on both SPARC and Pentium machines. 
Native code for the target machine was compiled using gcc 2.8.1
with -O0 and -O4 options, on both SPARC and Pentium.  
%%Results for -O0 are included to indicate how much variation optimization 
%%causes on the source architecture. 

As can be seen from the results, the statically translated code is just 
as efficient as native code on translations across the same 
architecture (i.e. SPARC to SPARC and Pentium to Pentium), 
and small or negligible overhead is created on static register-based
translations across different architecture machines.
This is due to the abstraction of code into \hrtl\ code 
and perhaps the small size of the test programs, which do not 
necessarily test all the features of large programs 
(such as differences in types or the need for interpretation).
Some translated programs (those translated by uqbtss and uqbtpp) are 
faster than their native counterparts because of accidents of instruction 
scheduling.  We compared the input and the translated program and 
noticed a few extra nop's and unfilled delay slots in the input 
optimized binaries.  These can make a very large difference for 
programs like fibonacci, which have very short inner loops doing most of 
the work.

The version of Sieve that is translated from the Pentium to the 
SPARC runs 9\% slower than the version compiled from C source 
code by the native SPARC compiler, when using gcc as the optimizer 
with UQBT. Because the Pentium has fewer registers than SPARC, 
the Pentium compiler did not put all variables in registers. 
In the translation from the Pentium binary, those variables remain
in memory, but when the native SPARC compiler translates the same
source code, it puts all variables in registers, so the natively 
compiled version is 9\% faster.  In contrast, the cc optimizer does  
perform this optimization and the result is a generated binary 
that runs at the same speed as native code.  

Translations between machines of different endianness, such as 
SPARC and Pentium, may require the use of byte swapping at each load 
and store in order to access initialized data.  This is the case
of the Mbanner Pentium to SPARC static translation, where a 100\%
overhead is seen.  
This is due to two main factors: memory locations are not promoted 
to registers wherever possible, and there are redundant byte swaps 
due to endianness differences.
In our translation to SPARC, the machine has to 
perform costly byte swapping for one 32-bit load instruction, which 
results in 10 SPARC instructions.  
Two redundant 32-bit byte swaps result in 20 SPARC instructions 
which the optimizer cannot remove.  This problem is not seen in 
SPARC to Pentium static translations however, because the Pentium has 
a single instruction to perform 32-bit byte swapping. 
The two shortcomings identified in the generated code can be 
rectified by implementing binary translation-specific optimizations 
at the \hrtl\ level, before emitting machine-dependent code.  

The Pentium to SPARC translations suffer a large performance hit
because of the way that endianness swaps are implemented. The
cost is some 8 SPARC instructions, with an extra 2 for the first
one (and if the register used to hold the mask is re-used). Most
SPARC machines these days have UltraSparc processors, and with
these machines it is possible to perform endianness swaps during
loads and stores (alternate address space 0x88 performs the
required swapping).

To implement the alternate address scheme, the macros need to be
split into two groups; one for loads, and one for stores. (Both
of these would be almost the same for Pentium targets). Also,
there is the issue that for the lowest overhead, two different
assembly language forms have to be used; one for when the SPARC
addressing mode is register plus register, and one for when it is
register plus constant. We did not implement these changes, 
so regrettably we do not know what the true cost of translation
from Pentium to SPARC really is (i.e. at present, it is
needlessly being swamped by the cost of endianness swaps using the 
first-mentioned method).

For the translator of SPARC to Java bytecodes we show 
initial results obtained without having performed stack-based 
optimizations on the code.  
Nevertheless, the JIT compiled 
version compares favourably with native code on the SPARC, 
especially due to the efficiency of present JIT compilers, 
which translate two or three bytecode instruction sequences 
into one target native instruction. 
These results apply to small integer benchmarks. 

