% $Id: intro.tex,v 1.6 1997/02/01 19:35:31 cierniak Exp $


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

The definition of the Java programming language includes both the
definition of the programming language
itself~\cite{Java-Language-Specification-1996} and the definition of
the virtual machine~\cite{Java-VM-1996} which can run compiled Java
applications represented in the form of {\em
  bytecodes\/}~\cite{Java-VM-1996}.  An application in the bytecode
form can run on any computer with an implementation of the Java
virtual machine.  A bytecode form of an application is distributed in
{\tt class} files which in addition to the bytecodes contain
information required for linking and verification.

On most computers, efficient execution of Java bytecodes requires
compilation to native machine instructions.  The compilation can be
performed off-line or on-demand, while the application is being
loaded.  The latter option --- Just-In-Time (JIT) --- is used in the
majority of current implementations.



As the technology matures, advanced compiler optimizations are being
proposed to speed up execution of Java applications (unless explicitly
stated otherwise, by a ``Java application'' we mean either a
stand-alone application or an applet).  Many techniques used to
optimize programs written in other programming languages can be
successfully applied to Java programs, other techniques are unique to
Java.  

This paper concentrates on optimizations which rely on the knowledge
of the target architecture, so they cannot be performed by the
compiler which generates the {\tt class} file, since the target
machine is not known at that time.  At the same time, the optimization
techniques we consider cannot be easily performed on bytecodes
directly and require the recovery of high-level representation of the
code which is being optimized.


Briki is a compiler developed to research the issues of potential
benefits of high-level optimizations for Java programs.  Briki reads
in a Java program distributed in the bytecode form, converts it into
JavaIR (an intermediate representation used to represent Java programs
in our compiler), performs the optimizations, and writes out the
optimized code.  We are primarily interested in the configuration of
Briki which performs JIT compilation, i.e., a compiler which is
integrated with the virtual machine and generates machine code for
immediate execution.

%However, we do not want to ignore other ways of
%compiling Java and so we have designed Briki so that multiple
%front-ends and multiple back-ends can be used with the same optimizer.
%We expect that in the future a front-end which converts Java source
%programs directly to JavaIR may be developed.  It may be also
%beneficial to write a back-end which writes the optimized code in some
%portable form, say, the C programming language.

The current implementation of Briki, which was used in the experiments
presented in this paper, reads in a {\tt class} file and writes the
optimized code to another file in the form of Java source.  We chose
off-line compilation and Java source as the output form for the ease
of debugging and better understanding of the quality of the recovered
code.  A JIT implementation of Briki which will integrate our compiler
with kaffe~\cite{kaffe-v0.5.5}, a publicly available JIT Java system,
is under way.

Section~\ref{sec:org} presents the organization of Briki including a
brief discussion of {\em JavaIR}, our intermediate representation for
Java programs.  More details on JavaIR can be found
in~\cite{Briki-TR621}.  Section~\ref{sec:recovery} discusses our
approach to high-level structure recovery.  Our optimization
techniques are described in Section~\ref{sec:opt}.  We include two
appendices to make our presentation clearer.
Appendix~\ref{sec:example:recovery} shows the recovery process on a
sample, short method.  Appendix~\ref{sec:example:opt} presents an
example optimization process for one of our optimization techniques
for a much simplified benchmark.  Experimental results are given
in Section~\ref{sec:exp}.

