% $Id: impl.tex,v 1.18 1997/07/30 19:19:17 cierniak Exp $

\section{IMPLEMENTATION}
\label{sec:impl}

Performing high-level optimizations in a Java JIT compiler is more
difficult than in a traditional compiler.  The main reasons are:
\begin{itemize}
\item Much of the information about program structure is lost in the
  process of translation from Java source to bytecodes.  This
  information (e.g., multidimensional array references) must be
  recovered before any optimizations can be attempted.  In our
  particular implementation that recovery is even more difficult
  since, for performance reasons, we have decided to directly use the
  Kaffe IR which is even lower than bytecodes.
\item Since the compiler is being invoked every time the program is
  being run, the speed of compilation is much more critical and many
  traditional analysis techniques must be replaced with faster
  alternatives.  Such new algorithms are proposed in this section.
\item Typically, to improve response time, a JIT compiler compiles
  bytecodes on demand one class at a time or one method at a time
  (Kaffe uses the latter approach).  Therefore, optimizations which
  require global information are not possible (or at least cannot be
  trivially implemented).
\end{itemize}

Since our compiler is embedded in Kaffe we have decided to use Kaffe
IR directly.  A brief overview of the Kaffe architecture is presented
in Section~\ref{sec:impl:kaffe}.  Briki performs the optimizations in
the following steps:
\begin{enumerate}
\item Build a control flow graph (CFG) for the method.
\item Find dominators.
\item Identify loops.
\item Compute def-use information.
\item Compute {\em constant values}.
\item Find {\em loop-defined variables}.
\item Identify multidimensional arrays which can be legally remapped.
\item Find optimal mappings.
\item Remap arrays.
\end{enumerate}
The rest of this section will discuss our implementation decisions for
the above algorithm.


\subsection{Kaffe architecture}
\label{sec:impl:kaffe}

Kaffe~\cite{Kaffe-v0.8.3-1997} is a free JIT implementation of the
Java Virtual Machine~\footnote{Kaffe can also run as an interpreter,
  but we use it only in its JIT mode.}.  Kaffe runs on several
architectures: i386, Sparc, Alpha, M68K.  This is possible because
Kaffe is designed to have two parts: the machine-independent front-end
which translates bytecodes into a low-level intermediate
representation, {\em Kaffe IR}, and a machine-dependent back-end which
translates Kaffe IR into the required machine language.

Kaffe IR is designed to closely resemble a modern microprocessor
architecture so that writing a new back-end is relatively simple.
Kaffe IR defines a virtual architecture with a very large number of
pseudoregisters (every local variable and every stack location is
mapped to a different pseudoregister) and it contains instructions to
move data between registers\footnote{We will use the terms {\em
    register}, {\em pseudoregister\/} and {\em variable\/}
  interchangeably.} or between registers and memory, perform
arithmetic and logical operations on values in registers, branch
conditionally to a label, call a subroutine, etc.

Every back-end must provide a set of core virtual machine
instructions.  If a virtual instruction cannot be mapped directly to
the target instruction set, it is implemented in software.  A back-end
may also implement a subset of optional instructions which will be
used by Kaffe to implement some bytecodes more efficiently.

A Kaffe IR (virtual) instruction is represented internally as a {\tt
  sequence} structure with a pointer to the back-end function which
takes as a parameter a pointer to the {\tt sequence} and translates it
into the target instruction set.  The {\tt sequence} structure also
contains all operands (pseudoregisters, constants or labels) to that
virtual instruction.

The translation process consists of two basic steps.  First the
bytecodes are translated by the front-end into the Kaffe IR, then the
list of the {\tt sequence} structures is traversed and every back-end
function is called generating native code.

The developers of Kaffe are very good about releasing updates to
Kaffe.  In the 14 months since the Kaffe project started, there have
been 21 releases of Kaffe (for the experiments described in this paper
we have used version 0.8.3 released on March 21, 1997), or---on
average---one every 3 weeks.  This caused a technical problem for us,
since the most convenient and efficient way of implementing our
optimizations would involve modifying internal data structures of
Kaffe, but to keep in sync with the updates of Kaffe we would have to
merge our software with the new Kaffe every three weeks thus
stretching our resources.  To avoid this problem, we have decided to
keep our optimizer as separate from Kaffe as possible.  While this
made our project manageable, it resulted in extra overheads both in
memory and processing time.  In that light we are glad that our
optimizations are very fast (see Section~\ref{sec:exp} for timings),
because there is room for additional improvement which can be achieved
by a tighter integration with Kaffe.  Main sources of those,
unnecessary, overheads are
\begin{itemize}
\item The need to allocate a shadow data structure for every {\tt
    sequence} structure to keep additional information needed during
  optimization.  Splitting the information into two structures results
  in lost spatial locality and unnecessary indirection.
\item The need to recognize individual instructions in Kaffe IR.
  Since the only way to tell what instruction is implemented by a
  given {\tt sequence} structure is to compare the back-end function
  pointer against the addresses of back-end functions extra time is
  spent where a single instruction would suffice if we changed Kaffe
  IR to suit our needs.
\end{itemize}
In the current implementation, we let Kaffe front-end generate its IR
(the {\tt sequence} structures), then we invoke our optimizer which
analyzes and transforms Kaffe IR, and after the optimization is done,
we return to Kaffe and the back-end translates the optimized Kaffe IR
form into native code.  That design means that the only change to
Kaffe source code needed to plug in our optimizer is the insertion of
a single function call just before the back-end invocation.
  


\subsection{Control Flow Graph}
\label{sec:impl:cfg}

We build the CFG for the Kaffe IR form of a method by searching for
the {\tt startBlock} and {\tt endBlock} instructions.  Than we use
standard algorithms to find dominators and identify
loops~\cite{Aho-compilers-1986}.  Those algorithms take about 10\% of
the total optimization cost (compare Figure~\ref{fig:exp:break:down}).



\subsection{Computing def-use information}
\label{sec:impl:def:use}

This step computes def-use information for every basic block.  The
operation is very simple and requires visiting every Kaffe IR
instruction exactly once to perform a sequence of simple bit
operations.  In our implementation this the most expensive part of the
array transformation optimization (compare
Figure~\ref{fig:exp:break:down}).

The long time to perform this optimization is an artifact of our
software engineering decision explained in
Section~\ref{sec:impl:kaffe}.  For relative independence of
Briki from changes in Kaffe we pay the price of
\begin{itemize}
\item The need for keeping a shadow structure for every Kaffe IR
  instruction (which results in worse cache utilization and
  unnecessary indirection in accessing the structures).
\item Very slow code to determine which registers are being modified
  in a given instruction.
\end{itemize}
We think that this time can be shortened when Kaffe becomes more
stable and a tighter integration of Kaffe and Briki is easier.


\subsection{Computing constant values}
\label{sec:impl:const:val}

For every array reference we have to be able to identify which array
allocation statement is associated with this reference.  There are
many known algorithms for solving this problem of {\em reaching
  definitions}.  Existing algorithms are not well suited for JIT
compilation since they use large amounts of memory to store the reaching
definitions information (e.g., in the form of bitmaps for every
instruction or {\em ud-chains\/}~\cite{Aho-compilers-1986}).

For our purposes we solve a simpler problem which can be computed
faster and represented in a more compact way.  The representation
contains one bit vector per basic block.  The bit vector represents
{\em constant values\/} with the following definition.
A variable $v$ is constant-value for a basic block $B$ if and only if
\begin{enumerate}
\item $v$ is defined in $B$.
\item $v$ is not defined in any other basic block.
\item $v$ is used only in basic blocks {\em dominated\/} by $B$.
\item $v$ is not used before its definition in $B$.
\end{enumerate}

We only analyze and possibly transform arrays which are stored in
constant-value variables.  Elements of the array may of course be
modified many times, but we make sure that the variable containing the
pointer to the array handle is a constant-value variable.  Note that
the fact that an array is stored in constant-value variable does not
suffice to determine if an array transformation is legal.  For example
a shape of a 2-D array could be changed by changing the length of one
of the rows, or a row could be passed as an argument or returned as a
result.  We conservatively assume that only arrays which have been
allocated as rectangular arrays (using the construct corresponding to
the {\tt multianewarray} bytecode) and whose all uses are references
using all dimensions can be remapped.

This condition is sufficient because to change the shape of an array
or to use an array in a way that depends on the mapping, a reference
to one of the subarrays would have to be used.  E.g., for an 3-D array
\texttt{B}, if all references \emph{use all dimensions}, i.e., are of
the form
\texttt{B[}\emph{expr1}\texttt{][}\emph{expr2}\texttt{][}\emph{expr3}\texttt{]},
the mapping of the array cannot change the semantics of the optimized
application.  However, expressions of one of the following three
forms,
\texttt{B[}\emph{expr1}\texttt{][}\emph{expr2}\texttt{]},
\texttt{B[}\emph{expr1}\texttt{]}, or
\texttt{B} could potentially depend on the mapping and arrays with
expression that \emph{do not use all dimensions} are not transformed
by Briki.


We can find constant-value arrays efficiently.  For every array
allocation, we note the variable, $v$, the array is stored in, and the
basic block $B$ that contains this allocation and we
traverse all other basic blocks and make sure that
\begin{itemize}
\item $v$ is not defined, and
\item $v$ is used only in basic blocks which are dominated by $B$.
\end{itemize}
The above operation can be performed as a single scan of all basic
blocks using the def-use information computed for every basic block in
Section~\ref{sec:impl:def:use}.  During the same scan we verify that
all uses of $v$ access the array using all its dimensions.

Note that for block $B$ we have to traverse all its instructions
rather than just use the summary def-use information computed for $B$
in Section~\ref{sec:impl:def:use}.



\subsection{Identifying loop-defined variables}
\label{sec:impl:loop:def}

To analyze precisely locality properties of array references contained
in loops, we would have to determine which variables are loop
induction variables and what is their step for the corresponding
loops.  Again, this operation is expensive and we have decided to
approximate the notion of an induction variable with a {\em
  loop-defined variable}.  For a loop $L$, a loop-defined variable is
any variable which is defined in loop $L$.  This simplification is
justified by the following observation for variables used in array
subscripts in scientific programs: if such a variable is assigned a
new value in a loop then the value of that variable will usually be
different in every loop iteration and the variable will usually be an
induction variable with a unitary step.

Loop-defined variables can be identified in a single scan of all basic
blocks.  For every basic block the set of variables defined in this
block is added to the set of loop-defined variables for all (if any)
enclosing loops.  Enclosing loops can be accessed quickly because
every basic block has a pointer to the innermost loop containing this
block and every loop has a pointer an enclosing loop.



\subsection{Recovering multidimensional array structure}
\label{sec:impl:array:ref}

Array transformations can be only applied to multidimensional arrays.
Multidimensional array references are present in the source program,
but the translation to bytecodes lowers them into a sequence of
one-dimensional references.  Those can be converted back into
multidimensional references with the techniques from our previous
work~\cite{Cierniak-offline-CPE-1997}.  

The dimension recovery is more difficult in the JIT version of Briki.
While in principle we could operate on bytecodes, for reasons
explained in Section~\ref{sec:impl:kaffe}, we perform our
optimizations on Kaffe IR which is even lower than bytecodes.  In
Kaffe IR, an array reference is converted to a sequence of low-level
instructions like memory loads, register moves, shifts and additions.
Briki analyzes each such sequence and represents it as a high-level
multidimensional array reference.  This high-level structure is not
stored anywhere---it is recomputed every time it is needed.  This
approach results in a fast implementation.  For cholesky, the time to
ensure legality of a transformation, finding the optimal mapping
(Section~\ref{sec:impl:opt:mappings}) and performing the
transformation (Section~\ref{sec:impl:remap:arrays}) constitutes only
about 20\% of the time spent in Briki.



\subsection{Finding optimal mappings}
\label{sec:impl:opt:mappings}

Since multidimensional arrays in the Kaffe VM are not represented as
contiguous portions of memory, but rather as arrays of 1-D arrays, we
use a much restricted set of array transformations as compared to the
one from~\cite{Cierniak-PLDI-1995}.  

For every array reference we determine which subscript contains
loop-defined variables of the innermost loop (or of the next enclosing
loop, if the loop-defined variables of the innermost loop are not
present in any subscript).

The best mapping for this array would make the dimension which
corresponds to this subscript the right-most dimension to increase
spatial locality.  

In any real program it is very likely that there would be conflicts
between desired mappings for different array references.  We resolve
the conflicts by assigning a {\em priority\/} to every array
reference.  The priority is based on the loop nesting---the higher the
nesting the higher priority.  This policy is adopted since {\em
  usually\/} the statements with higher nesting are executed more
times than statements with lower nesting.  This is of course not
guaranteed and in general it is not possible to predict at
compile-time how many times a given statement will be executed.

In the case of a conflict we choose the array mapping preferred by the
greatest number of references with the highest priority.  For
instance, if four is the highest priority and three references with
priority four require dimension 0 in the right-most position and one
reference with the same priority requires dimension 1 in the right-most
position then dimension 0 is permuted into the right-most position.


\subsection{Remapping arrays}
\label{sec:impl:remap:arrays}


Once we know which dimension should be permuted to the rightmost
position, remapping is very simple.  In this process we use the
dataflow information calculated in the step described in
Section~\ref{sec:impl:def:use}.

