
\chapter{The VPO Back End}
\label{ch-vpobackend}

{\small
\begin{flushright}
Design: Mike, Cristina, Norman. Implementation: Mike [98], Brian [01]. 
Documentation: Mike [98], Cristina, Brian [01]
\end{flushright}
}

In early 1998 we were using the VPO (very portable optimizer) system  
by Jack Davidson and students, University of Virginia, as our 
optimizer of choice.  We experimented with SPARC translations 
before we moved onto the C back end (see Chapter~\ref{ch-cbackend}). 
VPO's RTL interface back then was new and did not support x86 or 
other machines yet. 
The 1998 VPO back end is described in Section~\ref{sec-vpo}. 
This section is useful for historical reasons. 

In 2001 we went back to use VPO for optimization, by then, VPO's 
new RTL interface supported not only SPARC, but also x86 and ARM 
amongst other machines.  We were interested in translations to 
these three machines.  The original 1998 VPO back end was revived 
in a new form and made much more extensible and robust. 
The 2001 VPO back end is described in two parts: first, the 
experiment in translating IRTL to SPARC VPO RTLs is described in 
Section~\ref{sec-irtlvpo}, and next, the experiences with translating 
\hrtl\ to ARM VPO RTLs are described in Section~\ref{sec-vpo2001}. 


\section{The 1998 VPO Back End}
\label{sec-vpo}

This section describes \texttt{vpoback}, an experimental RTL$_{UQ}$
to RTL$_{VPO}$ translator which generates a file suitable for
piping to VPO, so that an executable file can be generated.
This backend is not meant to
be a serious prototype for a real backend, but is intended to demonstrate
the compatibility of the two RTLs. The experiment was
a success; it was possible to translate enough RTLs to generate a simple 
``hello world'' binary executable file for the SPARC platform (from 
a SPARC source binary).


\subsection{Description}

The experimental backend has been written to work with a preliminary
version of the VPO interface, as supplied by the University of Virginia 
in February 1998. This version has two distinct interfaces; one to generate 
Register Transfer Lists, and one to handle higher level concepts such as 
functions and global symbols. All functions of the first interface have 
names beginning with \texttt{Rtl\_}, while functions of the latter interface 
have names beginning with \texttt{VPOi\_}.


\subsection{Handling expressions}
\label{sec-expr}

In general, expressions in VPO are very similar to expressions in our
RTlists. For binary expressions, there are two considerations when
translating from RTL$_{UQ}$ to RTL$_{VPO}$. Firstly,
the operators have to be translated. Secondly, the \texttt{sethi}
instruction has to be considered specially. Most of our operators have
direct VPO equivalents. Notable exceptions are rotates with carry
(RTL$_{VPO}$ does not have them), and bit extractions (RTL$_{VPO}$ does
not appear to have them).

When translating the \texttt{sethi} instruction, it was found necessary
to translate
expressions of the form \verb!K << 10! (where K is a constant, and
\verb!<<! represents the left shift operator) to expressions like
\texttt{HI[X]}, where \texttt{HI} is a special Sparc specific unary
operator in VPO, and X has the value \verb!K<<10!.


\subsection{Handling registers}

Normal machine registers, such as r[8] (and even r[0] for register \%g0)
translate
directly to VPO using the \texttt{Rtl\_constLoc()} function. Some registers
are named (i.e. they are represented as a \texttt{Register} object, whose
\texttt{Index} member points to an object of type \texttt{Constant}, whose
value is a string, e.g. ``\%fp''). Others are implemented as special
registers (i.e. they are represented as a \texttt{SpecialReg} object).
SpecialReg objects have a name (it could also be \texttt{\%fp}; both
representations exist at present). These named registers
are translated into the appropriate general purpose register (\texttt{\%fp}
maps to register 30, and \texttt{\%sp} maps to register 14).

Temporary registers (e.g. \texttt{r[\_\_tmp123]}) are translated to ordinary
registers beginning with index 51 (for texttt{r[\_\_tmp001]}). VPO is to be
changed so that temporary registers will occupy their own storage spaces.


\subsection {Handling memory}

An object of class Memory contains a pointer to a Value object, which
could be of three types: \texttt{eCONSTANT}, \texttt{eREGISTER}, or
\texttt{eSPECIALREG}. These
represent the address of the memory being referenced. Where the address
is constant, the \texttt{Rtl\_constLoc()} function is used. Where the address
is given as a register, the register is processed as a location. This
location is fetched using \texttt{Rtl\_fetch()}, and the resultant expression
is used as the operand to \texttt{Rtl\_location()}.


\subsection {Handling RT assignments}

RT assignments involve a location and an expression. The location will
be either a register or memory object; each of these is translated to
a VPO location as above. The expression is also translated as previously
described (section~\ref{sec-expr}).
Where registers or memory are involved in the expression, they are translated 
as described above, and the result is converted into a value using
the \texttt{Rtl\_fetch()} function. The location and expression resulting
from the above (of types \texttt{Rtl\_ty\_loc} and \texttt{Rtl\_ty\_expr}
respectively) are
combined and emitted using the \texttt{VPOi\_rtl()} interface function.


\subsection {Handling Control Transfer instructions}

All the above translations are handled by considering a single Register
Transfer (RT) at a time. Basically, each RT of each RTL in the function
of interest is examined in a double counter for loop. However, there are a few
situations that have to be handled by examining a whole RTL; control
transfer instructions and frame instructions are examples. Complex
code examines each RTL to see if it matches the pattern of the appropriate
instruction of interest; if so, code is emitted to VPO directly instead
of translating the whole list of RTs separately. It is hoped that changes
to the representation for RTL$_{UQ}$ will simplify this comparison.

If the instuction is recognised as a control transfer instruction, more
complex code decides whether the instruction is a conditional or
unconditional branch, call, or return instuction. (This complex, difficult
to debug code may one day be automatically be generated by some sort of
tool given a piece of specification or RTL tree).

Return instuctions are simple; an assignment from register \texttt{RT}
(a special
VPO pseudo register) to register texttt{PC} is emitted.

For a call instruction, a symbol has to be generated for the destination
of the call. (This will become a call to the ``assembly interface'' one
day; at present, it is a VPOi function). At the time of writing, the
names of dynamic symbols was not available, so the function name is
fixed at ``printf''. The call is generated by emitting an assignment to
special VPO register ST (``STack''?) from the global symbol for the
destination of the call. In order to convince VPO that main was not a
leaf function, we had to use the \texttt{VPOi\_registerUse()} function,
with an argument list including all registers
from 1 to 15, indicating that all these registers had to be saved across
the call (and therefore, leaf optimisation for the procedure containing
the call is not possible).

Unconditional branches are not implemented as of this writing; they should
present no special problems beyond those required for a call.

Conditional branches in VPO have the form \texttt{PC=IC:0,L1234} where
\texttt{PC} of course represents the program counter, \texttt{IC} represents
the integer condition code register, the colon represents a relational 
operator, and \texttt{L1234} represents
a label. This is emitted as a guarded assignment, using \texttt{Rtl\_guard()}
and \texttt{Rtl\_Rtl\_assign()}. The required operator has to be determined
from an
expression contained in the RTL for the branch instruction (it depends
on the condition codes used, as well as the operators, and whether
the condition code is used directly, or negated first). This is again
difficult to write code that may be automated in the future.

As an example of this process, consider the \texttt{bg} (branch if signed
greater) Sparc instruction. There are three RTs in the RTL; the
%main RT contains the subexpression \texttt{\~(\%Z \| (\%N \^ \%V))}
main RT contains the subexpression \verb!~(%Z | (%N ^ %V))!
(where \verb!~!
represents logical negation, and \verb!^! represents the exclusive OR
operator). When this subexpression is detected, the VPO opertor required
is \texttt{Rtl\_op\_gt}.

It was found that VPO does not have suitable operators for handling
the jump if positive/negative instructions, and jump on overflow /
no overflow.


\subsection {Processing Frame instructions}

The save and restore instructions (which establish and remove stack
frames) are recognised at the RTL level, just as conditional control
transfer instructions are. At present, only the restore instruction
is correctly recognised, and this is used to call the
\texttt{VPOi\_functionEnd()} function.


\subsection {Other VPO calls}

The function \texttt{premble()} calls several VPOi functions that are
needed to
initialise VPO itself, and to set up a label for \texttt{main}. These
functions
set up the register map and special location map; both of these are
going to be changed in the next version of the VPO interface.


\subsection {Sample Generated Code}

This output is from an early version. It should be replaced by a later
version.

The input file was compiled from the folowing source by {\it gcc}:
\begin{verbatim}
#include <stdio.h>

int main()
{
    int a=5; int b=7;
    unsigned u=5; unsigned v = 7;

    if (a == b) printf("Equal\n");
    if (a != b) printf("Not Equal\n");
    if (a >  b) printf("Greater\n");
    if (a <= b) printf("Less or Equal\n");
    if (a >= b) printf("Greater or Equal\n");
    if (a <  b) printf("Less\n");
    if (u >  v) printf("Greater Unsigned\n");
    if (u <= v) printf("Less or Equal Unsigned\n");
    if (u >= v) printf("Carry Clear\n");
    if (u <  v) printf("Carry Set\n");
}
\end{verbatim}

Generated output (filtered by the \texttt{decode} program and formatted for
3 columns):
\begin{verbatim}
-   .seg    "text"      +r[51]=r[8]             +r[16]=R[r[51]]
-    .global _start     +R[r[51]]=r[11]         +r[17]=r[14]-r[9]
-_start:                +r[51]=r[30]+20         +PC=ICs0,L67452
+r[30]=r[0]|0           +r[16]=R[r[51]]         +r[8]=66{10
+r[51]=r[14]+64         +r[51]=r[30]+24         +r[30]=r[0]|232
+r[16]=R[r[51]]         +r[16]=R[r[51]]         +r[51]=r[30]+28
+r[17]=r[14]+68         +r[17]=r[14]-r[9]       +r[16]=R[r[51]]
+r[17]=r[14]-32         +PC=IC!0,L67236         +r[51]=r[30]+32
+r[30]=r[0]|r[1]        +r[8]=66{10             +r[16]=R[r[51]]
+PC=IC:0,L66984         +r[30]=r[0]|144         +r[17]=r[14]-r[9]
+r[30]=r[0]|r[1]        +r[51]=r[30]+20         +PC=ICh0,L67488
+r[8]=66{10             +r[16]=R[r[51]]         +r[8]=66{10
+r[30]=r[0]|116         +r[51]=r[30]+24         +r[30]=r[0]|256
+r[30]=r[0]|r[16]       +r[16]=R[r[51]]         +r[51]=r[30]+28
+r[30]=r[0]|r[17]       +r[17]=r[14]-r[9]       +r[16]=R[r[51]]
+r[10]=r[16]{2          +PC=IC:0,L67272         +r[51]=r[30]+32
+r[17]=r[14]+4          +r[8]=66{10             +r[16]=R[r[51]]
+r[17]=r[14]+r[10]      +r[30]=r[0]|152         +r[17]=r[14]-r[9]
+r[8]=130{10            +r[51]=r[30]+20         +PC=ICl0,L67524
+r[30]=r[0]|572         +r[16]=R[r[51]]         +r[8]=66{10
+r[51]=r[10]            +r[51]=r[30]+24         +r[30]=r[0]|280
+R[r[51]]=r[11]         +r[16]=R[r[51]]         +r[51]=r[30]+28
*                       +r[17]=r[14]-r[9]       +r[16]=R[r[51]]
+r[8]=64{10             +PC=IC'0,L67308         +r[51]=r[30]+32
+r[8]=64{10             +r[8]=66{10             +r[16]=R[r[51]]
+r[30]=r[0]|824         +r[30]=r[0]|168         +r[17]=r[14]-r[9]
+r[17]=r[14]+r[15]      +r[51]=r[30]+20         +PC=ICg0,L67560
+r[8]=0{10              +r[16]=R[r[51]]         +r[8]=66{10
+r[30]=r[0]|4           +r[51]=r[30]+24         +r[30]=r[0]|296
+r[51]=r[23]+r[8]       +r[16]=R[r[51]]         +r[30]=r[0]|0
+r[16]=R[r[51]]         +r[17]=r[14]-r[9]       *
+r[51]=r[8]+4           +PC=IC>0,L67344         +r[8]=64{10
+r[16]=R[r[51]]         +r[8]=66{10             +r[8]=64{10
+r[17]=r[14]-0          +r[30]=r[0]|184         +r[30]=r[0]|308
+PC=IC:0,L67144         +r[51]=r[30]+20         +r[17]=r[14]+r[15]
+r[17]=r[14]+4          +r[16]=R[r[51]]         +r[8]=0{10
+r[51]=r[16]            +r[51]=r[30]+24         +r[30]=r[0]|8
+r[16]=R[r[51]]         +r[16]=R[r[51]]         +r[51]=r[23]+r[8]
+r[17]=r[14]+4          +r[17]=r[14]-r[9]       +r[16]=R[r[51]]
+r[51]=r[16]            +PC=IC<0,L67380         +r[51]=r[8]+4
+r[16]=R[r[51]]         +r[8]=66{10             +r[16]=R[r[51]]
+r[17]=r[14]-0          +r[30]=r[0]|200         +r[17]=r[14]--1
+PC=IC!0,L67116         +r[51]=r[30]+20         +PC=IC:0,L67660
+r[30]=r[0]|5           +r[16]=R[r[51]]         +r[17]=r[14]+-4
+r[51]=r[8]             +r[51]=r[30]+24         +r[51]=r[16]
+R[r[51]]=r[11]         +r[16]=R[r[51]]         +r[16]=R[r[51]]
+r[30]=r[0]|7           +r[17]=r[14]-r[9]       +r[17]=r[14]+-4
+r[51]=r[8]             +PC=IC`0,L67416         +r[51]=r[16]
+R[r[51]]=r[11]         +r[8]=66{10             +r[16]=R[r[51]]
+r[30]=r[0]|5           +r[30]=r[0]|224         +r[17]=r[14]--1
+r[51]=r[8]             +r[51]=r[30]+28         +PC=IC!0,L67632
+R[r[51]]=r[11]         +r[16]=R[r[51]]         *
+r[30]=r[0]|7           +r[51]=r[30]+32
\end{verbatim}

This is a brief summary of the interace functions used by \texttt{vpoback}.

\subsection {RTL Interface}
\begin{tabular}{l l}
Rtl\_unary      & Generates a unary expression \\
Rtl\_binary     & Generates a binary expression \\
Rtl\_fetch      & Converts a location to an expression \\
Rtl\_op\_special & Generates a special RTL operator \\
Rtl\_int        & Generates an integer as an expression \\
Rtl\_location   & Generates a location \\
Rtl\_constLoc   & Generates a location from a space and an index \\
Rtl\_assign     & Generates an RT assignment from a location and expression \\
Rtl\_guard      & Generates a sort of guard (for conditional branches) \\
Rtl\_label      & Generates a label (e.g. \texttt{L1234}) \\
Rtl\_globalSymbol & Generates a global symbol (e.g. \texttt{printf}) \\
\end{tabular}

\subsection {VPOi Interface}
\begin{tabular}{l l}
VPOi\_rtl		& Sends an RTL to output \\
VPOi\_registerMap 	& Sends a register map line to output \\
VPOi\_specialLocationMap & Tells VPOi about the special locations \\
VOIi\_assembly    	& Generate assembler directives \\
VPOi\_functionName 	& Tells VPOi about a function \\
VPOi\_functionEnd 	& Tells VPO and VPOi that a function has ended \\
VPOi\_variableDeclaration & Sends a variable definition to output \\
VPOi\_registerUse  	& Sends register use information to output \\
\end{tabular}


\section{Initial 2001 Experiments with VPO -- Translating IRTL to VPO RTLs}
\label{sec-irtlvpo}

{\small
\begin{flushright}
Design: Brian;
Documentation: Brian;
Implementation: Brian [June 01]
based on Mike's 1998 SPARC VPO backend.
\end{flushright} 
}

The IRTL Sparc-to-VPO backend uses the
University of Virginia's Very Portable Optimizer (VPO)
to generate optimized SPARC code
from an IRTL ({\em not} HRTL) representation of a source SPARC
program.
The quality of the optimized code is about the same as produced by gcc
with optimization level \texttt{-O4}.
IRTLs ({\em intermediate RTLs}) are a representation of programs
that is close to the machine level.
IRTLs differ from RTLs primarily in having
delayed branch instructions removed.
They differ from HRTLs in being source machine-specific
and not having the additional information about,
for example, procedure parameters and return values,
that results from expensive HRTL analysis.

This backend is experimental and incomplete.
It cannot translate some programs where the more sophisticated (and
expensive) HRTL analysis is required.
For example, the test program \texttt{paramchain}
requires information about return values
that is only provided by HRTL analysis.
The IRTL backend also does not currently support switch statements
(although this would be relatively easy to add).
The IRTL backend passes about 75\% of the \uqbt regression tests.  

VPO provides instruction selection, instruction scheduling, and classical
global optimization.
VPO has been retargeted to a wide variety of architectures
including the SPARC, ARM, Pentium, and MIPS.
It operates on programs that are represented as register-transfer lists (RTLs).
These RTLs resemble those used by UQBT but are lower-level,
the expressions allowed are simpler.
While the VPO RTL language itself is machine-independent
(VPO has been used with several C front ends),
VPO RTLs encode target machine-specific information.
A VPO RTL is required to represent one target machine instruction.
This is called the {\em VPO invariant}.

Mike van Emmerik had done some initial experiments with VPO in 1998
that showed that VPO could be effective for optimizing translated programs.
One objective of the current work was to experiment further with VPO.
Another was to explore the use of a backend
that translates UQBT IRTLs into VPO RTLs.
IRTLs ({\em intermediate RTLs}) are a representation of programs
that is close to the machine level.
IRTLs differ from RTLs primarily in having
delayed branch instructions removed.
They differ from HRTLs in being source machine-specific
and not having the additional information about,
for example, procedure parameters and return values,
that results from expensive HRTL analysis.
The expectation was that it would be
straightforward to translate the low-level IRTLs into VPO RTLs
for the same machine.
A secondary goal was to explore how effective IRTLs are
as a basis for translations
when the target machine is the same as the source machine.
IRTLs are inexpensive to create compared to HRTLs,
but it was unclear whether additional information would be required.


\subsection{Design of the IRTL to VPO backend}

The SPARC IRTL to VPO backend (``VPO backend'')
is structured much like the other UQBT back ends.
The VPO backend is called for each procedure
to emit code for its IRTLs.
It does not directly emit code 
but instead emits VPO RTLs and other directives
that are written to a file \texttt{{\em procname}.cex}.
The VPO backend makes use of a small library,
the VPO input library {\em VPOi},
to produce the .cex file.
The Makefile generated for a translated program 
later invokes the VPO optimizer on each .cex file
to generate an optimized assembler source file.
That .s file is then assembled to produce a .o file
for each procedure of the source program. 

The VPO backend has two passes.
A first pass scans each basic block and IRTL
in order to discover what variables, labels, and procedures
need to be declared to VPO.
A second pass then processes each IRTL to emit the
necessary VPO RTLs and directives.
A recursive walk is made of each IRTL expression.
IRTL expressions (and so IRTLs) are higher-level than VPO RTLs
since they may require several target machine instructions to implement.
For example, the single IRTL

\begin{verbatim}
000109ec *32* r[8] := m[r[16] + 948]
\end{verbatim}

requires three SPARC instructions and so at least three VPO RTLs.


\subsubsection{IRTL in more detail}
While IRTL is close to the machine level
and to UQBT RTLs,
some machine-specific details have been abstracted away.
As mentioned above,
IRTL does not contain information about delayed branches.
This is useful for a VPO backend 
since VPO does not support the specification of delayed branches
in its input RTLs.
IRTL also does not contain information about 
whether a procedure in the source program was a leaf procedure
or whether it had a register window (used \texttt{save} and \texttt{restore}).
Detailed information about a procedure's entry prologue and epilogue
are abstracted away.
For example, when a procedure returns an integer result,
the IRTLs describing the semantics of a return
specify the semantics from the viewpoint of the caller
(the caller's \texttt{\%O0} register is set)
and do not indicate how the original procedure returned that value:
whether it stored into \texttt{\%O0} or \texttt{\%i0}.

Although IRTL does not reflect the extensive analysis done for HRTL,
some analysis is done.
For example, each basic block is identified and categorized.
Also, switch statements are recognized and analyzed,
and the resulting IRTL includes data structures describing 
each switch statement.
The IRTL for a switch also includes a synthesized variable for
the switch index in place of, say, the machine register 
containing the original index.


\subsection{Status of the VPO backend}
The VPO backend currently passes 34 (75\%) of our 45 regression tests.
This compares with 33 for the Expander backend which,
although it has access to the more precise HRTL information,
does not implement floating point.
The VPO backend does not implement switch statements yet.
This would be easy to do (perhaps needing three days),
and would enable the backend to pass an additional five tests.


\subsubsection{Performance}
Table~\ref{tab-perf} shows the performance of the VPO backend
compared to optimized gcc (gcc -O4) for a number of small programs.
The backend does not currently run larger programs such as compress
so these figures are only a rough indication of the backend's 
ability, through VPO, to generate efficient code.
The time required to run each program is given in seconds.
Source programs were compiled using gcc 2.8.1
using both -O0 and -O4.
All programs were run on an otherwise idle 451 MHz Sun 420R with 4GB of RAM
running Solaris 2.8.

\begin{figure}[htb]
\center
{\small
\begin{tabular}{|l|c|c|}
\hline
 {\em Program}            & {\em gcc -O4} & {\em VPO backend} \\
\hline
\hline
 \verb#Fibo-O0 (40)#      & \verb#9.9#    & \verb#21.5#       \\
 \verb#Fibo-O4 (40)#      & \verb#10.2#   & \verb#11.8#       \\
 \verb#Sieve3000-O0#      & \verb#10.3#   & \verb#12.4#       \\
 \verb#Sieve3000-O4#      & \verb#12.0#   & \verb#11.1#       \\
 \verb#MBanner-O0 (500K)# & \verb#47.7#   & \verb#51.0#       \\
 \verb#MBanner-O4 (500K)# & \verb#18.0#   & \verb#13.4#       \\
\hline
\end{tabular}
}
{\caption{\label{tab-perf}{Performance - gcc versus SPARC IRTL to VPO backend}}}
\end{figure}

Performance of the VPO backend's version of Fibo-O0
suffers because the source program kept its input argument
in memory rather than a register
and stored it in the caller's frame.
While the VPO backend can optimize references to local variables
(caching them in machine registers),
it was unable to optimize 
the many references to memory for the input argument.
The VPO version of Sieve3000-O0 is slightly slower
because VPO still emitted many unnecessary register to register moves.
There is a chance that this performance could be improved 
by giving VPO more precise information 
about the lifetimes of temporary locations.


\subsection{Experience}
This section describes various things that were learned 
during the development of the IRTL to VPO backend.
The next section summarizes the lessons learned during this work.

\subsubsection{Need for procedure argument and return analysis}
The most significant item learned during this work
was that analysis of procedure argument and return value information
is required for a VPO backend to correctly generate code.
This is unfortunate since that analysis is expensive.
The reason for this is ultimately that VPO requires detailed information 
about the lifetime of each location
(machine register or memory location).
A client program must specify for each procedure call
what locations contain parameters
and what locations will contain return values.
The VPO backend does not have this information,
with the result that many programs do not run,
in particular the larger, more realistic (representative) ones.

Currently, the VPO backend assumes that up to six parameters are passed
and that they are passed in the SPARC registers \texttt{\%o0} to \texttt{\%o5}.
This is clearly not enough for many programs,
and is not a correct assumption.
It also may result in VPO generating suboptimal code
since it must, e.g., reserve space for possibly unused parameters
in the calling frame.
However, this assumption was sufficient
to continue the backend's development long enough
to make significant progress and to discover other issues.

Analysis must also be done to discover information about return values.
The test program \texttt{paramchain} illustrates this need:

\begin{verbatim}
void addem(int a, int b, int c, int* res) {
    *res = a+b+c;
}

void passem(int a, int b, int c, int* res) {
    addem(a, b, c, res);
}

int main() {
    int res;
    passem(5, 10, 40, &res);
    printf("Fifty five is %d\n", res);
    return 0;
}
\end{verbatim}

When \texttt{paramchain} is compiled -O4 without inlining,
the following SPARC code is produced for 
procedures \texttt{passem} and \texttt{addem}:

\begin{verbatim}
addem()
	10934:  82 02 00 09        add     	%o0, %o1, %g1
	10938:  82 00 40 0a        add     	%g1, %o2, %g1
	1093c:  81 c3 e0 08        jmp     	%o7 + 8
	10940:  c2 22 e0 00        st      	%g1, [%o3]
	10944:  00 00 00 00        unimp   	0x0
	10948:  00 00 00 00        unimp   	0x0
	1094c:  00 00 00 00        unimp   	0x0
	10950:  00 00 00 00        unimp   	0x0
passem()
	10954:  82 10 00 0f        mov     	%o7, %g1
	10958:  7f ff ff f7        call    	addem
	1095c:  9e 10 00 01        mov     	%g1, %o7
\end{verbatim}

Note the unusual code for \texttt{passem}.
While it is a leaf procedure,
it makes a call.
The two instructions surrounding the call
save then restore the return location in \texttt{\%o7}
so that \texttt{addem} will return,
not to it,
but directly to its caller, \texttt{main}.
However, information about these instructions 
is lost in the IRTLs for these procedures:

\begin{verbatim}
IRTLs for procedure addem:
Ret BB (0x3da430):
00010934 *32* r[tmp] := r[8]
         *32* r[1] := r[8] + r[9]
00010938 *32* r[tmp] := r[1]
         *32* r[1] := r[1] + r[10]
0001093c *32* m[r[11]] := r[1]
0001093c  RET

IRTLs for procedure passem:
Call BB (0x3b82e8):
0010954  CALL addem()

Ret BB (0x3b81d8):
00000000  RET
\end{verbatim}

Since \texttt{passem} makes a call,
VPO will have it use a register window.
But this code is incorrect since then \texttt{addem}
(which VPO will make a leaf procedure)
will store its result in the memory location pointed to by \texttt{r[11]},
or \texttt{\%o3},
of \texttt{passem}, not \texttt{main} as intended.
Furthermore, the value stored will be based on the uninitialized
\texttt{\%o0} through \texttt{\%o2} of \texttt{passem},
not of the intended \texttt{main}.

Even if VPO were to make \texttt{passem} a leaf procedure
(so that \texttt{addem} reads then stores into \texttt{main's} variables),
the code still doesn't work since then 
\texttt{passem} will return to the wrong procedure:
not to \texttt{main} but to \texttt{passem}.
Worse, it will return to execute \texttt{passem's} \texttt{RET} instruction,
which will jump to itself, causing an infinite loop.

The solution for this is to do the same extensive analysis
for procedure arguments and return values
that HRTL analysis does.
This will have \texttt{addem} read and write {\em variables},
rather than registers, 
similar to the following code generated for \texttt{addem}
by the low-level {\em C} backend:

\begin{verbatim}
void addem(int32 r8, int32 r9, int32 r10, int32 r11) {
	...
	tmp=r8;		/* a parameter variable, not the register %o0 */
	r1=(r8)+(r9);
	tmp=r1;
	r1=(r1)+(r10);
	 *((int32*)( *(unsigned int32*)&r11))=r1;
	return;
}
\end{verbatim}


\subsubsection{Where to store procedure results?}
Since the VPO backend did not have
accurate procedure parameter and return value information,
it was initially hard to know where to return integer results.
A leaf procedure stores an integer result in \texttt{\%o0}
while a normal procedure, with a register window,
stores the result in \texttt{\%i0}.
As mentioned before, 
IRTL does not indicate where a integer-valued procedure
actually stored its result
(or whether the procedure is a leaf procedure or not).
Consider the following code for \texttt{banner6's} procedure \texttt{banprt}.
These are HRTLs, but IRTL has similar information
(without the argument information
and high-level information about conditional jumps).

\begin{verbatim}
High level RTLs for procedure banprt(r[24]<32i>)
L4: Oneway BB (0x4570b8):
00000000 *8* m[r[28] + 84] := truncs(32,8,0) 
00000000  JUMP 10b78
...

Twoway BB (0x456330):
00010bb0 *32* r[tmp] := r[27]
         *32* r[27] := r[27] + 1
00010bb4 *32* r[tmp] := r[28]
         *32* r[28] := r[28] + 85
00010bb8 *32* r[tmp] := r[26]
         *32* r[26] := r[26] + 85
00010bbc *32* r[tmp] := r[27]
         *32* v10 := 7
         *32* v9 := r[tmp]
         *32* r[0] := r[27] - 7
         SUBFLAGS( r[tmp], 7, r[0] )
00010bc0  JCOND 10b78, condition signed less
High level: v9 < v10<32i>
Synthetic out edge(s) to L4 L5 

L5: Ret BB (0x4571c8):
00010bc8 *32* r[8] := r[24]
00010bc8  RET
\end{verbatim}

Note the store to \texttt{r[8]}, or \texttt{\%o0}.
This is the overall meaning of the return,
and the semantics as viewed by the caller,
but is ``incorrect'' here for the purpose of emitting VPO RTLs.
The original procedure
was a normal, non-leaf procedure
and stored its result in \texttt{\%i0}.

Another source of trouble here was that VPO decides,
as part of its optimizations,
whether a procedure will have a register window or not;
there is no way for a VPO client to specify this.
The problem then was how the VPO backend should decide
where to store the result.

The solution was to predict whether VPO would 
give a procedure a register window.
VPO's rule for deciding this is simple: 
if a procedure writes to any non-``scratch'' register
(e.g., \%o7 or a local register),
it is given a register window.
The VPO backend determines (predicts) whether VPO 
will make a procedure a leaf procedure or not,
then stores the result in the appropriate location.
The drawback of this is a fragile dependence on VPO's implementation,
which might change at any time.


\subsubsection{Straightforward allocation of local variables can fail}
The VPO backend originally allocated a separate VPO local variable
for each local variable in a procedure's IRTL.
These local variables are ones stored in the procedure's frame
and are referenced using \texttt{m[\%fp-NN]},
or \texttt{\%fp-NN} when an address is needed.
This failed in some cases because VPO chooses the layout and ordering
of local variables.
It will decide whether to optimize access to a variable
by storing it in a register rather than memory.
It will even chose whether to optimize a variable away completely
if it can determine that the variable's result is never used.
The problem is that some programs depend on the order and relative layout 
of variables in memory.
As a result,
the backend initially generated bad code 
for the test program \texttt{returnparam}:

\begin{verbatim}
typedef struct myStructTag {
    char a[16];
    char b[16];
} myStruct;

char* getFirstStr(struct myStructTag* p) {
    return p->a;
}

int main() {
    myStruct s;
    strcpy(s.a, "Hello");
    strcpy(s.b, "World");
    printf("Elements are %s and %s\n", getFirstStr(&s), s.b);
    return 0;
}
\end{verbatim}

gcc inlines a \texttt{strcpy} of a short string literal
into a sequence of memory stores.
The VPO backend originally treated the destination of these stores
as separate variables,
which VPO could reorder in memory.
As result, the translated \texttt{returnparam} program
stored the last two bytes of each literal
in locations that \texttt{printf} did not read.
The solution was to use an array to hold all local variables
and to reference the variables using indexes.
This allows more direct control over storage layout.
The drawback is that this often requires more storage.


\subsubsection{VPO supports SPARC V8, not V9}
VPO currently only supports the SPARC V8 instruction set, not V9.
Since UQBT also supports (mostly) V8,
this is usually not a serious problem.
It does sometimes lead to less efficient code since, for example,
it is not possible to use 64 bit shifts, multiplies,
or other operations.

There are some occasions, where this can cause a problem.
For example, when the \texttt{-f} flag is not used,
UQBT's \texttt{frontsparc.cc} used to inline the V7 compatibility routines 
\texttt{.mul} and \texttt{.umul}
into a sequence of RTLs that require a {\em V9} 64 bit multiply instruction.
\texttt{frontsparc.cc} now generates RTLs that require only V8 instructions.
If UQBT later supports the full SPARC V9 architecture,
it will be hard to use VPO unless it also supports V9.


\subsubsection{Controlling what code is emitted can be difficult}
VPO chooses what order to emit SPARC instructions,
may revise them, and even eliminate them 
for better efficiency.
This is usually desirable,
but can sometimes be a problem for a client such as the VPO backend
that require a particular order for some instructions.
The VPO backend emits VPO RTLs that inline some V7 compatibility routines
such as \texttt{.rem} (represented by UQBT's \texttt{idMods}).
The inlined code for \texttt{.rem}
consists of a signed divide, a signed multiply, 
then a subtract.
Since VPO supports SPARC V8,
the divide must be preceded by a \texttt{WRY} instruction
that puts to most significant 32 bits of the dividend
into the \texttt{\%Y} register.
Unfortunately, VPO moves the \texttt{WRY} {\em after} the divide
regardless of what dependencies are put into the VPO RTLs.
This has not caused a failure yet in testing,
but probably some programs will fail.


\subsubsection{Undocumented VPO RTLs must sometimes be used}
To generate 8 and 16 bit loads,
additional ``semantic'' VPO RTLs must be emitted.
Perhaps these additional RTLs are used 
to decide whether to generate signed or unsigned loads.
It is annoying that the fact that these are required 
does not appear in VPO's noweb documentation.
Fortunately, the \texttt{lcc} compiler front end 
demonstrates how to support byte and halfword loads.
(In general, having the source code for \texttt{lcc} is invaluable
as further {\em documentation} for VPO.)
The code below from the VPO backend illustrates 
what is necessary to emit VPO RTLs for these loads:

\begin{verbatim}
/*====================================================================
 * FUNCTION:        SparcIRTLToVPOBackend::processMemoryRead
 * OVERVIEW:        Emits VPO RTLs for a memory load SemStr.
 * PARAMETERS:      exp: points to the UQBT SemStr for the load.
 *                  cType: expected type of the value being read.
 * RETURNS:         A VPO Rtl_ty_expr for the value read from memory.
 *===================================================================*/
Rtl_ty_expr SparcIRTLToVPOBackend::processMemoryRead(const SemStr* exp,
                                                     Type cType) {
    int currSize = cType.getSize(); // desired size in bits
    // get temp reg to hold the value read from the memory location
    Rtl_ty_loc temp = getTempReg(cType);
    Rtl_ty_loc memLoc = processMemOf(exp, cType);
    Rtl_ty_expr expr = Rtl_fetch(memLoc, currSize);
    
    // VPO requires extra "semantic" RTLs to emit 8 and 16 bit loads
    if (cType.getType() == INTEGER) {
        if (currSize == 8) {
            if (cType.getSigned()) {   // LDSB
                expr = Rtl_binary(Rtl_op_lshift,  expr, Rtl_int(24));
                expr = Rtl_binary(Rtl_op_rshiftA, expr, Rtl_int(24));
            } else {                   // LDUB
                expr = Rtl_binary(Rtl_op_and, expr, Rtl_uint(255));
            }
        } else if (currSize == 16) {
            if (cType.getSigned()) {   // LDSH
                expr = Rtl_binary(Rtl_op_lshift,  expr, Rtl_int(16));
                expr = Rtl_binary(Rtl_op_rshiftA, expr, Rtl_int(16));
            } else {                   // LDUH
                expr = Rtl_binary(Rtl_op_and, expr, Rtl_uint(0xffff));
            }
        }
    } // else LD, LDD, LDF, LDDF, which require no special treatment

    // emit the actual load instruction
    VPOi_rtl(Rtl_assign(temp, ((currSize < 32)? 32 : currSize), expr),
             NULL);
    return Rtl_fetch(temp, currSize);
}
\end{verbatim}


\subsubsection{VPO RTLs do not support some SPARC instructions}
It is not possible to emit a single VPO RTL 
to generate some instructions such as
\texttt{BPOS} (branch if positive) and \texttt{BVS} (branch if overflow set).
These can be implemented using RTLs that generate
a nested pair of conditional branches,
but this is awkward and inefficient.
It is likely that the VPOi interface and the SPARC VPOi extension interface
reflect just what the various VPO clients,
most of which are \texttt{C} compilers, have required over the years.
Ideally, VPO would have an ``escape hatch'' to emit such instructions.


\subsection{Lessons}
The lessons from this experience include:
\begin{itemize}
\item
Significant additional analysis is needed 
for IRTL to be a suitable basis for a VPO backend.
This includes, at a minimum,
analysis of procedure argument and return value information.
Such analysis is already done when producing HRTL,
which suggests that HRTL would be a better representation
for future VPO backend work.

\item
UQBT needs more control over what code and data are generated by VPO.
This includes being able to specify, when necessary,
what instructions must be generated and in what sequence.
For UQBT to be able to implement synchronous signals correctly,
it must be able to instruct VPO that instructions may not be
moved around instruction ``barriers'' that it specifies.
UQBT also needs to be able to control more directly
and more precisely where data is stored
and what loads and stores of that data must be preserved in VPO's output.
We implemented a barrier interface into VPO, but such barrier is 
not part of our distribution. 
\end{itemize}


\subsection{Usage}
To use the IRTL Sparc-to-VPO backend,
build \uqbt\ with \texttt{with-target=sparc}
and then request the IRTL backend using the command line option \texttt{-O}.
This will make \uqbt use the VPO optimizer as a backend
rather than the default low-level \texttt{C} backend.
The Makefile generated in the output directory created by \uqbt\ 
includes rules to run VPO then the SPARC assembler,
and then build the executable for the translated program.


\section{The ARM VPO 2001 Back end}
\label{sec-vpo2001}

{\small
\begin{flushright}
Design: Brian;
Documentation: Brian [Nov 01];
Implementation: Brian [Oct 01].
\end{flushright} 
}

The ARM VPO backend uses the
University of Virginia's Very Portable Optimizer (VPO)
to generate optimized ARM code.
The quality of the optimized code it produces
is about the same as produced by gcc
with optimization level \texttt{-O4}.
VPO provides instruction selection, instruction scheduling, and classical
global optimization.
It has been retargeted to a wide variety of architectures
besides the ARM including the SPARC, Pentium, and MIPS.

The particular ARM architecture supported by the ARM VPO optimizer
is the ARM7TDMI,
which is implemented, for example, by Intel's StrongARM processor.
This architecture has no floating point or integer divide hardware
and only supports 32 bit integers.
However, the ARM VPO backend will emit synthetic
floating point instructions
that make use of traps to invoke a software implementation
of the operations in a runtime library.
The ARM VPO backend supports the calling conventions
described in the document
``The ARM-THUMB Procedure Call Standard'',
document number SWS ESPC 0002 B-01,
published by ARM Limited.
These calling conventions are implemented
by the gcc compiler on the ARM,
and the \uqbt ARM VPO backend uses the gcc libraries.
These libraries include implementations of integer divide and mod
functions that emulate these operations.

The ARM VPO backend also supports little-endian addressing.
The ARM architecture itself is endianness-neutral,
but the ARM backend was designed to generate programs
that could run under Linux on the ARM,
which requires little-endian addressing.


\subsection{Status of the ARM VPO backend}

The ARM VPO backend is largely complete,
at least for source programs that use
integers that are 32 bits or less.
Integers longer than 32 bits could be supported by an emulation library,
but this has not been implemented.
The backend also does not currently support switch statements
(although this would be relatively easy to add).


\subsection{Use of the ARM backend}

To use the ARM VPO backend backend,
build \uqbt with \texttt{with-target=arm}
and then request the VPO backend using the command line option \texttt{-O}.
This will make \uqbt use the ARM VPO optimizer as a backend
rather than the default low-level \texttt{C} backend.
The Makefile generated in the output directory created by \uqbt
includes rules to run VPO then the ARM assembler,
and build the executable for the translated program.
Cross-development GNU gcc, ld, and assembler tools
can be downloaded to build ARM executables
on other platforms such as Linux and Solaris.
It is also possible to find native GNU tools for some ARM platforms.


\subsection{Overview of the ARM VPO backend's operation}

The ARM VPO backend operates much like the C and other backends.
It uses two passes to emit VPO ``RTLs'' and other directives
for a procedure being translated.
The directives and other information
are written to a file called \texttt{procname.cex}
where ``procname'' is the name of the source procedure.
That \texttt{.cex} file is later read by the VPO optimizer,
which then produces an assembler file for the translated procedure.

The backend's first pass scans the procedure's HRTLs to
look for and declare to VPO various things such as
input parameters, block labels,
and references to HRTL variables and registers.
The second pass recursively processes the procedure's HRTLs and
emits directives for each HRTL.
Given a HRTL, 
it checks first whether it is a high-level HRTL such as a CALL\_HRTL,
or if it is a RTLList, a list of low-level RTLs.
If the former, directives for the
control transfer or other high-level HRTL are emitted.
If the latter, directives for each RTL in the list are emitted.

In a little more detail,
the first pass declares each input parameter
with the appropriate size and offset in the ARM procedure frame.
It also declares VPO labels for each HRTL block label,
and declares each called procedure as an external reference.
A VPO variable called ``locals'' is declared as an array
to hold all HRTL local variables:
that is, the variables stored in the abstract HRTL frame and
referenced using an address relative to \texttt{\%AFP}.
We declare a single array for the locals
instead of separate VPO variables
to ensure that the locals
have the original order and offsets in the frame.
We access the locals using explicit offsets into the ``locals'' array.
For the same reason,
we also declare an array ``symVars'' to hold all HRTL symbolic variables
such as \texttt{v[0]}.
VPO local variables are also declared
for each referenced HRTL register, temporary,
and machine-dependant register such as \texttt{\%Y}.
The first pass also declares a 64 bit temporary for use
when marshalling arguments in procedure calls.

The ARM VPO backend first emits code to store
incoming parameter registers into the variables
allocated to hold those parameters.
If the procedure is the main procedure of the source program,
code is emitted to swap the elements of \texttt{argv}.
The second pass then emits code for the HRTLs in each basic block of
the procedure.
VPO temporary registers are used extensively
to hold intermediate values
in order to ensure that no VPO ``RTL''
becomes too complex for VPO to process.
VPO requires that each VPO RTL correspond
to a single target machine instruction.

Code generation is fairly straightforward except for parameter passing in
procedure calls.
The ARM calling conventions we use
pass both integer and floating point values
in ARM registers \texttt{r0-3} and, if necessary,
on the stack in reverse order.
It is possible for the two ``words'' of a 64 bit double floating point
value to be split between \texttt{r3} and the stack.
If so, a temporary memory location is used to marshal the double
since there is no direct data path on the ARM between
the floating point and the integer registers.

Another complication of generating code for the ARM
is its limited support for immediate values in instructions.
The ARM only supports 8 bits immediate values
in data processing instructions
and only 12 bit offsets in load and store instructions.
This means that constant addresses and values larger than 8 bits
must be stored in memory
and at a location close to the instructions that reference them.
To deal with this,
we store such constants in the code stream
(with a branch around them at the start)
and use PC-relative addressing to access them.
We build a data structure to hold such ``deferred'' constants
during code generation and then emit the constants
at the end of the procedure's code.


\subsection{Experience}

One limitation we discovered with the ARM VPO optimizer
is its limited support for ARM addressing modes.
This made the code sequences for any byte swaps
longer than would otherwise be possible.
For example, a 4 byte swap requires 10 ARM instructions currently.
With support for the ARM addressing modes that support shifted
operands, this could be done in 7 instructions.
If the ARM backend supported conditional instructions
(instructions that are only executed if a condition is true),
just 4 instructions would be needed.
Jack Davidson reported that his team at the University of Virginia
is adding support for more ARM addressing modes.


