\documentclass{acmconf}
\usepackage{url}
\usepackage{epic}
\usepackage{eepic}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{moreverb}
\newcommand{\ifxypic}[1]{#1}
\ifxypic{
\usepackage{xypic}
}
\newcommand{\trademark}{$^{\mbox{\footnotesize \sc tm}}$}
\newcommand{\code}[1]{{\tt #1}}
\newcommand{\filename}[1]{{\tt #1}}
\newcommand{\reminder}[1]{{\em NB: #1}}

\title{A Java\trademark\footnote{Java is a registered trademark of Sun Microsystems.} Bytecode Optimizer Using Side-effect Analysis}
\author{Lars R. Clausen\\\texttt{elascurn@daimi.aau.dk}}
\affiliation{Department of Computer Science\\Aarhus University}

\begin{document}
\maketitle 


\abstract{This paper describes Cream, an optimizer for Java bytecode using
side-effect analysis to improve the optimizations.  Dead code elimination and
loop invariant removal is implemented and tested, as well as several variations
of the side-effect analysis.  The optimizer is tested on real-world
applications such as itself and JavaSoft's Java compiler.  Results show that
the optimizations benefit a lot from the side-effect analysis.  The best
side-effect analysis gives five to ten times as many optimizations as without
an analysis, and, in one case, makes a sped increase of 25 \% possible.}

\section{Introduction}
Java, being a relatively young language, doesn't yet have as sophisticated
optimizing compilers as other, more mature languages like C and Fortran.  When
designing the optimizers needed to improve Java's speed towards a more
acceptable level, one must carefully consider the special traits of the
language.  In contrast with C programs, Java programs have many small method
invocations, many structure references, extensive exception handling and
dynamically-loaded classes.  A successful optimizer must deal correctly and
effectively with such programs.

Normally, optimization of Java code is done in two places: (1) In the compiler,
and (2) in the runtime system.  The compiler from Java source to bytecode can
perform some large-scale optimizations, but access to the source code is a
necessity for doing this.  The runtime system, whether it does JIT compilation
or interpreting, is limited by having little time to spare for optimizing, and
thus can only do some local optimizations.

A third possibility is to optimize on the Java bytecode, as shown in Figure
\ref{figure:optimizer}.  This has several advantages:

\begin{itemize}
\item Access to source code is not required.  In fact, it will be possible to
optimize programs written in other languages, if they can be compiled to
bytecode.
\item Machine independency is maintained.
\item Inter-procedural analysis is possible for the user, so library
variations are recognised.  The user will be able to optimize with respect to
his own libraries and still get valid results.
\end{itemize}

In any object-oriented language, massive use is made of object fields.  Since
objects generally live through several method invocations, it is difficult to
know much about their state locally.  On the other hand, inter-procedural
analysis is complicated by the existence of virtual methods and interfaces,
which are very common in Java.  Good methods for optimizing field accesses
interprocedurally are essential when working on object-oriented programs.

To address this problem, we have implemented a simple side-effect analysis.  It
does inter-procedural analysis where possible, determining if and how
side-effects are made.  Using this information, many more optimizations of
field accesses and method invocation become possible.

In this paper, we describe a working implementation of Cream, an optimizer for
Java bytecode, which performs dead-code elimination and loop-invariant removal
using standard optimization techniques from \cite{AhoSethiUllman85}, as well as
the side-effect analysis.  It handles native code, exceptions and monitors, and optimizes large class collections successfully.

In Section \ref{section:analyzing} we describe how we analyze Java bytecode.
Section \ref{section:purity} describes the side-effect analysis and its
effectiveness in our implementation, and Section \ref{section:usingpurity}
shows how it is used in Cream, and the resulting optimizations.  Section
\ref{section:relatedwork} briefly describes related work, and Section
\ref{section:conclusions} gives conclusions and future work.

\section{Analyzing Java bytecode}
\label{section:analyzing}

Java bytecode \cite{JavaVMSpec} is a simple, stack-based language with about
200 instructions, about 50 of which are special cases of other instructions.
It is strongly typed, and contains information about the class structure.
Each method has a fixed maximum stack depth, and the stack depth can easily
be calculated at any point in the program.  This makes it possible to regard
stack variables as short-lived local variables and use well-known optimization
techniques on them.

As illustrated in Figure \ref{figure:optimizer}, Cream consists of 9 phases.
The first two phases are interprocedural, while the remaining phases are
performed for one method at a time.  A brief description of each phase is given
below.

\begin{figure*}
\begin{center}
\input{optimize.eepic}
\end{center}
\caption{Lifetime of a Java program}
\label{figure:optimizer}
\end{figure*}

\paragraph{Class graph construction:}
The class graph is made in order to make it possible to analyze virtual and
interface methods.  It contains all the classes that may be used by the
program, as well as their superclasses.  Those classes that may have instances
allocated during program execution are marked as such.

\paragraph{Side-effect analysis:}
Before starting the normal analysis, side-effect analysis for virtual methods
(see Section \ref{section:virtualpurity}) is done, starting at a given
\code{main()} method.  Methods that are not reached by this will be analyzed
when needed.

\paragraph{Control-flow graph construction:}
The instructions of each method are divided into blocks at places where the
control flow may change, such as after \code{if} or \code{goto}, or before
instructions that are the target of such.  The possible flow of control is then
represented as edges between these blocks.  If an exception handler is present,
instructions that may throw an exception\footnote{It is necessary for good
optimizations to be able to optimize on field accesses.  For this reason, we
use the option where null pointer and class cast exceptions do not cause
branches.  Programming to catch such exceptions isn't very nice, anyway.} also end a
block, and cause an edge to be added from the block to the exception handler.
Exception and monitors are also considered when doing the actual optimization.

During this stage we also do the one abstraction that has proven necessary:
The control flow is separated from the order of the instructions, making it
much easier to move instructions around.  Once this abstraction was in use, the
problems encountered changed to be of a nature that any control-flow graph
would give.

\paragraph{Stack depth inference:}
In order to reason about stack variables, we have to know how high the stack is
at any given point.  This is found by a simple traversal of the control-flow
graph.  After this, stack variables are identified by their offset from the
bottom of the stack, not by their position relative to the stack pointer.

\paragraph{Use-def analysis:}
With the control-flow graph and stack depths ready, we build use-def chains for
local variables and stack variables.  This uses a standard analysis with kill-
and gen-sets.  The only difference is that stack variables are always
considered killed when they are used.

\paragraph{Cycle detection and dominance graph construction:}
Before doing loop invariant elimination, a cycle detector as in
\cite{AhoSethiUllman85} is run, and a dominance graph is built.  

\paragraph{Dead code marking:}
The dead code marker considers all impure instructions, return instructions,
and instructions that may alter the control flow, to be live.  Those that are
not live or used to construct anything live will be eliminated in the
transformation step.

\paragraph{Loop-invariant detection:}
Loop-invariant detection detects, fairly conservatively, instructions that are
invariant during a loop.  This may include field accesses and invocations of
method without side effects, if the loop itself is found to be side-effect
free.

\paragraph{Code transformations:}
Finally, the possible transformations are performed.  Care must be taken to
keep the stack consistent --- if the result of a method invocation is no longer
used, because the use turned out to be dead code, the result must still be
popped off the stack.  Exceptions and monitors present special problems for
moving code outside loops.  Code that may reasonably throw exceptions should
not be moved outside an area that has a handler for the exceptions they may
throw.  Similarly, in monitored areas, code that might involve the monitored
objects should not be moved away.  We take a conservative approach by simply
disallowing movement of any code that may throw exceptions outside areas with
an exception handler, and object field accesses or updates may not be moved
outside a monitored area.

\newcommand{\pure}{\textsf{pure}}
\newcommand{\semipure}{\textsf{read-only}}
\newcommand{\impure}{\textsf{write-only}}
\newcommand{\both}{\textsf{read/write}}
\newcommand{\Pure}{\textsf{Pure}}
\newcommand{\Semipure}{\textsf{Read-only}}
\newcommand{\Impure}{\textsf{Write-only}}
\newcommand{\Both}{\textsf{Read/write}}

\section{Side-effect analysis}
\label{section:purity}

The side-effect analysis is an inter-procedural analysis to determine when
computations may alter or inspect of object fields or array elements.  We have
called it `purity analysis' after the usage in functional languages, where
`purely' functional languages are those without the possibility of
side-effects.  

An instruction or collection of instructions is said to have a purity for all
object fields and the five basic types of array elements\footnote{At bytecode
level, determining the exact type of the elements of an array involves a great
deal of analysis.}.  Purity can be inferred for methods, loops and
instructions.  The inferred purity of an instruction for an object field or
array element can be one of four:

\begin{description}
\item{\pure:} An instruction is \pure\ for a field or element if it neither
alters nor inspects the field or elements.  These include allocations and array
length.
\item{\semipure:} An instruction is \semipure\ for a field or element if it
reads that field or element, but does not write to it.
\item{\impure:} An instruction is \impure\ for a field or element if it changes
the field or element.
\item{\both:} These instructions both alter and inspect
the object field or array element.  The only single instruction that can do
this is a method invocation.
\end{description}

\begin{figure}[htbp]
$$\diagram
                      & \Text{\both} = \top & \\
\Text{\semipure}\urto &      & \Text{\impure}\ulto\\
                      & \Text{\pure} = \top\urto\ulto &\\
\enddiagram$$
\caption{Partial ordering of purity information}
\label{figure:partialordering}
\end{figure}

These three types of purity form a partial ordering as shown in
Figure~\ref{figure:partialordering}. With this, finding the purity for a field
or an element of blocks, loops or methods becomes a matter of finding the least
upper bound of the corresponding purities of the instructions involved.  Figure
\ref{figure:purities} shows examples of purities of methods.  This ordering can
be extended to allow for more complex information, as demonstrated in section
\ref{section:advancedpurity}.

\begin{figure}[htbp]
%\begin{center}
%\begin{minipage}{10cm}
\begin{verbatim}
class Purities {
  int a;
  int b[];
  int pure1(int x) { return(x+2); }
  int pure2(int x) { return(x+b.length); }
  int readonly1(int x) { return(x+a); }
  int readonly2(int x) { return(x+b[0]); }
  void writeonly1(int x) { a = x; }
  void writeonly2(int x) { b[x] = 0; }
}
\end{verbatim}
%\end{minipage}
%\end{center}
\caption{Examples of \pure, \semipure, and \impure\ methods}
\label{figure:purities}
\end{figure}


\subsection{Simple purity}
\label{section:simplepurity}

The purity of most instructions can immediately be found.  The only directly
\impure\ instructions are array- and field-store, while array- and field-loads
are \semipure.  

The local purity of a method or a loop is found for each field or array element
by taking the least upper bound of the purities of the instructions involved.

To find the purity of a method invocation, it is necessary to recursively find
the purity of that method.  This would be easy, where it not for
recursive methods.  Because of them, more thought is needed.  Figure
\ref{figure:callgraph} shows such a recursive method.  Since \code{qux()} is
\impure, \code{bar()} will also be \impure, but \code{baz()} may already have
been visited and will wrongly be considered non-\impure.  

\ifxypic{
\begin{figure}[htbp]
$$\diagram
                   &\Text{\code{main()}}\dlto\drto&\\
\Text{\code{foo()}}&                              &\Text{\code{bar()}}\drto\dlto\\
                   &\text{\code{baz()}}\xto `u[-1,1] [-1,1]&
 &\Text{\code{qux()}\\(\impure)}\xto
`u[-1,-1] [-1,-1]
\enddiagram$$
\caption{Call graph with recursion}
\label{figure:callgraph}
\end{figure}
}

The fastest way to find the real purity of the recursive methods is by finding
the strongly connected components of the call graph \cite{CooperKennedy88} and
treat them as one virtual node.  Methods included in the same component will
have the same purity, as they may at some time call any of the others.
Finding the strongly-connected components has a well-known linear-time solution
\cite{Tarjan81}.  By using these virtual nodes, we turn the call
graph into a directed acyclic graph, where a simple depth-first traversal can
be used to find the purities.

The example in Figure \ref{figure:callgraph} will then have \code{bar()},
\code{baz()} and \code{qux()} as one virtual node in the callgraph, called from
\code{main()}.  All the methods involved in that node will be \impure, since
one of them is.  

Once the strongly-connected components are found and replaced by virtual nodes,
a depth-first traversal will take only $O(ek)$ time, where $e$ is the number of
edges in the reduced call graph, and $k$ is the time needed to find the least
upper bound of two purities.  This holds because each edge in the graph is only
visited once, and thus cannot be involved in more than one LUB.  Updating the
$m$ nodes represented by virtual nodes takes no more than $O(m)$ time.  Thus
the whole purity analysis is done in linear time times the height of the purity
ordering.

Native methods can of course not be analyzed, so they must be taken as being
both \semipure\ and \impure.  The naive approach also considers invocations of
interfaces and virtual, non-final methods to be both, too, as it is
undetermined what actual code they execute.  A more reasonable analysis of
virtual methods and interface methods is given in Section
\ref{section:virtualpurity}.

\subsection{Advanced purity}
\label{section:advancedpurity}

While the above purity gives some useful information (see Section
\ref{section:purityresults}), it is a very rough approximation.  If a field has
been altered in any object or array, it is considered \impure\ for all fields
and arrays.  In a loop like in Figure \ref{figure:loop1}, the field accesses to
\code{foo} and \code{bar} are invariant, but because the array is being
changed, the whole loop is considered \impure\ for \code{foo} and \code{bar}.
Thus the optimizer can't assume that the field accesses are invariant and could
be moved outside the loop.

\begin{figure}[htbp]
\begin{center}
\begin{minipage}{5cm}
\begin{verbatim}
  for (i = 0; i < 10; i++) {
    this.foo.bar[i] = 0;
  }
\end{verbatim}
\end{minipage}
\end{center}
\caption{A loop-invariant field access not 
optimizable with simple purity analysis}
\label{figure:loop1}
\end{figure}

In order to find the interesting loop invariants in such a loop, more
information is needed about which objects have which fields manipulated.

Our first approximation was to find the least object of which all objects with
affected fields are all subclasses and store that.  Arrays are kept separately,
with purity information being kept for each kind of array known in the bytecode
(Integer, Long, Float, Double and Object).  This does not take much space, but
each LUB operation can take time proportional to the height of the inheritance
tree.  This we call subclassing purity.

A better approximation is to store the classes that are affected.  This solves
the problem of subclassing purity that two simple reads in different classes
may cause a total loss of information, but takes up a lot more space.  We call
this class-based purity.

The optimal representation is of course to store exactly which fields have been
altered or inspected.  This will take even more space than the classbased
purity, but gives as good information as can be hoped for without using other
kinds of analysis to improve the code first.  This is what we call field-based
purity.

\subsection{Virtual methods}
\label{section:virtualpurity}

The analyses discussed above have the unfortunate drawbacks that they cannot
analyze virtual methods or interface methods, since they don't know what actual
method is being called.  These methods are the most common in Java, since a
method is virtual unless explicitly declared otherwise.

There are two ways to solve this problem: One is to reduce the number of
virtual methods by inferring the actual type of the objects.  Though this would
not get rid of all virtual calls, it should still give a vast improvement.
Type inference of this kind is well studied (\cite{PalsbergSchwartzbach93a},
\cite{Henglein97}), but outside the current scope of this project.  Instead we
have chosen the other, somewhat simpler solution, to make our analysis over all
possible methods called.  This costs precision, as we may include some methods
in the analysis though they couldn't possibly be called, but in many cases only
one method will be examined this way.

To find the possible methods called, one has to make certain assumptions.  The
most important is that the code being optimized must not change after
optimization or be used in other programs than the one currently being
optimized.  If that assumption is violated, we can not know what possible new
subclasses can be introduced and possibly should be included in the analysis.
Another assumption is that all the classes used in the program must be
available, for similar reasons.  These make up the `closed-world' assumption,
that the classes we optimize are part of one and only one
application\footnote{A class being used in several programs could of course be
optimized separately for each program.}.

Additionally, we must know the entry point to the program.  This is needed
because we must be able to deduce which actual classes can possibly be
allocated during program execution.  We only need concern ourselves with these,
instead of trying to find all existing classes.  This entry point will
typically be the \code{main} method in one class.

When analyzing the entry point, which should be done before analyzing any other
method, the optimizer simultaneously traverses the full call graph and creates
a class graph. The class graph will consist of all classes that are allocated
during the call, as well as their superclasses.  The classes that are known to
be allocated are marked as such.

Whenever a virtual method call is analyzed during the purity analysis, the
class graph will be consulted to find where that method is defined.  This is in
the defining class, and possibly also in any of the subclasses.  These methods
are individually analyzed as if they were non-virtual methods, and the result
is the least upper bound of the resulting purities.  In Figure
\ref{figure:bigclassgraph}, the purity of a call to \code{A.g()} will be the
least upper bound of the individual purities of \code{A.g()}, \code{E.g()},
\code{F.g()}, and \code{G.g()}.

If an interface method is called, we have to find all allocated classes that
implement that interface and subinterfaces, and analyze the corresponding
method therein.  These can be virtual methods, too, in which case they must be
analyzed as such.  Thus, in Figure \ref{figure:bigclassgraph}, a call to
\code{Interface1.h()} would combine purities of the \code{h()} methods in
the following classes: \code{B} and \code{H}, because they implement
\code{Interface1}, \code{H}, \code{I}, and \code{G}, because these are
subclasses of classes implementing \code{Interface1}, and \code{J}, because it
implements a subinterface if \code{Interface1}.

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=7.5cm]{classgraph.eps}
%\input{classgraph.epic}
\end{center}
\caption{A class graph with virtual and interface methods}
\label{figure:bigclassgraph}
\end{figure}

\subsection{Experimental purity results}
\label{section:purityresults}

To see the effects of the purity analysis on realistic programs, we have
selected four programs and run the various variants of the purity analysis on
them.  As can be seen in Figure \ref{figure:testprograms}, these programs are
of a non-trivial size.  The programs used are:

\begin{figure*}[htbp]
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
& Classfiles size & & & Virtual\\
& (in kilobytes) & Classes & Methods & methods\\
\hline

Kem &61  & 43& 199 & 187 \\
BYTEmarks &58&19&149&18 \\
Javac &485&167&1142&883 \\
Cream &439&380&2033&1892 \\
\hline
\end{tabular}
\end{center}
\caption{Size of test programs}
\label{figure:testprograms}
\end{figure*}


\begin{description}
\item{\bf Kem:} A bytecode disassembler.
\item{\bf BYTEmarks:} BYTE's benchmark program adapted for Java.  To make
the measurements comparable, they are modified to do a fixed number of
iterations instead of adjusting it by measuring their speed.  Since this is
directly translated from the C version, the style is more imperative than
object-oriented.
\item{\bf Javac:} Javasoft's Java compiler, taken from JDK 1.02.
\item{\bf Cream:} the optimizer itself, excluding a few support classes.  This
contains a lot of very small classes, including one for each bytecode
instruction.
\end{description}

First, we consider the non-virtual purity analyses from Section
\ref{section:simplepurity} and \ref{section:advancedpurity}.  To compare the
quality of the variants, we define a common measurement, the average number of
\semipure\ or \impure\ fields per method.  This is found for a method by
counting through all fields in all known classes, and collecting their purity.
We then take the average of these numbers over all the methods that we want to
optimize.  The results are found in Figure~\ref{figure:simpleresults}.

It may seem odd that the number of \impure\ or \semipure\ fields can rise when
going to a better analysis.  This is because some methods in the better
analysis are found to only read or write that field, but not both.  The actual
average number of fields that are being written to is the sum of the fields
that are only written to and those that are both written to and read from.  As
can be seen, this sum never rises.

There is a big difference in the purity of these programs.  Javac,
for some reason, gives poor results, while Cream, having a
large subclass structure, has many \pure\ and \semipure\ methods.  The analysis
of virtual methods does not give any substantial improvement here, but it is
worth noting that the improvement is in the amount of \semipure\ methods.  This
can be the effect of small encapsulation methods that only read a single
field.

It turned out that \code{Object.$<$init$>$}, the initialization method for
\code{Object}, does not contain any code.  This means that any call to it will
be \pure.  Since methods that do no explicitly make any \code{$<$init$>$}
procedure automatically gets one that calls \code{super.$<$init$>$}, there are
many pure \code{$<$init$>$} methods.  These account for up to one-fourth of the
\pure\ fields in some cases.

Native methods are also an important consideration.  Since we do no know
anything about what they do, they should be considered to be \both\ for all
fields.  Unfortunately, this makes quite a lot of methods \both, for instance
any that may eventually call \code{System.out.println}.  If we could annotate
the native code with information about its purity, we could avoid this
totally.  As an intermeditate solution, we have used the option of letting
native methods be \both\ on all fields in their own object, and \pure\ on
everything else, which gave a tremendous improvement in the purity analysis


Figure \ref{figure:virtualresults} shows the purity when using virtual
purity.  We see that the virtual purity analysis gives better results
than the non-virtual case.  This was not the case when native methods were
considered to be \both\ for all fields, where the amount of information
levelled out when reaching subclassing purity.  This effect is still visible in
the non-virtual purity.

\begin{figure*}[htbp]
\begin{center}
\begin{tabular}{|l|l|r|r|r|r|}
\hline
\multicolumn{2}{|c|}{}&Simple & Subclassing & Class-based & Field-based \\
\hline
Kem
&\pure\ fields: & 21.6 \% & 31.5 \% & 31.6 \% & 31.7 \% \\
&\semipure\ fields: & 3.5 \% & 0.5 \% & 0.3 \% & 0.3 \% \\
&\impure\ fields: & 5.5 \%& 0.2 \%& 0.2 \%& 0.2 \%\\
&\both\ fields: & 69.3 \%& 67.8 \%& 67.9 \%& 67.9 \%\\

\hline
BYTEmarks 
&\pure\ fields: & 8.1 \% & 49.3 \% & 56.0 \% & 57.5 \% \\
&\semipure\ fields: & 3.4 \% & 9.6 \% & 4.6 \% & 3.4 \% \\
&\impure\ fields: & 2.7 \%& 2.5 \%& 1.8 \%& 1.7 \%\\
&\both\ fields: & 85.9 \%& 38.5 \%& 37.6 \%& 37.4 \%\\

\hline
Javac
&\pure\ fields: & 6.0 \% & 33.8 \% & 38.1 \% & 38.2 \% \\
&\semipure\ fields: & 9.4 \% & 3.3 \% & 0.2 \% & 0.1 \% \\
&\impure\ fields: & 5.1 \%& 0.5 \%& 0.1 \%& 0.1 \%\\
&\both\ fields: & 79.6 \%& 62.4 \%& 61.6 \%& 61.6 \%\\

\hline
Cream
&\pure\ fields: & 35.5 \% & 75.9 \% & 77.7 \% & 78.1 \% \\
&\semipure\ fields: & 23.4 \% & 1.6 \% & 0.5 \% & 0.3 \% \\
&\impure\ fields: & 14.9 \%& 0.9 \%& 0.3 \%& 0.2 \%\\
&\both\ fields: & 26.3 \%& 21.5 \%& 21.4 \%& 21.4 \%\\
\hline
\end{tabular}
\end{center}
\caption{Non-virtual purity analysis}
\label{figure:simpleresults}
\end{figure*}

\begin{figure*}[htbp]
\begin{center}
\begin{tabular}{|l|l|r|r|r|r|}
\hline
\multicolumn{2}{|c|}{}&Simple & Subclassing & Class-based & Field-based \\
\hline
Kem
&\pure\ fields: & 21.6 \% & 64.7 \% & 80.9 \% & 82.4 \% \\
&\semipure\ fields: & 4.0 \% & 8.1 \% & 3.0 \% & 1.7 \% \\
&\impure\ fields: & 5.5 \%& 0.8 \%& 0.6 \%& 0.7 \%\\
&\both\ fields: & 68.8 \%& 26.4 \%& 15.5 \%& 15.1 \%\\

\hline
BYTEmarks
&\pure\ fields: & 8.1 \% & 64.2 \% & 77.2 \% & 81.6 \% \\
&\semipure\ fields: & 3.4 \% & 10.8 \% & 8.2 \% & 4.6 \% \\
&\impure\ fields: & 2.7 \%& 5.0 \%& 1.9 \%& 1.9 \%\\
&\both\ fields: & 85.9 \%& 20.0 \%& 12.6 \%& 11.9 \%\\


\hline
Javac
&\pure\ fields: & 6.0 \% & 55.5 \% & 63.9 \% & 77.5 \% \\
&\semipure\ fields: & 13.1 \% & 7.6 \% & 18.3 \% & 5.9 \% \\
&\impure\ fields: & 5.1 \%& 0.7 \%& 0.2 \%& 0.4 \%\\
&\both\ fields: & 75.8 \%& 36.1 \%& 17.6 \%& 16.3 \%\\

\hline
Cream
&\pure\ fields: & 35.5 \% & 85.6 \% & 89.9 \% & 92.2 \% \\
&\semipure\ fields: & 23.7 \% & 2.1 \% & 1.9 \% & 0.9 \% \\
&\impure\ fields: & 14.9 \%& 1.3 \%& 0.6 \%& 0.4 \%\\
&\both\ fields: & 26.0 \%& 10.9 \%& 7.7 \%& 6.5 \%\\

\hline
\end{tabular}
\end{center}
\caption{Virtual purity analysis}
\label{figure:virtualresults}
\end{figure*}

\section{Using purity}
\label{section:usingpurity}

When the purity information has been found, what is it good for?  It tells us
how safe it is to transform the code.  Most common optimizations can benefit
from it.

\paragraph{Dead code removal:}
If the result of a fully \pure\ or \semipure\ instruction is never used, it is
safe to remove that instruction.  Only in the case of an \impure\ instruction
must we keep it, as other computations may depend on the changes made there.
In the example in Figure~\ref{figure:optimizations}, the results of line 9 is
never used, and since it is not \impure for anything, it can be safely removed.
We have implemented this, and the results are listed in Section
\ref{section:results}.  

It may even be possible to determine when an object only can be referenced
locally.  If a method creates an object, but none of its instructions are
\impure\ for fields that could contain it, and it is not returned, it cannot
possibly be known after the method has executed.  It may then become possible
to remove the object entirely.

\paragraph{Loop invariant removal:}
A loop-invariant \pure\ instruction can be moved outside the loop safely.  An
instruction which is \semipure\ for some field can be moved out only if the
loop contains no instructions that are \impure\ for the same field.  Line 6 in
Figure~\ref{figure:optimizations} does not depend on \code{i} in any way, and
can be moved outside the loop.  We have also implemented this optimization, the
results of which are in Section \ref{section:results}.  This optimization
benefits the most from the subclass purity analysis, as it is common practice
to make several field-accesses in one assignment, as shown in Figure
\ref{figure:loop1}.

\paragraph{Constant propagation:}
If a field in an object or an array element is known to be constant, a method
that is not \impure\ for that field or element will never change its value, and
a method that is \pure\ for it will not even need the value.  In
Figure~\ref{figure:optimizations}, the value of \code{baz.qux.quod} is not
changed since the assignment in line 4, and the assignment in line 11 can be
reduced to an increment.

\paragraph{Common subexpression elimination:}
If common subexpressions involve only \pure\ instructions, the optimizer only
need to consider any local variables involved to ascertain whether it is safe
to evaluate them only once.  If there are \semipure\ instructions, there may
not be any instructions that are \impure\ for the relevant fields between the
subexpressions.  In Figure~\ref{figure:optimizations}, \code{bar[i].qux} is
evaluated in lines 7 and 8, though it does not change within one loop
iteration.  Thus, that calculation need be done only once.

\begin{figure}[htbp]
%\begin{center}
%\begin{minipage}{10cm}
\begin{listing}{1}
  public int foo(SomeClass bar[]) {
    int i,a,b,c;
    SomeClass baz = new SomeClass();
    baz.qux.quod = 1;
    for (i = 0; i < 10; i++) {
      a = bar[0].qux.quod;
      b = bar[i].qux.quis;
      c = bar[i].qux.quam;
      b += a + bar[i].qux.quam;
    }
    b += baz.qux.quod;
    return(b);
  }
\end{listing}
%\end{minipage}
%\end{center}
\caption{Examples of possible optimizations}
\label{figure:optimizations}
\end{figure}

\begin{figure}[htbp]
%\begin{center}
%\begin{minipage}{10cm}
\begin{listing}{1}
  public int foo(SomeClass bar[]) {
    int i,a,b;
    a = bar[0].qux.quod;
    for (i = 0; i < 10; i++) {
      OtherClass tmp = bar[i].qux;
      b = tmp.quis;
      b += tmp.quam + a;
    }
    return(b++);
  }
\end{listing}
%\end{minipage}
%\end{center}
\caption{The same example after all optimizations.}
\label{figure:optimizationsdone}
\end{figure}

\subsection{Experimental results}
\label{section:results}

\urldef{\purityurl}\url{http://www.daimi.aau.dk/~elascurn/purity.ps}

Figure~\ref{figure:deadcoderesults} shows how many instructions were removed by
the deadcode analysis, while Figure~\ref{figure:invariantresults} shows the
number of instructions moved as invariant.
 It is obvious that
the purity analysis is essential for the optimizer, and that the more precise
analysis does in fact allow for more optimizations.  

The dead-code optimizations do not benefit at all from the better kinds of
analysis.  This is because it does in fact no use more information than whether
an instruction is \impure\ or not.  For loop-invariant removal it makes a lot
more of a difference, because a field access can be moved outside a loop only if
there are no instructions in the loop that write exactly that
field.  


In order to get maximum benefit from loop invariant removal, it is necessary to
know is the loop body is executed at least once.  As most loops appear to be
while loops at the bytecode level, it was not possible to move instructions
whose values may be used outside the loop.  



In order to overcome this problem, we added a partial loop unroller.  It finds
all exits from the loop above the instruction in question and puts a copy of
those before the loop.  Instructions that are moved outside the loop are then
placed after the copied part, but before the entry to the loop.  This is shown in
Figure~\ref{figure:unrolling}, where the assignment to \texttt{k} can be moved
after unrolling.  The assignment to \texttt{l} can never be moved, as we can
not be sure that it will be executed at all.  Unrolling code turns out to give
a factor five to ten increase in the number of instructions that can be moved.


\begin{figure}[htbp]
\begin{center}
\includegraphics[width=7.5cm]{unroll.eps}
%\input{classgraph.epic}
\end{center}
\caption{Partial unrolling of a loop}
\label{figure:unrolling}
\end{figure}


On the other hand, this could decrease performance if large parts of code is
being duplicated in order to perform relatively small optimizations.  To avoid
this, it is necessary to add some heuristics to judge how much of a loop it is
worthwhile to unroll.  Gripping hand is, any invariant code in the unrolled
part has automatically been moved outside the loop when unrolling, so those are
even cheaper to optimize.  Exactly how to get the best results out of  this is
a separate subject; in our implementation we have just unrolled all necessary
code. 


\begin{figure*}[htbp]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
\multicolumn{2}{|c|}{}& \multicolumn{5}{|c|}{Purity type}\\
\hline
&Total      &None    &Non-virtual  &Virtual     &Virtual      &Virtual\\
&instructions&       &simple       &subclassing &class-based  &field-based\\
\hline
Kem: & 3476& 0& 165& 165& 165& 165\\
BYTEMarks: & 15037& 21& 43& 43& 43& 43\\
Javac: & 40281& 20& 116& 122& 122& 122\\
Cream:&32487 & 274& 376& 376& 376& 376\\
\hline
\end{tabular}
\end{center}
\caption{Number of instructions removed as dead code}
\label{figure:deadcoderesults}
\end{figure*}

\begin{figure*}[htbp]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|}
\hline
\multicolumn{2}{|c|}{}& \multicolumn{5}{|c|}{Purity type}\\
\hline
&Total      &None    &Non-virtual  &Virtual     &Virtual       &Virtual\\
&instructions&       &simple       &subclassing &class-based   &field-based\\
\hline
Kem: & 3471& 8& 8& 94& 179& 209\\
BYTEMarks: & 15015& 10& 10& 965& 1150& 1307\\
Javac: & 40209& 91& 91& 200& 485& 497\\
Cream: & 33709& 159& 159& 388& 653& 873\\
\hline
\end{tabular}
\end{center}
\caption{Number of instructions moved as invariant}
\label{figure:invariantresults}
\end{figure*}

In Figure \ref{figure:executionresults} is shown the improvement in execution
speed for the four programs described in Section \ref{section:purityresults}.
The figure shows raw execution times in seconds and relative exection times for
unoptimized code, optimization without purity analysis, optimization with
simple purity analysis, and optimization with virtual and subclassing purity
analysis.  The programs have been optimized with both dead-code elimination and
loop-invariant removal, and using full unrolling, treating native methods as
being \both\ only for their own object.  The
test programs were run on a Pentium Pro with Linux 2.0.28 using JDK1.02.

The greatest speed improvements are in the BYTEMarks, caused by the many tight,
imperative-style loops in that program.  The other programs, though they have
been quite heavily optimized, too, do not show any interesting increase in
speed.  This seems to indicate that other kinds of optimizations are necessary
for object-oriented programs.  The {\em decreased} speed seen for Cream is
caused by a poor reconstruction of the abstracted instruction order.

\begin{figure*}[htbp]
\begin{center}
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|}
\hline
&No opti-&\multicolumn{2}{|c|}{No purity}&\multicolumn{2}{|c|}{Non-virtual}&\multicolumn{2}{|c|}{Virtual sub-}&\multicolumn{2}{|c|}{Virtual class-}&\multicolumn{2}{|c|}{Virtual field-}\\
&mization&\multicolumn{2}{|c|}{}&\multicolumn{2}{|c|}{simple purity}&\multicolumn{2}{|c|}{classing purity}&\multicolumn{2}{|c|}{based purity}&\multicolumn{2}{|c|}{based purity}\\
\hline
Program&Sec.&Sec.&Rel.&Sec.&Rel.&Sec.&Rel.&Sec.&Rel.&Sec.&Rel.\\
\hline
Kem& 2.83 &2.80 & 0.99 &2.74 & 0.97 &2.78 & 0.98 &2.77 & 0.98 &2.78 & 0.98 \\
BYTEMarks: &30.2 &30.7 & 1.02 &30.7 & 1.02 &24.8 & 0.82 &24.6 & 0.82 &24.1 & 0.80 \\
Javac: &17.75 &17.56 & 0.99 &17.45 & 0.98 &17.49 & 0.99 &17.55 & 0.99 &17.45 & 0.98 \\
Cream: &3.8 &4.2 & 1.09 &4.2 & 1.09 &4.1 & 1.07 &4.1 & 1.07 &4.2 & 1.08 \\
\hline
\end{tabular}
\end{center}
\caption{Improvement in execution time}
\label{figure:executionresults}
\end{figure*}



\section{Related work}
\label{section:relatedwork}

Little optimization has been done on Java so far, but with the popularity of
the language, we will surely see more work in this area.  Suns compiler has
some inlining, though in versions before 1.1 it could break privacy of classes
\cite{Bell96}.  The only optimization they suggest is for the runtime system to
calculate certain constants ahead of time.

Cierniak and Li \cite{CierniakLi96} have made a flexible compiler/optimizer
using an intermediate representation.  It is also able to optimize bytecode to
bytecode, but their article does not mention any interprocedural analysis or
actual results.  This is the only optimizer we know of that are akin to Cream.

There are several bytecode-to-C compilers \cite{Harissa} \cite{Proebstring96},
which then use the C compiler for standard optimizations.  While this gives
many of the well-known optimizations, it does not take the special structure of
an object-oriented language into account.

Side-effect analysis was first thoroughly covered by Banning in
\cite{Banning79}, and the methods improved upon by Kennedy and Cooper in
\cite{CooperKennedy88}.  These papers considered optimizing imperative
languages, and thus did not consider classes and virtual functions.

\section{Conclusions and future work}
\label{section:conclusions}

We have defined and implemented an optimizer using inter-procedural side-effect
analysis.  The analysis has been shown to significantly improve the amount of
optimizations possible, even with a rather conservative optimizer.  Without the
purity analysis, few optimizations could be done, but with it, we see several
times as many optimizations, and, in one case, a performance improvement of up
to 25 \% with the most advanced analysis. 

We have also seen that Java bytecode, because of its simplicity and type
information, is an easy and worthwhile place to perform optimizations.  The
only abstraction needed is to separate control flow and instruction ordering.

It is noteworthy how optimization techniques that work well on imperative
programs have little effect on programs using an object-oriented design.  Other
methods should be developed for these, that take into account the amount of
field references and small, virtual methods.


Implementing common subexpression elimination would likely be worthwhile, as
there are often long chains of fields accesses occuring more than once in a
loop without being invariant.

The results obtained here should be compared to what can be done using the
Harissa bytecode-to-C translator \cite{Harissa}, both alone and together.  
Using an optimizing C compiler as backend gives local optimizations such
as strength reduction and register allocation for free, and the large-scale
optimizations suggested and partially in this paper will still be available.

\section{Acknowledgements}

The optimizer is based on Clark Verbrugge's Coffi program \cite{Verbrugge96}.
Though some rewriting was necessary, it has turned out to be a good starting
point for the program.  Ulrik Pagh Schultz co-implemented the first version of
the optimizer, primarily the virtual purity analysis and the class graph, but
also acted as a sounding board for ideas.  Laurie Hendren has been helpful with
support, advice and lots of corrections.

\bibliographystyle{plain}
\bibliography{main}

\end{document}
