% $Id: opt.tex,v 1.9 1997/02/01 19:35:19 cierniak Exp $


\section{Optimizations}
\label{sec:opt}


This paper describes only one group of optimizations: memory locality
optimizations by data remapping.  We expect that the benefits of those
optimizations will be observed in addition to other optimizations
performed by good JIT compilers.

Locality of memory references is extremely important on modern
machines which have processors much faster than main memories.  On
those machines a high cache hit ratio may significantly increase
execution speed.  Compiler optimizations for improving locality have
been studied extensively and many commercial and research compilers
use those techniques.  Strict definition of Java, especially its
notion of {\em abrupt
  completion\/}~\cite{Java-Language-Specification-1996} makes some of
the existing techniques less effective for Java programs than for
programs written in languages like C or Fortran.

Loop transformations belong to the category of optimizations which
while extremely effective for a wide range of computationally
intensive programs, are more difficult to use in optimizing compilers
for Java.  Java requires that the execution of a loop nest is
performed in a specific order.  Fortran and C have of course the same
requirements, but due to the rich exception mechanism in Java, it is
much easier to write a program in Java which will depend on the order
of loop execution.  In other languages, it usually sufficient to check
if the transformed loop nest does not violate dependence relations
defined by the original loop nest.  In Java this may not be
sufficient, because in the case of an abrupt completion of the loop
nest, the exception handler may depend on partial results being
generated in a specific order.  Detecting that this is not the case
puts an extra burden on the compiler.

Data transformations are an alternative to loop transformations.  Data
transformations have the advantage that they do not change the order
of execution (except for subscript evaluation order which can be dealt
with as described in Section~\ref{sec:opt:legality:evalorder}).  Which
makes checking if a data transformation would change the meaning of
the analyzed piece of code easier than a similar legality check for
loop transformations.  Applying data transformation requires other
checks---ensuring that transformed arrays are rectangular
(Section~\ref{sec:opt:legality:shapes}) is the most important one.  In
our view those checks can be performed without much effort for
traditional, scientific codes.
%
For common cases of array-based scientific applications both loop and
data transformations are equally powerful.  We show
in~\cite{Cierniak-Li-PLDI-1995} that a unified data and loop
transformation framework is needed for best performance.

We focus here on the effect of Java semantics on data layout
optimizations which improve memory hierarchies utilization.  We have
previously described similar optimizations for programs written in C
and Fortran~\cite{Cierniak-Li-PLDI-1995}.  Changing the data layout
for those languages is very difficult since both C and Fortran define
the layout of their data structures and any changes may be attempted
only after compiler analysis which ensures the legality of a data
transformation.  Such analysis is often very complex and sometimes
fails inhibiting any potential optimizations.

Changing the layout of data structures is much easier in Java since
the bytecodes do not use the concept of an address and cannot access,
say, a field in an object by specifying an integer offset from some
base pointer.  Similarly, pointer arithmetic cannot be used to access
elements of an array.



\subsection{Array layout optimizations}
\label{sec:opt:array}

Cache locality can be often significantly improved by changing the
layout of array elements in memory so that for a given access pattern,
array elements are more likely to lie in the cache which can be
accessed much faster than main memory.

Our array layout optimizations optimizations rearrange
multi-dimensional arrays in the context of nested loops.  To perform
any of those, we first have to recover multidimensional array
references and for-loops from the bytecode representation.
See~\cite{Cierniak-Li-PLDI-1995} for a more comprehensive discussion
of array and loop transformations.

\subsection{Field layout optimizations}
\label{sec:opt:field}

Many Java programs create data structures built with objects.
Accesses to such objects can be made much faster if fields which are
likely to be accessed together are placed in consecutive memory
locations so that they are likely to reside in the same cache line.
This optimization increases the likelihood that even if the access to
the first field missed in the cache, the access to the second field
will be a cache hit.



\subsection{Legality of code and data transformations}
\label{sec:opt:legality}


Before we apply our transformations, we have to ensure that they do
not change the meaning of the program.  There are three issues we have
to deal with for our transformations.
\begin{itemize}
\item Arrays we remap must be rectangular.
\item The order of evaluation of a remapped array reference must be
  the same as for the original expression (see Section 15.12.1
  of~\cite{Java-Language-Specification-1996}).
%\item Field initialization order must not be violated.
\end{itemize}
%Only the first two issues will be of any importance in the JIT version
%of Briki.  The possibility of violating the order of field
%initialization is an artifact of our off-line implementation which
%produces Java source as an intermediate step.  
The rest of this section gives more details about each of those three
potential problems.




\subsubsection{Array shapes}
\label{sec:opt:legality:shapes}

Array remappings used in our data and code transformations
framework~\cite{Cierniak-Li-PLDI-1995} can be applied only to
multidimensional array which are {\em rectangular}.  In a rectangular
array all elements in a given dimension have the same size.
Compiler-supported arrays in languages like C, C++ or Fortran are
rectangular (of course a programmer may implement non-rectangular
arrays explicitly by linearizing the logical structure in a
one-dimensional array).  Multidimensional arrays in Java are more
general since they are treated as arrays of arrays.

For our optimizations, we check the array was allocated using the {\tt
  multinewarray} opcode and that all accesses to that array use all
dimensions.  This approach is more conservative than necessary, but it
is very fast and completely adequate for scientific codes.



\subsubsection{Array expression evaluation order}
\label{sec:opt:legality:evalorder}

The definition of Java specifies that a multidimensional array
reference must be evaluated from left to right.  Our simplest
remapping switches two dimensions thus changing the evaluation order.

We solve this problem by checking if subscript expressions have
potential side effects (note that a possibility of an abrupt
completion is a potential side effect).  Those subscript expressions
that may have potential side effects, are being evaluated in the
original order with the results being stored in local variables rather
than being stored on the stack directly.



%\subsubsection{Field initialization order}
%\label{sec:opt:legality:fields}
%This issue will not exist anymore for our JIT implementation of
%Briki.  We have to deal with it temporarily because of the way we
%currently control the field layouts.  In principle it not possible to
%control the layout of an object in Java source.  However, since we use
%a specific Java to bytecode compiler and a specific VM implementation,
%we can have full control over the issue by knowing the exact algorithm
%of field layout.  Since this problem is an artifact of our preliminary
%compiler architecture, we do not discuss it in detail.
