% $Id: intro.tex,v 1.10 1997/07/30 17:35:43 cierniak Exp $

\section{INTRODUCTION}
\label{sec:intro}


Compiling scientific applications requires sophisticated compiler
optimizations.  Those optimizations are commonly available in
commercial compilers for languages traditionally used for high
performance computing.  Those languages (the most successful ones are
Fortran and, to a smaller extend, C++) are compiled off-line into a
stand-alone binary.  This approach is different from the dominant
compilation model for Java in which the source program is translated
into machine-independent {\tt class} files which are then interpreted
or dynamically (just-in-time) compiled into the target machine
language.

Many of the existing high-performance optimizations cannot be easily
adapted to just-in-time (JIT) compilation.  The reasons include:
\begin{itemize}
\item Sophisticated optimization techniques consume a lot of hardware
  resources: CPU time and memory.
\item Often, a global view of the program is necessary ({\em
    whole-program
    optimization\/}~\cite{Chambers-TR-Whole-Program-1996,
    Cierniak-PACT-1997}).
\end{itemize}

In this paper we address the issue of performing optimizations which
are as good or almost as good as traditional optimizations while
running much faster and using less memory.  For our study we use an
optimizations technique called {\em data transformations}.  In
previous work we have shown that data transformations can be very
effective in compiling Fortran or C
programs~\cite{Cierniak-PLDI-1995}.  Recently we have adapted the
technique for Java bytecodes~\cite{Cierniak-offline-CPE-1997,
  Cierniak-COMPCON-1997}.  However, our previous experiments with
optimizing Java bytecodes have been performed with an off-line
compiler and the compiler algorithms were not as fast as a competitive
JIT compiler is expected to be.  To perform data transformations we
need more program structure than is directly available in the
bytecodes.  Our previous implementation was recovering full high-level
structure of the original Java program before applying any
optimizations.  This high-level view of the input bytecodes was
represented with an intermediate representation called {\em JavaIR}.
JavaIR is very high-level and so high-performance optimizations, like
data remapping, can be performed very efficiently.  Unfortunately, our
experience has shown that recovering full structure from a {\tt class}
file is very expensive.  In our implementation, the time needed to
convert bytecodes to JavaIR is an order of magnitude longer than the
time to perform the optimizations.  Since most the high-level
structure is not needed to perform data transformation, we have
decided to use a different approach in our JIT optimizer.

This paper shows how to perform the same optimizations as described
in~\cite{Cierniak-offline-CPE-1997, Cierniak-COMPCON-1997} while
recovering only as much structure as needed and using faster (although
not necessarily as accurate) analysis techniques than those
traditionally used in off-line compilers~\cite{Aho-compilers-1986,
  Wolfe-compilers-1996}.  We have implemented all the techniques
described in this paper in our experimental compiler {\em Briki}.
Briki uses Kaffe~\cite{Kaffe-v0.8.3-1997} as the JIT compiler and
implements the optimizations in a relatively machine-independent
manner so that it can run Java programs on multiple architectures
(such as i386 or sparc).

