%
% Sep 99: Cristina, created, based on WBT paper
% Sep 01: Cristina, updated, based on Palm experiments from Mar 00 
%            and writeup from May 01 
%

\chapter{Experience in the Use of the UQBT Framework}
\label{ch-experience}

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

This chapter documents our experiences in building the \uqbt\ 
framework, and ours and others experiences in the use of the 
framework to instantiate translators. 
Our experiences in building the framework are described in terms of 
effort to create the \uqbt\ framework itself and effort in instantiating 
a new frontend or a new backend.  The adaptability of the framework 
is shown through the support for other architectures. 
The core of this chapter was written in 1999, the Palm experiences 
were written in 2001.  

As reported in the Instantiation chapter (Chapter~\ref{ch-instantiation}), 
writing a new frontend requires the SLED, SSL and PAL specifications 
to be written, as well as the binary-file format and the control-transfer
APIs to be satisfied.  Further, any machine-specific information that is 
not supported directly by the framework needs to be coded in as part of
the RTL to HRTL translation step.  
When writing a new backend, experimentation is mainly with different 
ways of generating code (at different levels of abstraction) in order
to try out a different optimzizer (say VPO or the PostOptimizer).  


\section{Effort in Building the UQBT Framework}
The UQBT framework provides binary translation writers with 
support for new architectures at low cost.  
This is evidenced by the effort to support a new architecture,  
which is low because most of the UQBT framework is reused. 
We quantify the effort to develop the UQBT environment and 
the effort to reuse it.  
We also provide our experiences with supporting a new target 
architecture, a stack-based architecture in this case.


\subsection{Development of the Framework}
The development of the UQBT framework has been an order of 
magnitude larger than writing a hand-crafted binary translator 
from scratch.  This complexity was introduced by the need to 
make the framework re-sourceable in particular, and the 
need to separate machine-dependent concerns from machine-independent
analyses.  UQBT has been developed over a period of 4 years 
by a small team, consuming 6.2 person-years (some of those with 
relatively inexperienced students initially).   
%% CC: it's 6.2 man-years w/o the JVM, which is 0.5 and it's 
%% mentioned elsewhere.  I've made these figures til end of Dec. 
%% In my time, I didn't include all this writing up of papers, 
%% which has consumed a fair bit while I've been here. 
%% Breakdown of 6.2 man-years: [at eoDec 99]
% Mike: 3 years * 80%
% Cristina: 3.5 years * 50% + 0.5 years * 30%
% Shane Sendall: 1 * 40% (SSL) 
% Doug Simon: 1 * 50% (SSL, PAL) 
% David Ung: 1 * 100% (SSL)
%% JVM back end: Trent Waddington: 1 * 50% (JVM) 
%% for dynamic, David Ung, extra 2 years * 100%

The use of specifications allows us to create new binary translators 
quickly, by instantiating from the UQBT framework by specifying the 
source and target machine, reusing most of the components in the system 
and providing a driver skeleton for the decoding phase.  
In order to support peculiarities of particular machines, extensions 
to the system may be required, either in the form of extra analyses 
(specific to one machine) or extra constructs in the semantic 
language. 

To add DCTL support we expect a 0.2 person-year effort as this is 
a simple transformational language which is easily described 
and used.  DCTL can replace about 1000 lines of code, which are currently 
specific to the SPARC architecture.  Due to the low occurrence
of the delayed transfer of control concept on modern architectures, 
we have not placed a high priority in the implementation of this language.  


\subsection{Reuse of the Framework---Low Cost}
The size of the specifications gives an estimate of the amount 
of code a developer would need to write in order to get 
the basic translation system to work, or in determining how 
much it supports a given pair of machines.  
Current machine instruction descriptions (syntax, semantics, 
control flow) for SPARC and Pentium architectures are between 1,100 
and 2,600 lines, and calling convention and stack frame specifications 
are around 200 lines each (see Figure~\ref{fig-specSizes}.
This is in contrast to 26,500 lines of source code, 
6,200 lines of definitions in header files, 
3,900 lines of specification files and the 
skeleton driver generated by the framework (on average 2,000 lines).  

\centerfigbegin
\begin{tabular}{|l|c|c|c|} \hline
Machine & SLED & SSL & PAL \\ \hline
SPARC & 306 & 689 & 173 \\
Pentium & 746 & 1626 & 172 \\
mc68K & & & \\ \hline
\end{tabular}
\centerfigend{fig-specSizes}{Number of Lines of Code for Different
    Machine Specs.}

This highlights the reduced amount of code that a binary 
translation writer would have to develop.  Further, reuse of
specifications is also possible, particularly when other 
people have already written such specifications.


\subsection{Endianness}
\emph{This section needs to be updated.} 

Without special analysis, it is necessary for the translated program to run
using the endianness of the source program. This basically implies swapping the
byte ordering of multi-byte memory references after every load and before every
store. The Pentium processor has single instructions for doing this, but the
sequence on the SPARC is 10 instructions for the first swap, and 8 instructions
thereafter if a constant mask can be retained in a register.

For memory intensive programs, this overhead can be quite large, and in the
case of a SPARC target, there is additional register pressure as well
(i.e. a variable that might have otherwise been optimized to registers
will have to be spilled to memory).  Further, in the context of
byte swapping, instructions like ``increment memory variable'', that
require 5 \hrtl\ instructions:

\begin{smallverbatim}
  v1 = m[%afp + 4]
  byteswap (v1)
  v1 = v1 + 1
  byteswap (v1)
  m[%afp + 4] = v1
\end{smallverbatim}

end up being represented in SPARC machine code as a series of up to 21
instructions: 1 instruction for the memory load, 8 or 10 instructions for the
first byte swap, 1 instruction for the increment, 8 instructions for the
second byte swap, and 1 last instruction for the memory store.
This type of code cannot be optimized by even the best current
optimizers.

In the generated code, some of the byte swaps are redundant or could
be eliminated with analysis, in effect removing the overhead created
on machines that do not natively support byte swapping of words.
In the UQBT framework, this analysis can be done at the \hrtl\ level, 
but such analysis has not been implemented at this point in time.


\section{Experiences with Translation to Bytecodes of the Java Platform}
The adaptability of the UQBT framework was first tested in 1999 by our 
student Trent Waddington by supporting translations to bytecodes, the 
assembly language of the Java virtual machine. 
We instantiated two new translators, \texttt{uqbtsb} and \texttt{uqbtpb}, 
to translate from SPARC and Pentium architecture binaries to bytecodes. 
We reused the specifications for the source machines and 
wrote a back end for \texttt{gcc} (the GNU C compiler) to generate 
bytecodes in assembly files linkable by \texttt{jasmin}~\cite{Meye97} 
into Java class files. 

In order to run bytecode binaries, an extra support environment 
was written to provide support for memory access and pointers 
to memory, as well as translating some library calls.

The results of this experiment were good.  The performance of 
the translated programs on non-memory intensive micro-benchmarks 
were comparable to native C code compiled on the machine where the 
JVM was running.  Memory intensive programs showed a performance 
degradation due to our memory management support and to the 
lack of unsigned integral types in the JVM.   

The overall effort of this experiment was 0.5 person-years in 
the development of the \texttt{gcc} JVM back end, the JVM runtime 
support environment, and testing of micro benchmarks. 
 

\section{Experiences in Instantiating a Palm Translator} 
One of the advantages of a retargetable framework is that it 
allows the framework to be used in unexpected ways.
Our experiments translating PDA applications illustrate this flexibility
as the framework was not specifically designed for translations 
of embedded systems software.

We experimented with translating CISC mc68328 Palm applications to a 
RISC processor, the ARM, as well as to bytecodes for the
Spotless~\cite{Taiv99} virtual machine for the Java platform.
Spotless is Sun Microsystems Laboratories' virtual machine for small 
devices that runs on PalmOS.
A commercial version of Spotless that is independent of PalmOS
is available as the K virtual machine\TM (KVM\TM).
The KVM runs on multiple platforms including the Palm.

We instantiated two translators:
one from the (mc68328,PalmOS) to the (ARM,PalmOS) 
and the other from (mc68328,PalmOS) to the (Spotless,PalmOS).
We use the term ``instantiated''
because the work of creating a new translator
often consists of selecting among existing components
rather than implementing an entirely new translator from scratch.
We also use a (processor,operating system) notation
to describe more precisely a specific platform:
a combination of a processor and an operating system.
The first section below describes how we instantiated the
mc68328-to-HRTL front end shared by both translators.
The next two sections describe the use of two UQBT back ends
to generate, respectively, ARM machine code and JVM bytecodes.

This experiment was run by Cristina and Mike in March-May 2000. 
We mainly worked on instantiating a new mc68328 frontend, which 
took some time due to lack of familiarity with the mc68328 
architecture.  We were familiar with the SLED, SSL and PAL 
description languages, as well as how the \uqbt\ framework works. 
In Feb 2001, Brian Lewis run experiments with existing backends, 
the low-level C and the JVM backends.  
A total of 3.5 man-months was spent in the experiments reported 
herein. 


\subsection{Instantiating a UQBT front end for mc68328 Palm binaries}
The first step in instantiating a new translator
is to build a front end for the source platform.
The front end translates source binary files
into the HRTL intermediate format.
This requires writing, or reusing, SLED, SSL and PAL specifications
for the source platform.
Also, an implementation of the binary file API for the
source binary files must be available.
If one does not already exist, it will have to be written.
This process is explained in detail elsewhere (Chapter~\ref{ch-instantiation}).
We give an overview of the steps involved here
as well as the effort involved for those steps when
instantiating the (mc68328,PalmOS) translators.
In brief, the steps involved in instantiating the framework are:

\begin{itemize}
\item Write support for the binary file format:
%\textbf{Write support for the binary file format:}
        The PalmOS uses .PRC files, which were not yet supported by UQBT,
	so we wrote a \texttt{PalmBinaryFile} class 
	that satisfied the \texttt{BinaryFile} API exported by UQBT. 
	\texttt{PalmBinaryFile} was written and tested in five days.
	This was a little longer than usual because of the unusual 
	compression involved, and the difficulty finding details about 
	the .PRC format at that time.

\item Write and test the SLED (syntax) specification: 
%\textbf{Write and test the SLED (syntax) specification:}
	Writing a SLED specification is usually the most time consuming
	step because of the time needed to learn a new processor's
    instruction set.  
	For a machine as complex as the mc68k, up to a couple of 
    months can be spent writing its specification.  
	We reused a mc68k specification that had previously been written 
	as part of the New Jersey Machine Code toolkit~\cite{Rams97}.
	We only needed to simplify it to support the mc68328
	(which has, e.g., fewer addressing modes than some mc68k processors)
	and to fix some bugs.
    The SLED specification describes 211 user and system level instructions.
	It took two weeks to test and integrate the specification
	into the UQBT framework, resulting in the creation of a 
      mc68328 decoder. 

\item Implement the control transfer API:
%\textbf{Implement the control transfer API:}
    Implementing this API is trivially done in one day, by extending     
    the SLED decoder from the previous step to support the mc68328's
    control transfer instructions.

\item Write and test the SSL (semantic) specification: 
%\textbf{Write and test the SSL (semantic) specification:}
	Writing a new SSL specification is usually straightforward once the 
	SLED specification has been written, because by then the 
	instruction set is familiar.
    We only specify the user level mc68328 instructions for our
    translations, therefore 147 instructions were specified.
	Writing this SSL specification required just one week
	for someone experienced in writing SSL specifications.
    An additional week was needed for testing and making corrections.

\item Write the PAL (procedure abstraction) specification:
%\textbf{Write the PAL (procedure abstraction) specification:}
    A PAL specification is based on an operating system's
    ABI (application binary interface) conventions for procedure calls,
    parameter passing, and the representation of call stack frames.  
	For mc68328 Palm code we identified five different caller 
	prologues, five callee prologues, four callee epilogues, 
    and one caller epilogue.
    Parameters are passed on the stack aligned on 16 bit boundaries 
	and returned values are placed in the \texttt{d0} register, 
	except for addresses (which are placed in \texttt{a0}) and doubles 
	(which use \texttt{d0} and \texttt{d1}).  
	Writing and testing the PAL specification for mc68328 Palm code
    took two weeks.  
	
\item Additional, machine-specific analyses: 
%\textbf{Additional, machine-specific analyses:}
	When instantiating a translator,
	it may be necessary to add additional analyses 
	to remove some remaining source platform peculiarities.
	In the case of the mc68328, the data section has a 
	global data pointer that acts much like the frame pointer.
    Even though this concept could be emulated in the generated
    code, it is best to remove it all together.
    We transformed mc68328-RTL code into HRTL code that does not 
    use a global data pointer by extending the existing analysis that 
    transforms a platform's stack pointer registers into an 
    abstract stack frame pointer register (\texttt{\%afp}). 
    In this way, we now support transformations of the global data
    pointer into an abstract global pointer (\texttt{\%agp}), which
    is a fixed reference location instead of a variable address.   
\end{itemize}

\centerfigbegin
\begin{fnverbatim}
static DWord StarterPilotMain(Word cmd, Ptr cmdPBP, 
                              Word launchFlags)
{   Err error;
    error = RomVersionCompatible(version20,
                                 launchFlags);
    if (error) return (error);
    switch (cmd) {
       case sysAppLaunchCmdNormalLaunch:
           error = AppStart();
           if (error)
               return error;
           FrmGotoForm(MainForm);
           AppEventLoop();
           AppStop();
           break;
       default:
           break;
    }
    return 0;
}
\end{fnverbatim}
\centerfigend{fig-c-eg}{Example translated: StarterPilotMain}

As an example for the rest of this section,
we show the translation of the procedure \texttt{StarterPilotMain}
from the Palm example application \texttt{Starter}.
The C code for \texttt{StarterPilotMain} appears in Figure~\ref{fig-c-eg}. 
While short, this procedure has moderately complex control flow,
calls a number of procedures, some returning parameters,
with arguments of various sizes.
The mc68328 assembly code for \texttt{StarterPilotMain}
is shown in Figure~\ref{fig-asm-eg}.

	Figure~\ref{fig-hrtl-eg} shows the HRTL code generated for
	\texttt{StarterPilotMain}.
	The code is too long to show in its entirety,
	so we elided code after the first conditional branch (to L1)
	up to the basic block with the call to \texttt{FrmGotoForm}.
        The procedure is called \texttt{proc1} since the .PRC binary format 
        does not specify a standard way of storing names of procedures in 
        any of its sections.
        Addresses on the left of each RTL are those of the first corresponding
        source binary instruction.
        Annotations of the form \texttt{*16*} and \texttt{\{16\}}
        indicate the size of assignments and expressions in RTLs.
        Basic blocks have been identified and are labelled with the kind
        of control transfer at their end.
        Note how procedure calls and branches have been recognized 
        using PAL information and source machine-specific details
        eliminated.

\centerfigbegin
\begin{fnverbatim}
03C6: 4E56 0000      link      a6, #0
03CA: 48E7 1C00      movem     <1c00>, -(a7)
03CE: 3A2E 0008      movew.ex  8(a6), d5
03D2: 382E 000E      movew.ex  14(a6), d4
03D6: 3F04           movew     d4, -(a7)
03D8: 2F3C 0200 3000 movel.exl #33566720, -(a7)
03DE: 4EBA FCD0      jsr.ex    RomVersionCompatible
03E2: 3600           movew     d0, d3
03E4: 4A43           tstw      d3
03E6: 5C4F           addqw     #6, a7
03E8: 6706           beq       03F0
03EA: 3043           movew     d3, a0
03EC: 2008           movel     a0, d0
03EE: 602A           bra       041A
03F0: 3005           movew     d5, d0
03F2: 6702           beq       03F6
03F4: 6022           bra       0418
03F6: 4EBA FF6E      jsr.ex    AppStart
03FA: 3600           movew     d0, d3
03FC: 4A43           tstw      d3
03FE: 6706           beq       0406
0400: 3043           movew     d3, a0
0402: 2008           movel     a0, d0
0404: 6014           bra       041A
0406: 3F3C 03E8      movew.ex  #1000, -(a7)
040A: 4E4F           trap      sysTrapFrmGotoForm
040E: 4EBA FEEC      jsr.ex    AppEventLoop
0412: 4EBA FF86      jsr.ex    AppStop
0416: 544F           addqw     #2, a7
0418: 7000           moveq     #0, d0
041A: 4CDF 0038      movem     (a7)+, <0038>
041E: 4E5E           unlk      a6
0420: 4E75           rts
\end{fnverbatim}
\centerfigend{fig-asm-eg}{mc68328 assembly code for StarterPilotMain}


\centerfigbegin
\begin{fnverbatim}
High level RTLs for procedure proc1(v0, v1, v2)
Call BB 
000003c6
000003ce *16* r[5] := v0
000003d2 *16* r[4] := v2
000003d6 *16* r[temp1] := r[4]
         *16* v5 := r[temp1]
000003d8 *32* v4 := 33566720
000003de  v3 := CALL proc3(v4, v5)

Twoway BB
000003e2 *16* r[temp1] := v3
         *16* r[3] := r[temp1]
000003e4 *16* r[tmp1] := r[3]{16}
         *16* v6 := r[tmp1]
000003e8  JCOND (v6 = 0) 3f0
...       ...

L5: Call BB
00000406 *16* v5 := 1000
0000040a  CALL FrmGotoForm(v5)

Call BB
0000040e  CALL proc4()

Call BB
00000412  CALL proc5()

Fall BB
00000416

L4: Fall BB
00000418 *32* v3 := 0

L2: Ret BB
0000041a  RET                   
\end{fnverbatim}
\centerfigend{fig-hrtl-eg}{HRTL code for StarterPilotMain}


\subsection{Using UQBT back ends to translate mc68328 Palm binaries to the ARM}
\label{sec-to-arm}
For several years, the standard UQBT back end has used 
a C compiler to optimize its intermediate code
and produce binary files for the target platform.
This backend translates HRTL code to low-level C code,
effectively using the C compiler as an assembler.
The following section (\ref{sec-to-c}) describes our use of this 
back end for the (mc68328,PalmOS) to (ARM,PalmOS) translator.
Section~\ref{sec-to-jvm} describes our use of a second,
experimental, back end that emits JVM bytecodes.

We are currently extending UQBT to directly integrate
with other retargetable optimizers at the HRTL level.
HRTL code will be translated to lower-level, target-specific M$_t$-RTL code
and fed into an optimizer such as VPO.
Figure~\ref{fig-newUqbt'} illustrates this new UQBT framework and its
three back ends.  

\psfigbegin{figures/uqbtOverall2001.eps}{8.5cm}
\psfigend{fig-newUqbt'}{The 2001 UQBT framework for retargetable binary translation}

To generate M$_t$-RTL code we need to solve several 
problems that are not discussed in this paper: 
\begin{itemize}
\item How to transform HRTL code to M$_t$-RTL code in a
      machine-independent way. 
      This step requires a few extensions to the PAL language
      to support retargetable code generation for procedure calls.
      That is, we want to use this extended PAL language to automate
      the generation of code for calls and parameters, in much the same 
      way that PAL currently automates the recognition of standard 
      call prologues and epilogues.
      The extended PAL language will emit code to use the specified
      call and parameter passing conventions for a target platform, 
      as well as to set up its stack frames. 

\item How to satisfy the M$_t$-RTL invariant that some optimizers
      such as VPO require. 
      This invariant requires that each RTL be at the level of 
      a target machine instruction.
      This invariant allows retargetable optimizers to perform
      not only machine-independent optimizations
      but also machine-dependent ones. 
\end{itemize}


\subsubsection{Translation to ARM using the Low-level C Backend}
\label{sec-to-c}
UQBT's C back end generates low-level C code, in effect, using 
the C compiler as a macro assembler.  
Figure~\ref{fig-cgen-eg'} shows the code generated by this back end
for the procedure \texttt{StarterPilotMain}. 
As this code illustrates, type casting is frequent and
used to ensure that the C compiler does exactly what is required.
In particular, there are frequent casts
between 16 bit and 32 bit integers
and pointers to storage containing those integers
to preserve the original 16 bit computations
of the source binary.
We do not attempt to optimize our generated code
since we expect the C compiler to do this.
The hexadecimal numbers in comments
identify the start of basic blocks in the source binary.

\centerfigbegin
\begin{fnverbatim}
#include "uqbt.h"
void proc1(int16 v0, int32 v1, int16 v2) {
    int16 v3;
    int32 v4;
    int16 v5, v6, v7, v8;
    int32 r3, r4, r5, r8;
    int32 temp1, tmp1;

    /* 3c6 */
    *(int16*)&r5=v0;
    *(int16*)&r4=v2;
    temp1= *(int16*)&r4;
    v5=temp1;
    v4=33566720;
    v3=proc3(v4,v5);
    temp1=v3;
    *(int16*)&r3=temp1;
    tmp1=(unsigned int16)(*(unsigned int16*)&r3);
    v6=tmp1;
    if ((*(int32*)&v6)==(0)) goto L1;
    ...
L5:      /* 406 */
    v5=1000;
    FrmGotoForm(v5);
    proc4();
    proc5();
L4:      /* 418 */
    *(int32*)&v3=0;
L2:      /* 41a */
    return;
}
\end{fnverbatim}
\centerfigend{fig-cgen-eg'}{Low-level C code for StarterPilotMain}

We compiled this C code using a cross-compiler,
a version of GNU gcc 2.95.2 that emits code for the ARM.
We had gcc generate code for the ARM V4 architecture,
which is used by a number of ARM processors
including the StrongARM processor.
Figure~\ref{fig-c-to-arm-eg} shows a disassembly
of the optimized ARM code generated using the flag \texttt{-O4}.

The ARM is a RISC processor with 16 32-bit registers
(in fact, there are 32 registers but only 16 are visible at any time).
Every data processing instruction can use a barrel shifter
as well as the ALU,
which allows compact code sequences in many cases.
Although the code of Figure~\ref{fig-c-to-arm-eg}
does not use this,
the ARM allows each instruction to be \emph{predicated}--that is,
conditionally executed--which avoids the pipeline stalls
that would result from the branches
otherwise used to implement conditional code.
%%The ARM does not have delayed control transfers.
%%It also does not have the SPARC processor's register windows.
In the figure, the result register of most instructions
is the first register after the opcode.
The instruction \texttt{bl} (branch and link) is used to call procedures.
Arguments are passed in registers \texttt{r0}, \texttt{r1}, etc.,
and 32 bit or smaller integer results are returned in \texttt{r0}.

Unlike earlier versions of the ARM architecture,
ARM V4 includes halfword (16 bit) load and store instructions,
which improves the quality of the code generated 
for our translated 16 bit mc68328 operations.

This code assumes that the necessary Palm libraries are available.
Notice the call to the library procedure \texttt{FrmGotoForm},
which is PalmOS-specific.  
We do not currently have access to Palm libraries for the ARM,
and so we have not been able to run the translated code.
We expect this situation to change 
since Palm has announced that they are porting PalmOS
to the ARM.

\centerfigbegin
\begin{fnverbatim}
proc1():
   0: e1a0c00d   mov   r12, sp
   4: e92dd800   stmdb sp!, {r11, r12, lr, pc}
   8: e24cb004   sub   r11, r12, #4   ; 0x4
   c: e24dd014   sub   sp, sp, #20    ; 0x14
  10: e15bc1be   ldrh  r12, [r11, -#30]
  14: e15b31b6   ldrh  r3, [r11, -#22]
  18: e18cc800   orr   r12, r12, r0, lsl #16
  1c: e3a00402   mov   r0, #33566720  ; 0x2003000
  20: e1833802   orr   r3, r3, r2, lsl #16
  24: e1a03863   mov   r3, r3, ror #16
  28: e50b3018   str   r3, [r11, -#24]
  2c: e2800a03   add   r0, r0, #12288 ; 0x3000
  30: e15b11f8   ldrsh r1, [r11, -#24]
  34: e1a0c86c   mov   r12, r12, ror #16
  38: e50bc020   str   r12, [r11, -#32]
  3c: ebfffffe   bl    proc3
  40: e14b01b0   strh  r0, [r11, -#16]
  44: e15b31ba   ldrh  r3, [r11, -#26]
  48: e15b21f0   ldrsh r2, [r11, -#16]
  4c: e1833802   orr   r3, r3, r2, lsl #16
  50: e1a03863   mov   r3, r3, ror #16
  54: e50b301c   str   r3, [r11, -#28]
  58: e15b31bc   ldrh  r3, [r11, -#28]
  5c: e14b30be   strh  r3, [r11, -#14]
  60: e51b300e   ldr   r3, [r11, -#14]
  64: e3530000   cmp   r3, #0         ; 0x0
  68: 1a000026   bne   108 <proc1+0x108>
                 ...
  ac: e3a00ffa   mov   r0, #1000      ; 0x3e8
  b0: ebfffffe   bl    FrmGotoForm
  b4: ebfffffe   bl    proc4
  b8: ebfffffe   bl    proc5
  bc: e3a03000   mov   r3, #0         ; 0x0
  c0: e50b3010   str   r3, [r11, -#16]
  c4: e91ba800   ldmdb r11, {r11, sp, pc}
\end{fnverbatim}
\centerfigend{fig-c-to-arm-eg}{Generated ARM code for StarterPilotMain}


\subsubsection{Translation to JVM bytecodes using the JVM Backend}
\label{sec-to-jvm}
UQBT includes an experimental JVM backend
that transforms HRTL code into bytecodes.
These are written to \texttt{.j} files that Jasmin~\cite{Meye97}
assembles into Java class files.
We have only tested this backend so far with integer programs.
The code the JVM backend generates
makes use of a \emph{compatibility library}
that emulates the source platform's libraries
on the target platform, the Java virtual machine.
The backend includes only very limited support
for C's memory model.
For example, it implements \texttt{malloc} using a method
that allocates memory from a pre-allocated array of bytes
then returns that memory's offset.
Support for translated programs to use the JVM memory model
more directly will require additional analysis by UQBT (or 
any other binary translation front end for that matter).

\centerfigbegin
\begin{fnverbatim}
.method public static _proc1(III)V
    .limit stack   10
    .limit locals  130
    iconst_0
    istore 8
    iload  0    
    istore 18
    iload  2    
    istore 19
    iload  19   
    istore 100
    iload  100  
    istore 12
    ldc    33566720
    istore 11
    iload  10
    iload  11
    invokestatic Starter/_proc3(II)I
    istore 10
    iload  10   
    istore 100 
    iload  100  
    istore 20 
    iload  20   
    ldc    65535
    iand
    istore 100 
    iload  100  
    istore 13
    iload  13   
    bipush 0
    if_icmpeq L1
    ...
L5: sipush 1000
    istore 12
    iload  10
    invokestatic Starter/_FrmGotoForm(I)I
    istore 10
    invokestatic Starter/_proc4()V
    invokestatic Starter/_proc5()V
L4: bipush 0   
    istore 10
L2: return
.end method
\end{fnverbatim}
\centerfigend{fig-bytecode-eg}{JVM bytecodes for StarterPilotMain}

The Java virtual machine is stack oriented.
Bytecodes that perform data processing
operate on values already on the stack.
Both parameters in method calls and return values
are passed on top of the stack.
All integral types are signed. 
Stack entries can hold a value of any type
including a \texttt{double}, which is 64 bits.
However, a frame's local variables are 32 bits
(\texttt{double} and \texttt{long} values occupy two consecutive
local variables).
Bytecodes that load and store local variables
operate on only 32 bits or 64 bits,
so loads and stores of 16 bit integers sometimes require
additional bytecodes to ensure that the correct values are read or stored.
Class fields may be either 8, 16, 32, or 64 bits,
but these are not yet used by any code
currently generated by the JVM backend.

Figure~\ref{fig-bytecode-eg} shows part of the bytecodes
generated for \texttt{StarterPilotMain}.
This code shows that \texttt{StarterPilotMain}
and the procedures it calls have been
translated into \texttt{static} class methods,
which closely resemble C procedures.
Most bytecodes indicate the type of their operands,
with the type given by the first letter of their name:
e.g., \texttt{iload 19} loads a 32 bit \texttt{int} from local variable 19.
The bytecode \texttt{bipush} sign-extends a \texttt{byte}
to an \texttt{int} value,
which it pushes onto the stack.
The bytecode \texttt{if\_icmpeq L1}
is an example of a conditional control transfer;
in this case, it pops two \texttt{int} values from the stack,
compares them for equality,
and, if so, jumps to the bytecode at the offset specified by its argument
(here, \texttt{L1}).

The automatic translation of Palm binaries to the Spotless environment 
illustrates how complete automation of a translation is not 
possible when the source and target platforms set up services
in different ways.  
The way in which event handling is set up in Spotless
differs from that in PalmOS.  
In Spotless, the \texttt{Spotlet} class
provides callbacks for event handling.
Applications extend \texttt{Spotlet}
to override the appropriate event handling methods.
For example:

\begin{fnverbatim}
public static void main(String[] args) {
    (new myApp()).register(NO_EVENT_OPTIONS);
}
\end{fnverbatim} 

In contrast, PalmOS applications require explicit code to
set up the event loop and event handling,
whereas in the Spotless system this is done implicitly
by inheriting from the \texttt{Spotlet} class.  
These differences mean that translation can only be
completed once an expert user determines
which procedures should be modified, or removed entirely
since their functionality is already provided by Spotlet.

Another problem that prevents automatic translation
is that the JVM backend does not support function pointers.
This is because the Java virtual machine
does not allow taking the address of a method.
Programs that use function pointers themselves or pass them to libraries
cannot be automatically translated.
Unfortunately, several PalmOS library procedures take function pointers,
including \texttt{FrmSetEventHandler}, which is used by \texttt{Starter}.
To emulate these library procedures, 
the corresponding methods of the compatibility library
and the calling methods,
must be modified to use \emph{closures},
instances of classes that may have a method invoked
in much the same way as a function pointer is called.

At present, PalmOS system calls are not supported by the 
Spotless or KVM systems, therefore, we have not tested 
the generated Java bytecode in a PalmOS environment. 


