\documentclass[letterpaper]{article}
%\usepackage{fullpage}
%\usepackage{hyperref}
\usepackage{graphicx}
%\usepackage{pst-all}
\usepackage{pstricks}
\usepackage{pst-node}
\usepackage{colortab}
%\usepackage{subfigure}
\usepackage{times}
\usepackage{mathptm}
\begin{document}
\bibliographystyle{unsrt}

% Definition of title page:
\title{Annotating Java Class Files with Virtual Registers for Performance}
\author{\textbf{Joel Jones} (\texttt{jjones@uiuc.edu})\\
\textbf{Samuel Kamin}\\
Department of Computer Science\\
University of Illinois at Urbana-Champaign}
\date{}

\maketitle
\newcommand{\vrzero}{\mbox{${\mathsf{vr_{0}}}$}}
\newcommand{\vrone}{\mbox{${\mathsf{vr_{1}}}$}}
\newcommand{\vrtwo}{\mbox{${\mathsf{vr_{2}}}$}}
\newcommand{\vrthree}{\mbox{${\mathsf{vr_{3}}}$}}

\begin{abstract}
The Java \texttt{.class} file is a compact encoding of programs for a 
stack-based virtual machine.
It is intended for use in a networked environment, which requires 
machine independence and minimized consumption of network bandwidth.
However, as in all interpreted virtual machines, performance does not 
match that of code generated for the target machine.
We propose verifiable, machine-independent annotations to the Java class file 
to bring the quality of the code generated by a ``just-in-time'' 
compiler closer to that of an optimizing compiler without a 
significant increase in code generation time.
This division of labor has expensive machine-independent analysis performed 
off-line and inexpensive machine-dependent code-generation performed on the 
client.
We call this phenomenon ``super-linear analysis and linear exploitation.''
These annotations were designed mindful of the concurrency features of 
the Java language.
In this paper we report results from our a machine-independent, prioritized 
register assignment.
We also discuss other possible annotations.
\end{abstract}

\section{Introduction}
The Java \texttt{.class} file is a compact encoding of programs for a stack-based virtual 
machine.
It is intended for use in a networked environment, which requires 
machine independence and minimized consumption of network bandwidth.
However, as in all interpreted virtual machines, performance does not 
match that of code generated for the target machine.
To ameliorate this problem, many implementations of the Java Virtual 
Machine (JVM) use ``just-in-time'' (JIT) compilers, in which Java 
bytecodes are translated into machine code.

This environment differs from both 
conventional batch compilation and compilation for interactive 
languages.\cite{John88a} \cite{STAN//CS-TR-94-1520}
In conventional compilation, to a first order of approximation, 
compilation costs are ignored, and the target machine is known;
no holds are barred in terms of aggressive analyses and 
machine-dependent trickery.
In the interactive environment, the target machine is known, but the 
cost of compilation is constrained by the need to maintain interactive 
responsiveness.
By contrast, in the network client/server model, compilation 
to bytecode is done 
off-line and is, to a first-order of approximation, unconstrained. 
However, it must generate portable code and therefore cannot perform 
machine dependent optimizations.
Compilation of bytecode to target machine code is performed on 
the client and may therefore be very machine-specific.
However, since this compilation time is added to the overall response 
time seen by the user, it must be minimized.
As a result, the quality of the code generated by ``just-in-time'' 
compilers does not match that of an optimizing compiler for the 
same machine.

We propose machine independent annotations to the Java class file 
\cite{lindholm:1997}
to bring the quality of the code generated by a ``just-in-time'' 
compiler closer to that of an optimizing compiler without a 
significant increase in code generation time.
The annotations proposed are a specification of a prioritized register 
assignment, load-store elimination, and register spilling.
Our notion is to provide a division of labor between the class file 
annotator on the server and the code generator on the client.

One guiding feature of our annotations, and indeed of any 
annotations of the Java class file, is that the annotations can be 
safely ignored by those implementations of the Java VM that do not 
recognize them.
This precludes any transformation on the bytecode that results in a 
\texttt{.class} file which is unverifiable or incorrect when 
considered without the annotations.

The key idea is that the machine-independent analysis phase performed 
by the Java compiler may be expensive, but the results of that 
analysis may be expressed compactly and used inexpensively.
We call this phenomenon ``super-linear analysis and linear exploitation.''
% This particular division of labor raises interesting issues, due to 
% the differences from traditional batch compilation and from interactive 
% environments such as Smalltalk\cite{John88a} or 
% Self\cite{STAN//CS-TR-94-1520}.
% Unlike a traditional batch compilation environment, the Java compiler 
% does not have 
% access to information about the machine on which the program will run.
% But, we can spend a lot of time on analysis in the annotator, unlike 
% the demand for extremely short response time required in an 
% interactive programming environment.
% 
% Another requirement of the network distributed code environment is 
% portability.
% This results in two important problems for our system.
% First, we must produce annotations that are machine-independent, or 
% as a minimum, biased toward current computer architectures.
% Second, our annotations must be verifiable by the receiving Java 
% virtual machine (JVM).
% This verification must ensure that the code produced by the 
% combination of the standard Java bytecodes and our annotations will 
% not corrupt the virtual machine.

The following sections describe 
in more detail the environment we are trying to produce code for
followed by a concrete example showing Java source, Java bytecodes, and 
SPARC machine code.
Then, the properties of the machine code generated 
by our ``just-in-time'' compiler, 
the semantics of our register assignment annotation, 
and annotation generation are discussed.
Following this are more examples of Java source code, the corresponding 
Java byte code, and the machine code generated with 
our register assignment annotation, including timing information.
We then cover related work in solving this sort of problem and then 
conclude with a summary of our contributions.

\section{The Overall Environment}
In Figure~\ref{fig:JVMexecution} we see the environment in which our 
annotated \texttt{.class} file must operate.
A client makes a request for some Java code, packaged either as a 
\texttt{.class} file, or as a \texttt{.jar} file containing a 
\texttt{.class} file.
The server sends the file to the client.
This annotated code is used by our modified JVM to produce machine 
code, as in any Just-in-time (JIT) compilation system.
In the figure, $t_{1}$ represents the time from when the client 
requests a Java \texttt{.class} file to the time that the 
client first sees results, while $t_{2}$ represents the time from the 
\texttt{.class} file request to when the computation completes.
We are interested in minimizing both $t_{1}$ and $t_{2}$.
If we were interested in minimizing just $t_{1}$, then we could use 
an interpreter over the bytecodes and see our first results almost 
immediately.
If we were interested in minimizing just $t_{2}$, then for a 
program which was compute intensive, we could tolerate a large amount 
of traditional optimizing compiler analysis being done by the JVM.

Obviously, the client-side code generator could perform the same control and 
data flow analysis that the server-side annotator does.  
But our approach is to do as much work up front as possible.  
There are two advantages to having the analysis done by the server.  
First, time is saved by having the analysis done once, not every time 
a class file is compiled to machine code.  
More importantly, many optimizations can be divided into a 
super-linear analysis phase and a linear exploitation phase.
By performing the expensive analysis phase and recording the results 
as annotations, we can then very quickly produce high-quality code in 
the code generator.

The first part of our system, the annotator, takes as input \texttt{.class} 
files and produces as output annotated \texttt{.class} files.
These annotations are produced by using the Java bytecodes as an 
intermediate representation and applying modifications of traditional 
optimizing compiler algorithms to them.
We then add as annotations to the output \texttt{.class} file the 
results of these algorithms.
The size of these annotations must not be overly large, as this would 
increase the amount of time needed to transfer the annotated 
\texttt{.class} file across a network.

\begin{figure}[tbp]
    \centering
	    %\includegraphics[scale=0.8]{execution.eps}
\begin{psmatrix}[rowsep=18bp,colsep=20bp]
  {\Large\sf Server}  &&& {\Large\sf Client}    \\
                      &&& \cnode*{3bp}{REQ}   & \pnode{TIMERSTART}\\
  \cnode*{3bp}{REPL}  \\
  			&&& [name=GENCODE]\psframebox{% 
			\parbox{1in}{modified JVM produces native code}} & \\
                      &&&  [mcol=l]execution begins & \\ 
  			&&&  [name=FIRST,mcol=l]first result & \pnode{FEND}\\
 			&&&  [name=FINAL,mcol=l]final result & \pnode{FIN}
\psset{arrowsize={4pt 2}}
\ncline[offset=-10bp]{|->|}{TIMERSTART}{FEND}\naput{$t_1$}
\ncline[offset=14bp]{|->|}{TIMERSTART}{FIN}\naput{$t_2$}
\ncline{->}{REQ}{REPL}\nbput[nrot={:D}]{.class request}
\ncline{->}{REPL}{GENCODE}\nbput[nrot={:U}]{annotated .class}
\end{psmatrix}
	\caption{Java Virtual Machine Execution}
	\label{fig:JVMexecution}
\end{figure}

\section{Motivating Example}\label{sec.motivate}
Before going into detail about how annotations are generated and  
the exact nature of the mechanisms in the code generator to exploit 
them, let's examine a very simple example first.

In Figure~\ref{fig:foracc}, we have an example of the Java source for 
a ``for'' loop at the upper left.
This ``for'' loop has three values, \texttt{sum}, \texttt{i}, and the 
constant \texttt{3}.
Below it, we have the Java bytecodes corresponding to the source.
On the right-hand side, we have the SPARC machine code generated from 
the bytecodes.
The rightmost column of the Java bytecodes block is a register 
assignment for the bytecode to its left.
We call this register assignment ``virtual registers'' or VRs.
For the SPARC machine code, instructions 
for a single Java bytecode are separated by single gray horizontal lines.
For both Java bytecodes and SPARC machine code, basic blocks 
are separated by double horizontal lines.
The Java bytecode is formatted with the first column the bytecode 
PC, the second column the Java 
bytecode and any arguments, and the third column being the ``VR'' 
annotation.

The assignment for \texttt{sum} is \vrzero; \texttt{i},
\vrtwo; and \texttt{3}, \vrone.
Also, the assignment of physical registers for virtual registers 
starts at \texttt{\%l0}.
The first piece of machine code starts with a SPARC machine idiom of 
using global register \texttt{\%g0}, which is always zero, to 
initialize a register with an integer value.
Next, we see an empty slot in our machine code diagram, indicating 
that no machine code was generated for the \texttt{istore\_0} bytecode.
The next interesting set of instructions occurs in the code for the 
\texttt{iinc} bytecodes.
The numbers after the \texttt{iinc} bytecodes indicate which local 
slot is being incremented, and what it is being incremented by, 
respectively.
This is part of the normal encoding for the \texttt{iinc} bytecodes.
Each \texttt{iinc} bytecode is translated into a single SPARC add 
instruction, since the values
referenced by both bytecodes are being stored in physical registers.

\begin{figure}[ht]
\begin{tabular}{p{2.7in}cp{1.7in}}
\begin{verbatim}
    int sum = 0;
    for (int i = 0; i < 3; i++) {
        sum += 1;
    }
\end{verbatim}
    \begin{tabular}{|lll|}
    \hline
        0 & \texttt{iconst\_0} & 1\\
        1 & \texttt{istore\_0} & 1\\
        2 & \texttt{iconst\_0} & 0\\
        3 & \texttt{istore\_1} & 0\\
        4 & \texttt{goto 13} & --\\ 
        \hline 
        \hline
        7 & \texttt{iinc 0,1}  & 1\\
        10 & \texttt{iinc 1,1}  & 0\\
        \hline 
        \hline
        13 & \texttt{iload\_1}  & 0\\
        14 & \texttt{iconst\_3}  & 2\\
        15 & \texttt{if\_icmplt 7}  & 0,2\\
        \hline
    \end{tabular}
&
\parbox[t]{0.25in}{
      \vspace{1in}
	  $\Rightarrow$
}
&
\begin{tabular}[t]{|ll|}
 	\hline
 	\texttt{mov} & \texttt{\%g0, \%l1}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 	\texttt{mov} & \texttt{\%g0, \%l0}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 	\rnode{A}{\texttt{b}} & \\
 	\texttt{nop}  & \\
	\hline
	\hline
 	\texttt{addcc} & \rnode{D}{\texttt{\%l1,1,\%l1}}  \\
	\hline
 	\texttt{addcc} & \texttt{\%l0,1,\%l0}  \\
	\hline
	\hline
	  & \\
	\NAC{gray}\hline\ENAC
 	\rnode{B}{\texttt{mov}} & \texttt{3, \%l2} 
	\ncbar[nodesep=3pt,angle=180]{<-}{B}{A}\\
	\NAC{gray}\hline\ENAC
 	\texttt{cmp} & \texttt{\%l0, \%l2}  \\
 	\texttt{bl} & \rnode{C}{\texttt{\ }}
	\ncbar[nodesep=10pt,angle=0]{<-}{D}{C} \\
 	\texttt{nop} & \\
	\hline
\end{tabular}
\end{tabular}
\caption{For Loop with Accumulator \label{fig:foracc}}
\end{figure}

\section{The Code Generation Environment}
In Figure \ref{fig:codegenenv} and in the following sections we present the 
general guidelines and properties that our code generator follows.
Figure \ref{fig:codegenenv} gives a very general machine model.
To make things more concrete, we will use the SPARC as our example 
machine in the following sections.
With the exception of its register windows, the SPARC is like most modern 
RISC architectures.
Furthermore, since all architectures perform better when registers are 
used as much as possible, most of the 
principles guiding the SPARC implementation hold everywhere.
\footnote{Including the popular Intel x86 and embedded 
versions of the Motorola 68K.}
% The exception to this is when we consider shared memory access, which 
% is covered in Section \ref{sec:concImp}.
\begin{figure}[tbp]
	\centering
	    \includegraphics[scale=1.0]{env.epsi}
	\caption{Run-time Environment.  The stack location of \vrzero is 
	reserved for spilling register \vrzero; it may or may not contain the 
	same value at other times.}
	\label{fig:codegenenv}
\end{figure}

Figure \ref{fig:codegenenv} gives the overall structure of the 
machine environment we are generating code for.
The bounds of the current activation record (stored on the stack) is
maintained by 
two registers, the stack pointer (SP in the figure) and the frame 
pointer (FP in the figure).
Temporaries used by the code generator are also set aside in the 
registers (shown as TEMP0 and TEMP1 in the figure).
Values kept primarily in registers are shown in the table labeled 
``Registers.''
Values which primarily reside in memory are shown only in 
the table labeled ``Stack.''
Objects and arrays are kept in the heap and references to them are 
kept in registers or on the stack (shown as arrows in the figure).
The following sections give details related to the environment 
sketched in Figure \ref{fig:codegenenv}.

\subsection{Simple Properties}
Our central annotation is the virtual register (VR) annotation.
The basic notion is that there is a set of virtual register numbers 
for each Java bytecode which correspond to the operands of the bytecode.
The code generator uses the VR annotation to generate a register 
assignment for the machine instructions.
These VRs are arranged in \emph{priority} order, meaning that the 
lower the VR is, the more likely it is to be assigned to a physical 
register in the code generator.
We will deal with the details of the VR annotation
in more detail in Section~\ref{VRs}.

Below are some simple properties that guide our code generation process.
We use the term ``physical register(s)'' to refer to the registers 
that exist on the machine we are generating machine code for.  
We use the term ``physical location'' to refer to some location on the 
machine, either in a physical register or in memory.
The memory that is used for virtual registers is contained in a run-time 
stack, which contains additional information.
\begin{itemize}
    \item  All virtual registers have at least one physical location.
        Virtual registers which primarily reside in physical registers 
        have two physical locations, their physical register and their 
        stack location.
	For machines without register windows, the stack locations are needed 
	for preserving caller-saved registers when making function calls.
	We will see an additional need for all values having a place on the stack 
	when we deal with spilling.
	Other virtual registers will reside only in one physical location, 
	on the stack.
    \item 
    Constants are either folded into the machine instructions or 
    are statically allocated alongside the code for each method.
    The memory for the code and constants is allocated in the heap, but is 
    otherwise treated statically by our code generation system.

	\item  There is no explicit bytecode operand stack.
	Although Java bytecodes specify manipulations of a run-time value 
	stack, this stack is not explicitly mimicked by the generated machine 
	code.
	All VRs not assigned to physical registers are loaded into physical 
	registers if necessary, then written out, using physical registers 
	dedicated to such temporary use.
	A more detailed description of this process is given in the next 
	section.

    \item A simple data structure, the VR location table, provides the mapping 
    from VRs to physical locations.
    Conceptually, the code generator keeps two sets of mapping, one for 
    virtual registers residing only in memory, and one for virtual registers 
    additionally residing in a physical register.
	Imagine we have a machine where only two physical registers remain 
	after setting aside registers for use as temporaries.
    Further, assume that the method we are compiling has five VRs, 
    numbered 0 -- 4, specified in all its bytecodes. 
	An example of this data structure can be seen in Figure 
	\ref{fig:whereStored1}.
    \begin{figure}[h]
    	\centering
	    \begin{tabular}{l|l|l} \label{sec:datastruc}
	    virtual register & physical register & memory \\
	    \hline
	    0 & \%l0 & [\%fp - 12] \\
	    1 & \%l1 & [\%fp - 16] \\
	    2 & -- & [\%fp - 0] \\
	    3 & -- & [\%fp - 4] \\
	    4 & -- & [\%fp - 8] \\
	    \end{tabular}
	\caption{VR Location Table; \textsf{MAXREGS} = 2}
	\label{fig:whereStored1}
    \end{figure}
    This indicates that virtual registers 0 and 1 will be primarily
	stored in physical registers \verb|%l0| and \verb|%l1| respectively 
	and that virtual registers 2, 3, and 4 will be primarily stored in 
	memory at 0, 4, and 8 off the frame pointer.
	
\end{itemize}

\subsection{Non-register Resident Values}
To manage situations where the number of physical registers is 
insufficient to contain all the virtual registers, a scheme to place 
the excess virtual registers into memory has been devised.
There are several things to note.
\begin{itemize}
    \item  Several physical registers are reserved for temporary use.
    The lifetime of the values placed into these registers typically does not 
    extend beyond the span of the machine code generated for one Java bytecode.
    \item  For a given virtual register, its location on the stack is at a 
    fixed offset from the frame pointer.
    \item  On machines which allow reading and writing of a single 
    physical register in an instruction (e.g. \verb|add %l0,%l1,%l0|), 
    only two temporary registers are needed (actually, 
    two temporary registers for integral values and another two 
    for floating-point values.)
	Note that on the SPARC, the destination of an instruction is the 
	rightmost argument.
\end{itemize}

The general scheme for generating machine code is as follows, doing 
the steps below for each bytecode:
\begin{enumerate}
	\item For all input VRs to the bytecode which are not assigned a 
	physical register, generate a load from their stack location into 
	a temporary physical register.
	\item If the output VR from the bytecode is not assigned a physical 
	register, set aside a temporary physical register.
	\item generate the appropriate machine instruction using 
	temporary and/or permanent registers
	\item If the output VR from the bytecode is not assigned a permanent
	physical register, generate a store from the temporary physical 
	register to its location on the stack.
\end{enumerate}

The VR location table is determined by the code generator in the back-end 
by using information gathered during the bytecode and VR annotation 
verification process.
The verification step is used by the JVM to insure that the bytecodes 
of a downloaded program do not corrupt the virtual machine.
We have modified this step to additionally verify the VR annotation 
associated with each method.
As a side effect of this process, the type of each virtual register is 
determined.
For machines with a split general purpose register set and floating 
point register set, object references and integral types are 
assigned to the general purpose register set, and floating point types 
are assigned to the floating point register set.
Any virtual registers not assigned to physical registers are assigned 
locations on the stack.
This process is also responsible for  generating procedure entry 
prologues.

The verification process allows us to make an important optimization.
Since the verification process ensures that every use of a local JVM 
frame slot (or equivalently a local variable) is preceded along all 
paths by a definition of that slot, we can logically eliminate most load/store 
bytecodes that reference locals.
As an example of the machine code generated using this scheme, here 
is a bytecode and its associated annotation:
\begin{tabular}{ll}
     ``\texttt{iadd} & 2,3$\rightarrow$4'' \\
\end{tabular}
which signifies that the \texttt{iadd} bytecode is annotated with 
three virtual registers, 2, 3, and 4.
The \texttt{iadd} bytecode, in the semantics of the stack-oriented 
JVM, removes the top two integer operands off the bytecode operand stack, adds 
them, and pushes the resulting integer result onto the stack.
Our VR annotation has the semantics: take the 
values contained in virtual registers 2 and 3, add them, 
and place the result in virtual register 4.
If we have a SPARC-like machine with only two allocatable physical 
registers for holding integers, then we generate the following, 
assuming the mapping from Figure \ref{fig:whereStored1}:
\begin{verbatim}
	! virtual registers > vr1 live in the activation record
    ld [%fp - 0], %g1  ! copy vr2 -> g1
    ld [%fp - 4], %g2  ! copy vr3 -> g2
    add %g1,%g2,%g1    ! compute result
    st %g1, [%fp - 8]  ! copy result to vr4
\end{verbatim}
(We are using \verb|%g1| and \verb|%g2| as temporary registers.)
If we can allocate four physical registers to virtual registers, then 
the mapping would become that shown in Figure \ref{fig:whereStored2}.
    \begin{figure}[h]
    	\centering
	    \begin{tabular}{l|l|l}
	    virtual register & physical register & memory \\
	    \hline
	    0 & \%l0 & [\%fp - 4] \\
	    1 & \%l1 & [\%fp - 8] \\
	    2 & \%l2 & [\%fp - 12] \\
	    3 & \%l3 & [\%fp - 16] \\
	    4 & -- & [\%fp - 0] \\
	    \end{tabular}
	\caption{Mapping from VRs to Physical Registers; \textsf{MAXREGS} = 4}
	\label{fig:whereStored2}
    \end{figure}
We would generate:
\begin{verbatim}
	! virtual registers > vr3 live in the activation record
    add %l2,%l3,%g1      ! compute result
    st %g1, [%fp + 36]   ! copy result to vr4
\end{verbatim}

\section{Annotations}\label{sec.OurAnnotations}
We have designed four sets of annotations: 
a register assignment (VRs),
redundant load/store elimination (``remove if physical,'' RIPs), 
register spills (swaps), and copies.
Below is a description of the VR annotation.
Currently, the VR annotation is implemented in both the annotator and 
in the code-generator.
The RIP and swap annotations, which have not been implemented yet, are 
described in Section~\ref{sec-futwork}.
We have a ``copy'' annotation which indicates where a load from one 
local followed by a store to another local corresponds to a copy 
assignment from one local to another.
We will not deal with the copy annotation any further in this 
presentation.

\subsection{VRs}
\label{VRs}
The VR annotation is an assignment for each Java bytecode of a set of 
virtual register numbers which correspond to the operands of the 
bytecode.
The number of virtual registers per bytecode varies.
For example, as we have seen above, a binary arithmetic operator 
will have three virtual registers---two for the input and one 
for the result.
A method call bytecode will have a variable number of virtual 
registers---one for the object, one for each argument to the 
method, and one for the return value.

The salient characteristics of this annotation
are that VRs are assigned their priority based upon their importance 
and that the number of distinct virtual registers is minimized.
The priority is equivalent to the inverse of the virtual register 
number.
Disjoint live ranges of the same type may be assigned to the same virtual 
register.
This makes each VR \emph{monotyped}, i.e. a VR can only ``carry'' one 
type of value throughout the entire method.
This includes reference types, taking into account the least-upper 
bound along the inheritance and interface hierarchies induced by the 
data-flow algorithm of the bytecode verification procedure\cite{lindholm:1997}.
For example, if \vrzero is used as a reference to an object of class A at 
one point in a program, 
it may not later be used as an integer or even as a reference to an 
object of class B, unless class A and class B have a 
type-compatible superclass.

This annotation uses an unsigned one byte quantity 
for each virtual register.
The values 0--254 indicate a valid virtual register number and the 
value 255 indicates no virtual register assignment.
More information on the VR usage for every bytecode can be found in 
\cite{Jones:annotationSemantics:1997}.
% The notion of virtual register here is similar to that found in the 
% literature.	

\subsection{Generating VRs}
The process of generating our VR annotation is similar to that of
other register allocators.
Once we have discovered the values that are actually used by a method, 
we proceed using standard graph-coloring techniques, with an 
important distinction --- we don't know the number of physical 
registers.
Therefore, our algorithm for finding a register assignment
consists of the standard algorithm modified to operate without this 
vital piece of information.
We will begin by describing the Chaitin graph coloring register 
allocator, which forms the basis for our allocator. 
\cite{Chaitin:Auslander:Chandra:Jocke:Hopkins:Marksteinjocl:1981}
We will then proceed by giving our modifications to the Chaitin 
algorithm. 

Finding a register allocation can be viewed as a graph coloring problem.
An interference graph is constructed where each node represents a 
value (live range) from the program and the edges are between values which are 
simultaneously ``live.''
The goal is to find a $k$-coloring of the interference graph, where 
$k$ is the number of physical registers.
We can view this process as involving an oracle that tells us whether 
or not a $k$-coloring is possible (using a particular heuristic).
If it is, then the coloring of the interference graph indicates which 
values should be assigned to which physical registers.
If a $k$-coloring isn't possible, then a value is chosen to be 
spilled (i. e. to reside in memory), effectively removing its node 
from the graph, and another attempt to $k$-color 
the graph is made.
This process continues until the graph is colored and thereby a 
register assignment obtained.

In our allocator, we also view the register assignment problem as 
graph coloring of the interference graph.
However, we have to change our abstract notion of the problem to deal 
with the fact that we don't know the value 
of $k$, the number of physical registers.
Therefore, instead of attempting to find a $k$-coloring, we are 
actually trying to find the minimum $k$, such that a $k$-coloring of 
the graph exists.
This gives us a coloring that tends to reduce the number of registers;
although this number may well be larger than the actual number of 
registers of a particular machine, it is still a logical place to 
start.
Another aspect of our environment that we must deal with is the 
need for verification.
We do this by introducing edges into the interference graph between 
nodes that have differing types.
This insures that every VR is \emph{monotyped}, as discussed above.
A final concern that arises in our environment is that we must 
prioritize our colors --- in a very abstract sense, turning our colors 
into a gray-scale.
In the normal Chaitin allocator, which physical register holds which 
live ranges doesn't matter.
In our prioritized VR scheme, on the other hand, we need to decide 
beforehand which registers should be spilled first, and it is 
simplest to use the register number to indicate its priority.
Thus there may be no difference between using register 1 and using 
register 10 \emph(if the machine has ten registers), but there is a 
difference if the machine has fewer registers and we are forced to 
spill one; register 10 has the lower priority, so it will be the one 
spilled.
Therefore, we use a set of three functions, called the ``Haifa 
heuristics'' \cite{bernstein:89a} to order our colors so that the 
color that holds the most important live ranges are numbered lower.
These heuristics take into account the number of uses of the live 
range, and how many other live ranges are simultaneously live with 
this live range.
Once this prioritization has been calculated, the VR annotation is 
added to the \texttt{.class} file.

% Obviously, we can't use the standard techniques unmodified, since we 
% do not know the value of $k$.
% Therefore, we must assign virtual register numbers to 
% values carefully.
% The following description of the Chaitin algorithm is due to Briggs, 
% \cite{Briggs:phd:1992}
% with the removal of phases that are not used in our allocator.
% \begin{description}
%     \item[Renumber]  Find all the live ranges in a method and 
%     number them uniquely.
% 
%     \item[Build]  Construct the interference graph. 
% 
%     \item[Spill Costs]  For every live range, calculate an estimate of 
%     the cost of the load and store instructions that would be required 
%     to spill it.
% 
%     \item[Simplify]  Repeatedly remove nodes from the interference 
%     graph with degree $<k$.
%     As each node is removed, place it on a stack.
% 
%     \item[Select]  Pop each node from the stack, and insert it back 
%     into the interference graph, giving it a color distinct from its 
%     neighbors.
% \end{description}
% 
% We do this by using the same sort of tactics that a Briggs-Chaitin 
% \cite{Chaitin:Auslander:Chandra:Jocke:Hopkins:Marksteinjocl:1981}
% \cite{Briggs:phd:1992}
% graph-coloring register allocator uses when it decides which 
% values to spill.
% Our approach is to successively run a coloring algorithm with the 
% number of physical registers decreased on each iteration.
% In this way, we produce a coloring of virtual registers.

% We now describe those phases of our VR-based 
% graph coloring register allocator which differ from the 
% Chaitin algorithm as simplified above.
% The description below gives the phases of the coloring algorithm which 
% were changed or were added, and a description of the modification.
% \begin{description}
%     \item[Find $k$]  We set the initial value of $k$, the desired 
%     number of colors, to the max degree of the graph minus one.
%     Starting this way, we color by removing nodes from the graph, and 
%     reducing $k$ and coloring, until the graph is colored.
% 
%     \item[Build]  In building the interference graph, we additionally 
%     add edges to represent those values which have different types.  
%     This is used to ensure verifiability in the code generator.
% 
%     \item[Spill Costs]  Rather than using precise information about 
%     the cost of spills and other instructions, we set the cost of 
%     instructions which are not loads or stores to one, and set the 
%     cost of a load or a store to ten.
%     This represents an estimate of the comparative cost of the 
%     differing instruction types.
% 
%     \item[Prioritize]  Priorities are assigned using the 
%     ``Haifa''\cite{bernstein:89a}
%     heuristics, after the \emph{Select} phase has run.
%     These heuristics are three different functions which attempt to 
%     measure the spill cost in slightly different ways, taking into 
%     account the degree and extent of each live range in different ways.
%     The function which produces the lowest total cost is chosen to be 
%     the cost measure for a given method.
%     This cost measure is then used to produce a complete ordering over 
%     the virtual registers.
% \end{description}
% After our modified algorithm is run, we add the VR annotation to the 
% \texttt{.class} file.

% We will proceed by elaborating on the detail of the process described 
% above by first presenting some definitions, then give some details 
% of how our annotator generates the input to the Briggs-Chaitin 
% allocator from the byte code, and then give a unified description of 
% the regular allocator and our modifications to it.
% 
% The following definitions are from Muchnick\cite{Muchnick:1997}.
% %will prove useful in the further discussion of our register allocator.
% \begin{description}
% 	\item[reaches] A particular definition (i.e. assignment of a value to 
% 	a variable) is said to reach a given point in a procedure if there is 
% 	an execution path from the definition to that point such that the 
% 	variable may have, at that point, the value assigned by the definition.
% 	This is also called \emph{reachability}.
% 	\item[du-chain] The du-chain for a variable connects a definition of 
% 	that variable to all the uses it may flow to, i.e. reaches.
% 	\item[web]  A web is a maximal union of du-chains. 
% 	%such that, for each 
% 	%definition $d$ and use $u$, either $u$ is in the du-chain of $d$ or 
% 	%there exist $d~=~d_{0}, \dots, u_{0},d_{n},u_{n}~=~u$, such that, for 
% 	%each $i$, $u_{i}$ is in the du-chains of both $d_{i}$ and $d_{i+1}$.
% 	In other words, a web connects together du-chains whose definitions reach
% 	uses in common.
% 	A web represents the allocatable object for register allocation, 
%         serving as the nodes in the graph to be colored.
% 
% 	\item[liveness] For a given variable (here, a web) and a given point 
% 	in the program, liveness is whether there is a use of that variable 
% 	along some path from the point to the exit.
% \end{description}
% 
% Like most compilers, the input to our register allocator is a 
% low-level intermediate code --- in our case, Java bytecode.
% We must determine which of the values specified in the bytecode 
% (namely variables, temporaries, and large constants) are reasonable to 
% assign virtual register assignments to, and therefore more 
% susceptible to being placed into physical registers by the 
% just-in-time compiler.
% We do this by simulating the operation of the bytecodes, keeping track 
% symbolically of what values are on the JVM stack at all points in all 
% potential executions.
% This process also finds the control structure of the bytecodes.
% Then, def-use chains (du-chains) are formed.
% This is done in the usual way, by using Kildall's iterative forward 
% data-flow analysis to calculate reachability\cite{Muchnick:1997}.
% 
% The following description of a Chaitin allocator, as given in Briggs 
% \cite{Briggs:phd:1992}
% gives a top-level overview of the allocation process, divided into 
% individual phases.
% We will describe our algorithm by mixing Briggs' description of the 
% Briggs-Chaitin allocator with our modifications incorporated.
% In the following list, starred items are those phases of the 
% algorithm which we have have modified.
% Each of these phase descriptions will begin with the 
% Briggs-Chaitin version, (potentially) followed by our modification.
% \begin{description}
% 	\item[renumber] Coalesce the def-use chains, creating the set of 
% 	``webs'' for which registers are allocated.
% 
% 	\item[build *] Construct the interference graph.  
% 	Edges are added between those webs which are simultaneously live.  
% 	Then, in a modification to the standard algorithm to support verification 
% 	in the client, additional edges are added between those webs which are of 
% 	incompatible types.
% 	For example, if we have webs 0 and 1 of type integer and webs 2 and 3 
% 	of type float, the following edges are added if they do not already 
% 	exist due to simultaneous liveness: $\{(0,2), (0,3), (1,2), (1,3)\}$
% 
% 	\item[spill costs *] Spill costs are calculated for each web, 
% 	based on an estimate of the cost of the load and store instructions 
% 	that would be required to spill a particular web.  
% 	The cost of each bytecode that uses a web is weighted by $10^{d}$ 
% 	where d is the instruction's loop nesting depth.
% 	Our modification uses an estimate that is machine independent, 
% 	such that the cost of a load or store is some $>$ 1 multiplier of the 
% 	cost of non load/store instructions.
% 
% 	\item[find $k$ *] Set $k$ to the number of physical registers.
% 	Our modification, as described above, is to set $k$ to the max 
% 	degree of all nodes in the interference graph.
% 	
% 	\item[simplify *] Remove from the interference graph all nodes with 
% 	degree $< k$.
% 	If at any point there is a node with degree $\geq k$, choose the 
% 	node which has the lowest spill cost and remove it from the graph.
% 	This test is unnecessary in our version of the algorithm.
% 	
% 	\item[repeat] Set $k$ to $k-1$ and if $k > 0$ goto simplify.
% 	
% 	\item[collapse] Merge webs that have identical colors.
% 	
% 	\item[prioritize *] Assign ``priorities'' to the webs based upon the 
% 	``Haifa''\cite{bernstein:89a} heuristics.
% 	These consist of three functions that calculate the cost of keeping 
% 	a particular value in a register.
% 	For each of the three functions, calculate the sum of the value of the 
% 	function on each web.
% 	Choose the function which produced the lowest total cost and sort the
% 	webs based upon the cost for that function.
% 	Assign the priorities (VR assignment) for each web.
% 	Write out the annotation to the \texttt{.class} file.
% 	
% \end{description}

\section{Examples}
In the following pages are two examples of code generation for 
the SPARC using the annotation scheme described above.
The annotations were produced by our compiler, which accepts 
\texttt{.class} files as input and produces annotated \texttt{.class} 
files as output.
The SPARC machine code shown was produced by our code generator embedded 
within the kaffe JVM \cite{kaffeURL}.
The general format of these examples follows that first shown in 
Figure \ref{fig:foracc}.

In Figure~\ref{fig:twoacc1} we have the code for a complete method, 
which therefore includes machine code for setting up the activation 
record on the stack --- the \texttt{save} instruction in the SPARC 
machine code on the right. 
We will return to this example again in Section \ref{sec:swapSemantics}

In Figure \ref{fig:chaitincode} we have the equivalent Java source 
code for the example from the Chaitin et. al. 1981 paper
\cite{Chaitin:Auslander:Chandra:Jocke:Hopkins:Marksteinjocl:1981}.
What makes this example interesting is that the separation into two 
if-then-else statements makes local register allocation ineffective.
To wit, local register allocation forces the store of \texttt{sum} 
at the end of both branches of the second if statement and the 
subsequent load of \texttt{sum} at the beginning of the ``return'' 
basic block.
\begin{figure}[tbp]
\begin{verbatim}
    int test(boolean mode, int U[], int V[]) {
        int SUM;
        if (mode) {
            A1 = U[0]; A2 = U[1];
        } else {
            B1 = V[0]; B2 = V[1];
        }
        if (mode) {
            SUM = A1 + A2;
        } else {
            SUM = B1 + B2;
        }
        return SUM;
    }
\end{verbatim}
\caption{Example from Chaitin (size = 2, SPARCstation 20)}
	\label{fig:chaitincode}
\end{figure}
\begin{figure}[tbp]
    \centering
    \includegraphics[scale=0.8]{chaitin.epsi}
    \caption{Bytecodes and SPARC Machine Code Generated from Chaitin 
    (size = 2)}
	\label{fig:chaitinsparc}
\end{figure}


In Figure \ref{fig:chaitinsparc}, we have the bytecodes and the SPARC 
machine code generated by a code generator for a portion of the source 
code of Figure \ref{fig:chaitincode}.
On the bottom left, we have the code generated by the kaffe code 
generator, which doesn't use our VR annotation.
On the bottom right, we have the code generated by our code 
generator, using our VR annotations.
The code shown is that for the very end of the then-branch of the 
second if statement and for the return statement.
Note that the code for line 614 of the ``Without VRs'' SPARC code is 
preceded along both of its predecessors, lines 5e0 and 610, with 
stores.
The stores in lines 5dc and 610 and the following load in line 614
are necessary because the kaffe code generator is only doing a local 
register allocation.
In the ``With VRs'' SPARC code, the predecessors to the 
basic block containing the return do not contain unnecessary stores, 
and the return block itself does not contain unnecessary loads.
\begin{figure}
    \begin{tabular}[t]{|l|l|l|l|l|l|}
    \hline
             & & \texttt{.class} & code     &           & \\
     problem & & file            & gen      & execution & verification \\
     size    & & size            & time     & time      & time\\
    \hline
    2 & w/o VRs & 1252 & 1ms & 3ms  & $<$1ms \\
      & w VRs   & 1645 & 2ms & 3ms & $<$1ms \\
    \hline
    10 & w/o VRs & 1800 & 6ms & 6ms & $<$1ms \\
       & w VRs   & 2354 & 5ms & 5ms & $<$1ms \\
    \hline
  \end{tabular}
  \caption{Results of VR annotation for chaitin (SPARCstation 20)}
  \label{fig:chaitin-results}

\end{figure}
\begin{figure}[tbp]
\end{figure}

\begin{figure}[tbp]
	\centering
	\begin{tabular}{|l|l|l|l|l|}
    \hline
         & \texttt{.class} & code     &  execution     &\\
         & file            & gen      &  + compilation & verification \\
         & size            & time     & time           & time \\
		\hline
		w/o VRs & 619 & 5ms & 132,405ms  & $<$1ms \\
		w VRs   & 855 & 5ms & 124,856ms  & $<$1ms \\
		\hline
	\end{tabular}
	\caption{Results for quicksort (SPARCstation 20)}
	\label{fig:quicksort-results}
\end{figure}
In Figure \ref{fig:chaitin-results} we see performance numbers based 
upon the example in Chaitin et al's 1981 work 
\cite{Chaitin:Auslander:Chandra:Jocke:Hopkins:Marksteinjocl:1981}.
The lines for size = 2 corresponds exactly to the source code in 
Figure \ref{fig:chaitincode}.
The lines for size = 10 correspond to the example as given in Chaitin 
et al\cite{Chaitin:Auslander:Chandra:Jocke:Hopkins:Marksteinjocl:1981}.
We see that for larger problem sizes, i.e. 10 vs. 2, that the VR 
annotation provides a speedup, while not increasing code generation 
time, or the part of code generation time spent on verification.
These numbers were obtained on a SPARCstation 20.
The lines marked ``w/o'' is for code generated by the standard kaffe 
code generator, which uses a local register allocator, run at code 
generation time.
The lines marked ``w'' is for code generated by our code generator, 
using the VR annotations.
Similarly, we see in Figure \ref{fig:quicksort-results}, similar 
results for an integer quicksort routine.

Overall, we see an 8\% speedup, without an increase in code 
generation or verification time.
We calculate the speedup using the normalized geometric mean equation 
from \cite{hepa:96}:
\[ \sqrt[n]{\prod_{i=1}^{n}\mathrm{Execution~time~ratio}_{i}} \]
Since the total execution time includes all methods, not just those 
annotated, this represents a very conservative estimate of the 
potential speedups.

\section{Other Annotations}
\label{sec-futwork}
As noted earlier, we have defined two annotations other than the VR 
annotation.
The first of these, the ``RIP'' annotation, is used for redundant 
load-store elimination.
The second of these, the ``swap'' annotation is used to indicate where 
register spills should be performed if needed.

\subsection{Semantics of ``RIP'' Annotation} 
The VR annotation removes most of the redundant loads and stores that 
would result from a naive JIT implementation for Java bytecodes.
However, VRs do not address redundant load/store elimination for heap 
resident values.
In situations dealing with class and instance variables, machine code for 
multiple loads (i.e. \texttt{getfield} and \texttt{getstatic} bytecodes) not 
reached by another definition after the first load, can be eliminated by 
marking all subsequent loads as ``remove if physical'' if the virtual 
register is being stored in a physical register.
A similar situation holds for stores.
The analysis must take note of 
possible changes to an object that may take place via function calls.
A conservative approach is to define any live range as ending when it 
reaches a function call.
An example will help to clarify.
Suppose we have the Java source code in Figure \ref{fig:RIPexample}.
\begin{figure}[tbp]
	\centering
	\begin{verbatim}
			AClass anObj;
			anObj.aField = 3;
			for (i = 0; i < a.length; i++) {
			    a[i] = a[i] + anObj.aField;
			}
		\end{verbatim}
	\caption{Example of Utility of RIP Annotation}
	\label{fig:RIPexample}
\end{figure}
The resulting annotated bytecode would have a \texttt{putfield} 
bytecode, for the assignment to \texttt{anObj.aField}.
As long as we arrange for the VR used by the 
\texttt{getfield} bytecode for \texttt{anObj.aField} inside 
the loop to be the same as the VR used by the \texttt{putfield} 
bytecode, we can mark the \texttt{getfield} bytecode as a RIP.

Due to the ``precise exception'' semantics of Java, it is anticipated 
that a few store instructions will not be marked ``remove if physical'' 
using the above guidelines.  
For example, suppose we have the following Java code as the entire body 
of a method: 
\begin{verbatim} 
int b = 0;
obj.a = 0;
try { obj.a = 3; b = 4; obj.a = 5; } 
finally { obj.f(b); } 
\end{verbatim} 
It might seem that the first \verb|putfield| bytecode in the \texttt{try} block
for \verb|obj.a| could be marked ``remove if physical''.  
However, assume that some asynchronous exception is thrown before 
the assignment of \verb|b|, in the \verb|try| clause.  
Since \texttt{obj.f()} may contain a \verb|getfield| bytecode,  
the \verb|putfield| may not be marked ``remove if physical''.

% other applicable work: exceptions --- Hennessey, Goodenough, Tiemann
It is this sort of issue that makes optimizing for Java and C++, 
languages with exceptions, different 
from optimizing for languages like C and FORTRAN, which do not.
There has been little published work in the area of optimizing for 
languages with exceptions.
One important work however, is Hennessy's\cite{Hennessy81.2} 1981 
paper.
Other important work in the area of implementing exceptions has been done by 
Tiemann\cite{Tiemann:1990:EHI} for C++,
by Chase\cite{Chase:JCLT-5-4-229}\cite{Chase:JCLT-6-1-20} for Ada, 
Modula2+, C++, Module-3 and Eiffel,
and by Goodenough\cite{Goodenough:cacm:1975} for general exception 
mechanisms.

Threading also must be examined carefully when 
generating ``remove if physical'' annotations.
Java has a shared-memory model for the sharing of information between 
threads of execution.
Access to this shared-memory area may or may not be synchronized, 
with synchronization obtained either through explicit 
\texttt{monitor\_enter} and \texttt{monitor\_exit} bytecodes, or 
through methods marked as synchronized.

>From a safety viewpoint, RIPs do not pose a threat.
It may appear that the elimination of a store can lead to a violation of 
the requirement for definite assignment before use, which is normally 
guaranteed by the bytecode verification process.
Since RIPs only apply to loads and stores of heap allocated values, the 
requirement is met by the class, array, and object creation 
semantics.
When a class or instance is created, any variables associated with it 
are assigned an appropriate default value.
\footnote{Assuming that an initializer is called after object 
creation.\cite{Freund:1998}}
For numeric types, this default value is zero.
More importantly, for reference types, the default value is \texttt{null}.
Therefore, so long as the bytecode and VR are type-compatible, 
``RIPs'' cannot be used to grab a rogue pointer and break the sanity of the JVM.

\subsection{Semantics of ``swap'' Annotation}\label{sec:swapSemantics}
When every variable is used with about the same frequency throughout a
program, 
deciding which are most important to keep in physical registers (or 
equivalently in our case, to assign to lower numbered virtual 
registers)
doesn't matter much.
Similarly, if there are enough physical registers, then the priority 
doesn't matter.
The reason is that no matter what the assignment, an equal number of 
operations will result in accesses to memory.
% However, if there are regions of the program where some values are 
% used much more than other values, than it becomes profitable to change 
% the physical register assignment for those values.
The point is that the non-uniform use of a variable through out a 
method opens up opportunities for that variable to be spilled and 
allow a more important value to have a chance at a physical register.

Using the swap annotation to guide changes in physical register 
assignment is crucial in achieving our goal of having 
machine-independent annotations.
There is a great disparity in the number of registers available in 
popular microprocessors.
Those in the RISC family, such as the SPARC, have a large number 
of registers, typically 32 or greater.
In the CISC family, there is a great deal of variance.
The embedded version of the Motorola 68000 has only 16 registers, and 
the most popular non-embedded processor, the Intel x86 family, has 
even fewer.
Given this disparity in the number of registers, swap annotations 
provide a means for improving the quality of the register assignment 
by allowing spill code to be generated more optimally, but in a 
machine-independent fashion.

To do this, we mark regions of the program with ``swaps'' between two
virtual registers.
This indicates that until otherwise indicated, the roles of the two 
registers are swapped.
This is accomplished in the code generator by changing the VR location 
table.
In a traditional global register allocator, if the number of 
registers is insufficient to contain all live ranges, 
then code is inserted to ``spill'' values from registers into memory 
and load values from memory into registers.
The swap annotation has the effect that spill code generation has in a 
traditional allocator. 
As covered in more detail below, the presence of a swap annotation may 
or may not result in spill code being generated by the code generator.
\begin{figure}[tbp]
\begin{tabular}{p{2.7in}cp{2.5in}}
\begin{verbatim}
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < 3; i++) {
        sum1 += i;
    }
    System.out.println(sum1);
    for (int i = 1; i < 4; i++) {
        sum2 += 1;
    }
    return sum2;
\end{verbatim}
\begin{tabular}{|lll|}
		\hline
 		0 & \texttt{iconst\_0} & 0\\
 		1 & \texttt{istore\_0} & 0\\
 		2 & \texttt{iconst\_0} & 3\\
 		3 & \texttt{istore\_1} & 3\\
 		4 & \texttt{iconst\_0} & 1\\
 		5 & \texttt{istore\_2} & 1\\
 		6 & \texttt{goto 16} & \\
		\hline
		\hline
 		9 & \texttt{iload\_0} & 0\\
 		10 & \texttt{iload\_2} & 1\\
 		11 & \texttt{iadd} & 0,1 $\rightarrow$ 0\\
 		12 & \texttt{istore\_0} & 0\\
 		13 & \texttt{iinc} & 1\\
		\hline
		\hline
 		16 & \texttt{iload\_2} & 1\\
 		17 & \texttt{iconst\_3} & 2\\
 		18 & \texttt{if\_icmplt 9} & 1,2\\
		\hline
		\hline
 		21 & \texttt{getstatic} & 4\\
 		24 & \texttt{iload\_0} & 0\\
 		25 & \texttt{invoke\_virtual} & 4,0\\
 		28 & \texttt{iconst\_1} & 1\\
 		29 & \texttt{istore\_3} & 1\\
 		30 & \texttt{goto 39} & \\
		\hline
		\hline
 		33 & \texttt{iinc} & 3,1\\
 		36 & \texttt{iinc} & 1,1\\
		\hline
		\hline
 		39 & \texttt{iload\_3} & 1\\
 		40 & \texttt{iconst\_4} & 2\\
 		41 & \texttt{if\_icmplt 33} & 1,2\\
		\hline
		\hline
 		44 & \texttt{iload\_1} & 3\\
 		45 & \texttt{ireturn} & 3\\
		\hline
\end{tabular}
&
\parbox[t]{0.25in}{
      \vspace{3in}
	  $\Rightarrow$
}
&
\begin{tabular}[t]{|ll|}
		\hline
 		\textit{\texttt{save}} & \textit{\texttt{\%sp, -200, \%sp}}  \\
	\NAC{gray}\hline\ENAC
 		\texttt{mov} & \texttt{\%g0, \%l0}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{mov} & \texttt{\%g0, \%l3}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{mov} & \texttt{\%g0, \%l1}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{b} & \texttt{xxx}  \\
 		\texttt{nop} & \\
		\hline
		\hline
	  & \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{add} & \texttt{\%l0, \%l1, \%l0}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{addcc} & \texttt{\%l1,1,\%l1}  \\
        \hline
		\hline
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{mov} &  \texttt{3, \%l2}  \\
	\NAC{gray}\hline\ENAC
 		\texttt{cmp} & \texttt{\%l1, \%l2}  \\
 		\texttt{bl} & \texttt{0x10aea8}  \\
 		\texttt{nop}  & \\
		\hline
		\hline
 		\texttt{sethi} & \texttt{\%hi(xxx), \%g4}  \\
 		\texttt{or} & \texttt{\%g4, 0x324, \%g4}  \\
 		\texttt{ld} & \texttt{[\%g4], \%l4}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{mov} & \texttt{\%l4, \%o0}  \\
 		\texttt{ld} & \texttt{[\%o0], \%g2}  \\
 		\texttt{ld} & \texttt{[\%g2 + 0x8c], \%g2}  \\
 		\texttt{mov} & \texttt{\%l0, \%o1}  \\
 		\texttt{call} & \texttt{\%g2}  \\
 		\texttt{nop} & \\
	\NAC{gray}\hline\ENAC
 		\texttt{mov} & \texttt{1, \%l1}  \\
	\NAC{gray}\hline\ENAC
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{b} & \texttt{xxx}  \\
 		\texttt{nop} & \\
		\hline
		\hline
 		\texttt{addcc} & \texttt{\%l1,1,\%l1}  \\
	\NAC{gray}\hline\ENAC
 		\texttt{addcc} & \texttt{\%l3,1,\%l3}  \\
        \hline
		\hline
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{mov} & \texttt{4, \%l2}  \\
	\NAC{gray}\hline\ENAC
		\texttt{cmp} & \texttt{\%l1, \%l2}  \\
 		\texttt{bl} & \texttt{xxx}  \\
 		\texttt{nop} & \\
		\hline
		\hline
	  & \\
	\NAC{gray}\hline\ENAC
 		\texttt{ret} & \\
 		\texttt{restore} & \texttt{\%g0, \%l3, \%o0}  \\
		\hline
\end{tabular}
\end{tabular}
\caption{Two for Loops with Different Accumulators \label{fig:twoacc1}}
\end{figure}


One can see a simple example of the utility of swaps in Figure 
\ref{fig:twoacc1}.
On the top left is the body of a Java function.
On the bottom left is the corresponding annotated Java bytecode.
The value corresponding to \texttt{sum1} is assigned to \vrzero, and the 
value for \texttt{sum2} is assigned to \vrthree.
Although \vrthree is not used in the first for loop and \vrzero isn't used in 
the second, we cannot assign either to the same virtual register 
since they are simultaneously live or interfere.
If we were generating code for a machine with two allocatable 
registers, and used only our VR annotation, then \vrthree would not be 
assigned to a physical register.
However, we can improve the performance of this code by annotating 
the \texttt{goto} bytecode at PC 30 by saying that the relative 
priority of \vrone and \vrthree are swapped when doing code generation.
This is done by modifying the VR location table discussed in 
Section \ref{sec:datastruc}.

The ``swap'' annotation consists of information indicating the PC 
where the swap is located, and which virtual registers are having 
their priorities swapped.
What the code generator does with the swap annotation is dependent 
upon the number of registers available to be allocated.
The ``swap'' annotation has the form $A\leftrightarrow B$, where 
$A$ and $B$ are the VR's that are to have their priorities swapped.  
In this annotation, we always have
$A<B$, so that $B$ is the VR whose priority is being increased.  
The rule is simple:  if $A$ is in a physical register and $B$ is not, 
then insert spill code and modify the VR location table accordingly;
otherwise do nothing --- 
that is, neither generate any machine code nor change the VR location table.

% The ``swap'' annotation consists of information indicating the PC 
% where the swap is located, and which virtual registers are having 
% their priorities swapped.
% What the code generator does with the swap annotation is dependent 
% upon the machine architecture, namely the number of registers 
% available to be allocated and is summarized in 
% Figure~\ref{fig:swapsemantics}.
% \begin{figure}[ht]
% \begin{tabular}{l|l|p{3.0in}}
% 	A & B & action  \\
% 	\hline
% 	in reg & in reg & none  \\
% 	in reg & in mem & store reg(A) and load mem(B), change loc(B) to be 
% 	reg(A), loc(A) to be mem(A)  \\
% 	in mem & in reg & none  \\
% 	in mem & in mem & none  \\
% \end{tabular}
% \caption{Swap of Virtual Registers A and B Versus Their Physical 
% Registers \label{fig:swapsemantics}}
% \end{figure}
% In the figure, ``in reg'' means that the corresponding 
% virtual register resides in a physical register, ``in mem'' 
% means that the corresponding virtual register resides in memory, 
% reg(A) means the physical register assigned to
% ${\mathsf{vr_{A}}}$, mem(A) means the memory location assigned to 
% ${\mathsf{vr_{A}}}$, and loc(A) means the current 
% physical location of a virtual register A.
% Also, B is the VR whose priority is being raised.
% The second line of the table in Figure~\ref{fig:swapsemantics} 
% specifies a change in these mappings, as well as a physical exchange 
% of values between a register and memory.
% Since ${\mathsf{vr_{B}}}$ is currently not in a register, but 
% ${\mathsf{vr_{A}}}$ 
% is, ${\mathsf{vr_{A}}}$ is stored to memory and ${\mathsf{vr_{B}}}$ is loaded 
% into the physical 
% register previously used for  ${\mathsf{vr_{A}}}$.

To devise an algorithm for determining where swaps should be 
inserted, we will use the intuition provided by the aggressive live 
range splitting algorithm of Briggs\cite{Briggs:phd:1992}.
There, live ranges are aggressively split before coloring by inserting 
spill code based upon the  single assignment (SSA) form of the 
method.
Extraneous copies are eliminated before coloring is attempted.
We will simplify the Brigg's algorithm by simply generating the SSA 
form and then inserting the appropriate swap annotations to correspond 
to the location and values of the $\phi$-functions of the SSA form.

It may prove necessary to have two kinds of swaps---before and after.
An after swap placed on a bytecode indicates that the swap should 
logically take place after the effect of the instruction has taken place.
For conditional branches, this will have the additional semantics that 
the swap takes place when the branch is not taken.
This is necessary to insure that there is always a place to put the 
swap --- which logically appears on a control-flow edge, not an instruction.

Swaps present no integrity problem, as long as the two values being 
swapped are type-compatible.

% \section{Concurrency Implications}\label{sec:concImp}
% \textit{ 
% Sam:  Here I intend to discuss several issues:
% \begin{description}
%    \item[VRs] clustering of non-local shared ((get|put)(field|static)).
%    VRs which refer to locals are not shared between threads, and therefore 
%    only those VRs which refer to heap values are effected by 
%    concurrency issues.
%    It is typically more efficient to cluster shared variables 
%    together, as long as there isn't so much concurrency that blocking 
%    becomes an issue.
%    \item[RIPs] similar
%    \item[related work] references to parallel compilation.
%    I am developing a reading list and will try to discuss some of the 
%    issues.
%    Notably, Java's concurrency model is based on monitors, while most 
%    of the work done in static analysis I've found so far has been done 
%    on Ada, which uses a rendezvous model.
% \end{description}
% }
% 
% \section{Size Considerations}
% \textit{As we saw in Figure \ref{fig:chaitin-results} and 
% Figure \ref{fig:quicksort-results}, the VR annotation adds approximately 30\% 
% to the the size of the \texttt{.class} files.
% Here we will give a brief analysis of the potential impact the swap 
% and RIP annotations will have on the size of the \texttt{.class} files.
% }

\section{Related Work}
Many current implementations of the JVM use JIT technology.
We discuss a few of these below.

% kaffe: interpreter or compiler, not both
The open source virtual machine which we use to implement our work is 
kaffe, from Transvirtual\cite{kaffeURL}.
This VM can be deployed either as an all-interpreted system or an 
all-JIT system.
Their JIT system does a very weak local register allocation, and no 
other optimizations.

% other JVMs with JITs: java hotspot, IBM tokyo, AJIT
Sun's ``Java HotSpot$^{TM}$ performance engine''\cite{HotSpotURL} 
employs an optimizing compiler on code that has been determined to be
performance critical.
The optimizing compiler in their VM includes implementations of dead-code 
elimination, loop invariant hoisting, common subexpression elimination, 
constant propagation and a graph coloring global register allocator.

Another JVM developed in a commercial environment is one at IBM 
Tokyo Research Laboratory\cite{Ishizaki1999}.
It applies a similar set of optimizations as HotSpot does in its JIT.
However, it does not use a global register allocator, but use a 
region-based local one instead.  They claim ``Since the JIT 
compiler requires fast compilation, expensive register allocation 
algorithms, such as graph coloring, cannot be used.''
We prove this assertion is false by doing the graph coloring when 
making the \texttt{.class} file, not when executing it.

Most closely related to our work is the AJIT system\cite{Hummel1997}
\cite{Azevedo1999}.
They also add annotations to the \texttt{.class} file, and then use an 
``annotation-aware'' JVM to generate machine code.
They break up some of the more complicated Java bytecodes into 
suboperations  (e.g. \texttt{iaload}, load an element from an array of 
integers) and produce annotations specific to the suboperations.
By in effect transforming their bytecodes into a sort of microcode, it 
seems likely that the verification process is made more difficult.
Furthermore, they do not have the swap annotation, which we 
argued is important for increasing the portability of any annotated 
code.

\section{Conclusions}
We have defined and implemented a register allocation annotation for Java 
\texttt{.class} files which is both machine-independent and safe.
In addition, we have defined two other annotations which are 
machine-independent and safe, ``remove if physical'' and swaps which 
should also prove to be performance enhancing.

\section*{Acknowledgments}
We would like to thank Mike Lake for coining the phrase and clarifying the 
concept of ``superlinear analysis and linear exploitation.''

\bibliography{bound,unbound}
\end{document}
