
\documentclass{article}

\author{
Aart J.C. Bik  and Dennis B. Gannon \\
Lindley Hall 215, Computer Science Department, Indiana University \\
Bloomington, Indiana 47405-4101, USA \\
\texttt{ ajcbik@extreme.indiana.edu } \\
}

\title{A Prototype Bytecode Parallelization Tool}

\date{} 

\input{mystyle.tex}

\addtolength{\textheight}    {+3.50cm}
\addtolength{\topmargin}     {-1.75cm}
\addtolength{\textwidth}     {+2.00cm}
\addtolength{\oddsidemargin} {-1.00cm}
\addtolength{\evensidemargin}{-1.00cm}

\begin{document}

\maketitle 

\begin{abstract}
This paper provides a manual for {\tt javab}, a prototype tool that 
supports the automatic detection and exploitation of 
implicit loop parallelism in JVM bytecode.
Implicit parallelism is made explicit by means of the multi-threading mechanism
provided by the JVM. Automatically exploiting implicit
parallelism at bytecode level can be done independently from
the source program and platform from which the bytecode was obtained,
and independently from the platform on which the bytecode eventually will run.
The parallelized bytecode remains architectural neutral
and may exhibit speedup on any platform 
that supports the true parallel execution of JVM threads.  \\
This project is supported by DARPA under contract ARPA F19628-94-C-0057
through a subcontract from Syracuse University.
\end{abstract}

\section{Introduction}
In this paper, we describe our prototype research
tool {\tt javab}, which is a bytecode tool
(written in C) that supports the automatic detection and
automatic exploitation of implicit loop parallelism in bytecode, 
i.e. the architectural neutral instructions of the JVM (Java Virtual Machine).
The tool performs a bytecode to bytecode transformation, 
where implicit loop parallelism is made explicit
by means of the multi-threading mechanism
provided by the JVM~\cite{javalang,javavm,javaconc,meyer,javathreads}.

\plaat{t}
\resizebox{11cm}{!}{\includegraphics{javab.ps}}
\taalp{Automatic Bytecode Parallelization by {\tt javab}}{javab}

In figure~\ref{javab}, we illustrate the
automatic exploitation of implicit loop parallelism
in JVM bytecode. A binary file {\tt MyClass.class} 
in the class file format~\cite{javavm} is used as input of {\tt javab}.
Thereafter, the compiler transforms the input program
into a form that uses the JVM multi-threading mechanism
to make all implicit parallelism explicit.
Because parallelism is expressed in JVM bytecode itself,
the transformed program can still be 
executed by any implementation of the JVM ({\tt java} in the figure,
or, alternatively, an interpreter that is embedded in a 
browser or appletviewer), and speedup can be obtained on any platform 
that supports the true parallel execution of threads.
All transformations can be done independently from
the source program and platform from which the bytecode was obtained,
and independently from the platform on which the bytecode eventually will run.
Hence, this approach allows the optimization of bytecodes
that have been generated by the Java compiler {\tt javac},
bytecodes that have been downloaded over a network, bytecodes generated
by bytecode producing compilers 
for other high level languages, or bytecodes produced
by a JVM assembler like Jasmin~\cite{jasmin,meyer}. 

Because filenames are essential in Java, the
transformed program is stored in the file 
{\tt MyClass.class} again, after a copy of the
original program has been saved in 
 {\tt MyClass.old}.\footnote{
Our prototype Java restructuring
compiler {\tt javar}~\cite{bikgana,bikgan4} renames a source
file {\tt MyClass.java} into {\tt MyClass.orig}, so that
both tools can be used without conflicts.}
Some auxiliary classes,
support the parallel execution of loops,
may also be generated by the bytecode
parallelization tool {\tt javab}

To keep compile-time limited, the prototype relies on 
relatively simple but generally also less expensive analysis,
rather than doing, for instance, advanced data dependence
analysis (see e.g.~\cite{banerbook3,midkiff,pol,pugh_omega,wolfe96,zima}).
Although currently an off-line bytecode to bytecode transformation is applied,
keeping compile-time limited may become more important
if the techniques are used for some form of JIT parallelization,
i.e. bytecode parallelization directly prior to execution.

\section{{\tt javab} Command}
The bytecode tool {\tt javab} is invoked as follows:

\code
\verb"javab [-bcdlnopqsv] [file ...]" \\
\edoc

An arbitrary number of class files may be supplied 
to the tool (e.g. `{\tt javab Class1.class Class2.class}'
or `{\tt javab *.class}'), and the options
may be given in any order (e.g. `{\tt javab -op MyClass.class}', 
`{\tt javab -o -p MyClass.class}', or `{\tt javab -o MyClass.class -p}').

The options have the following meaning for all
specified class files:

\begin{itemize}
\item \verb"-b" : 
  Enforces {\tt javab} to show information 
  about the basic blocks in the JVM bytecode.
\item \verb"-c" : 
  Enforces {\tt javab} to summarize
  constant pool contents.
\item \verb"-d" : 
  Enforces {\tt javab} to print the JVM 
  bytecode instructions for each method.
\item \verb"-l" : 
  Enforces {\tt javab} to preserve the exact
  handling semantics of \emph{linking\/} exceptions.
\item \verb"-n" : 
  Enables loop parallelization of \emph{single\/} loops.
\item \verb"-o" : 
  Enforces {\tt javab} to write back each class file.
\item \verb"-p" : 
  Enforces {\tt javab} to automatically detect implicit parallel
  loops in the JVM bytecode.
\item \verb"-q" : 
  Enables user interaction if
  inter-procedural information is required.
\item \verb"-s" : 
  Enforces {\tt javab} to show the
  stack states associated with each
  bytecode instruction.
\item \verb"-v" : 
  Enforces {\tt javab} to print messages
  about its activities. 
\end{itemize}

A nonzero exit status is returned by {\tt javab}
if an error is encountered in \emph{any\/} of the specified
class files,  and a zero exit status otherwise.
All errors, messages, user queries, and output enforced
by the options `{\tt -bcdsv}' are written to standard error.

With only the `{\tt -p}' option, {\tt javab} merely 
attempts to detect implicit loop parallelism without
actually transforming the input class files.

With the `{\tt -o}' option, {\tt javab}
renames each class file {\tt MyClass.class}
into {\tt MyClass.old} and generates
the output for this file in {\tt MyClass.class} again.
If {\tt javab} cannot rename a file {\tt MyClass.class}
into {\tt MyClass.old} because this latter file
already exists, {\tt javab} assumes that the conversion
already has been done.  In this case, the programmer 
must first rename {\tt MyClass.old} into {\tt MyClass.class}
if the former file indeed contains the original bytecode program,
or, otherwise, the programmer must first deal with the
conflicting file {\tt MyClass.old} in some other manner. 
If no files are specified, then {\tt javab} reads
a class file from standard input and, if the option `{\tt -o}'
is also given, writes the class file back to standard output, 
which enables the use of {\tt javab} in 
Unix pipes or  input-output redirections~\cite{unix}
(e.g. {\tt javab -op < filein > fileout}).
Clearly, the `{\tt -o}' option is only useful
when combined with the parallelization `{\tt -p}' option.

\section{Automatic Loop Parallelization of JVM Bytecode}
If the `{\tt -p}' flag is given, {\tt javab} examines the 
JVM bytecode of every method in each class file to automatically
detect and exploit implicit parallelism in the natural loops that are 
defined by back edges in the flow graph 
(see e.g.~\cite{aho,appel,fisher,parsons,wolfe96,zima}).
The default approach taken by  {\tt javab} 
to preserve the user-visible state after exceptions~\cite{javavm} 
as much as possible (without being over restrictive with respect to transformations)
is to only transform regions of code for which the compiler 
can prove that {\bf run-time exceptions} cannot occur, but to allow
semantical changes with respect to the handling of {\bf JVM errors}
and {\bf linking exceptions}.  The compiler-switch `{\tt -l}' can be used, however,
to preserve the exact handling semantics of linking exceptions as well.

In some cases, the tool can detect implicit loop parallelism
completely automatically. For example, below
we show a small Java fragment together with
the corresponding JVM bytecode (as presented by our research tool):

\code
\begin{tabular}{l}
\verb"static double[] loop1(int n) {" \\
\verb"  double[] a = new double[n];" \\
\verb"  for (int i = 0; i < n; i++)" \\
\verb"     a[i] = 1.0;" \\
\verb"  return a;" \\
\verb"}" \\
\vspace*{4cm}
\end{tabular}
\verb"          "
\begin{tabular}{l}
\verb"*** method 0x08 loop1(I)[D 1->1" \\
\verb"    max_stack   = 4" \\
\verb"    max_locals  = 3" \\
\verb"    code_length = 23" \\
\verb" ----------" \\
\verb" [ 0]  0:  iload_0" \\
\verb"*[ 1]  1:  newarray double" \\
\verb" ----------" \\
\verb" [ 1]  3:  astore_1" \\
\verb" [ 0]  4:  iconst_0" \\
\verb" [ 1]  5:  istore_2" \\
\verb" [ 0]  6:  goto 16" \\
\verb" ----------" \\
\verb" [ 0]  9:  aload_1" \\
\verb" [ 1] 10:  iload_2" \\
\verb" [ 2] 11:  dconst_1" \\
\verb"*[ 4] 12:  dastore" \\
\verb" ----------" \\
\verb" [ 0] 13:  iinc 2 1" \\
\verb" ----------" \\
\verb" [ 0] 16:  iload_2" \\
\verb" [ 1] 17:  iload_0" \\
\verb" [ 2] 18:  if_icmplt 9" \\
\verb" ----------" \\
\verb" [ 0] 21:  aload_1" \\
\verb" [ 1] 22:  areturn" \\
\verb" ----------" \\
\end{tabular}
\edoc

First, the access flags,  name, and method descriptor~\cite[ch4]{javavm} of 
the method are shown (`{\tt  0x08 loop1(I)[D}').  The next 
descriptor $w \rightarrow w'$ denotes
the corresponding number of words moved from the
operand stack of the caller into locals
of the callee, and pushed on the operand stack 
of the caller by the callee on return, respectively. 
Finally, the bytecode is presented, where different basic blocks
are separated by horizontal lines.  For each instruction,
the byte offset is shown together with the number of words that reside
on the stack prior to execution of this instruction in between square brackets.

Each instruction that may throw a run-time
or linking exception (ignoring JVM errors)
is marked with an `{\tt *}'.
For this particular loop, {\tt javab} can determine
that the abnormal loop-exit from the instruction 
at address~12 will not be taken,
because a non-{\tt null} array reference is used,
and the index is always within bounds of the declared
array. Furthermore, {\tt javab} can determine
that all iterations of the bytecode loop corresponding
to the {\tt i}-loop are completely independent. Hence,
the prototype proceeds with parallelization of this loop.

If the method {\tt loop1()}
appears in a class file {\tt MyClass.class}
that defines a class with the fully qualified
name {\tt package.MyClass}, then {\tt javab} 
subsequently constructs a new class file
{\tt MyClass\_loop1\_x.class} that defines
an auxiliary class {\tt package.MyClass\_loop1\_x}
(where `{\tt \_x}' denotes some compiler-generated number),
and places this new class file
in the same directory as where the original class file resided.
In this manner, the auxiliary class belongs to the same
package as the original class.
The auxiliary class is a sub-class of `{\tt java.lang.Thread}',
and contains a {\tt run()}-method that can be used to let
different threads executed the loop-body of the parallel loop
concurrently.  The number of threads $T$, where  $2 \leq T \leq 16$,
that must be used for the parallel execution 
can be defined by the environment variable `{\tt JAVAB\_THREADS}'
(the default value is $T=4$).  The original loop in
{\tt MyClass.class} is replaced by a construct
that initiates these $T$ threads.
After all loops in the original class file
have been examined, the (possibly) modified class is written back into
the file {\tt MyClass.class}, after
a copy of the original program has been saved in a
file {\tt MyClass.old}.

In other cases, user interaction may be required.
For example, below
we show another small Java fragment together with
the corresponding JVM bytecode:

\code
\begin{tabular}{l}
\verb"static void loop2(double a[], int n) {" \\
\verb"  for (int i = 0; i <= n+30; i++)" \\
\verb"     a[i] = 1.0;" \\
\verb"}" \\
\vspace*{4cm}
\end{tabular}
\verb"          "
\begin{tabular}{l}
\verb"*** method 0x08 loop2([DI)V 2->0" \\
\verb"    max_stack   = 4" \\
\verb"    max_locals  = 3" \\
\verb"    code_length = 21" \\
\verb" ----------" \\
\verb" [ 0]  0:  iconst_0" \\
\verb" [ 1]  1:  istore_2" \\
\verb" [ 0]  2:  goto 12" \\
\verb" ----------" \\
\verb" [ 0]  5:  aload_0" \\
\verb" [ 1]  6:  iload_2" \\
\verb" [ 2]  7:  dconst_1" \\
\verb"*[ 4]  8:  dastore" \\
\verb" ----------" \\
\verb" [ 0]  9:  iinc 2 1" \\
\verb" ----------" \\
\verb" [ 0] 12:  iload_2" \\
\verb" [ 1] 13:  iload_1" \\
\verb" [ 2] 14:  bipush 30" \\
\verb" [ 3] 16:  iadd" \\
\verb" [ 2] 17:  if_icmple 5" \\
\verb" ----------" \\
\verb" [ 0] 20:  return" \\
\verb" ----------" \\
\end{tabular}
\edoc

Here, although {\tt javab} can determine that the iterations
of the bytecode loop corresponding to the {\tt i}-loop are independent,
without inter-procedural analysis the compiler cannot
determine whether an abnormal loop-exit due to a run-time
exception thrown by the {\tt dastore} at address~8 may occur.
In such cases, either worst-case assumptions are made by resorting
to keeping the loop serial (the default), or, if the
compiler-switch `{\tt -q}' is given, user-interaction
is initiated to obtain inter-procedural analysis:

\code
\begin{tabular}{l}
\verb"*** MyClass.class:: Queries for method `loop2([DI)V'" \\
\verb"> Queries for the 1-dimensional array parameter `[D' in local 0" \\
\verb"      * dim-1: is range [0, 31+n) valid where n = parameter in local 1?" \\
\verb"      (y/n/q) =>"  \\
\end{tabular}
\edoc

The following responses can be used:

\begin{itemize}
\item `{\tt y}': confirms the query
\item `{\tt n}': denies the query (the loop will be kept serial)
\item `{\tt q}': denies the query, and disables further user interaction
\end{itemize}

Furthermore, to prevent unforeseen loop-carried
data dependences, for each array parameter
that is involved in a {\tt <t>astore} instruction
within the candidate parallel loop, the compiler also inquiries the user
whether this parameters will always
refer to non-overlapping (sub) arrays in memory 
with respect to \emph{all\/} other array parameters that
are referred to within the loop.

Consider, for example, the following Java
static method {\tt query()}:

\code
\begin{tabular}{l}
\verb"static void query(int[][] a, int[] b, int x[], int k, int l) {" \\
\verb"  for (int i = 0; i <= k+100; i++)" \\
\verb"     for (int j = 0; j < l-25; j++)" \\
\verb"        b[i] += a[i][j] * x[j];" \\
\verb"}" \\
\end{tabular}
\edoc

If user interaction is enabled with the
flag `{\tt -q}', then eventually the following inquiries
will be made to the programmer:

\code
\begin{tabular}{l}
\verb"*** ManQuery.class:: Queries for method `query([[I[I[III)V'" \\
\verb"  > Queries for the 2-dimensional array parameter `[[I' in local 0" \\
\verb"    * dim-1: is range [0,101+n) valid where n = parameter in local 3?" \\
\verb"    * dim-2: is range [0,-25+n) valid where n = parameter in local 4?" \\
\verb"  > Queries for the 1-dimensional array parameter `[I' in local 2" \\
\verb"    * dim-1: is range [0,-25+n) valid where n = parameter in local 4?" \\
\verb"  > Queries for the 1-dimensional array parameter `[I' in local 1" \\
\verb"    * dim-1: is range [0,101+n) valid where n = parameter in local 3?" \\
\verb"Is storage of array parameters 0 `[[I' and 1 `[I' non-overlapping?" \\
\verb"Is storage of array parameters 2 `[I'  and 1 `[I' non-overlapping?" \\
\end{tabular}
\edoc

We realize that resorting to user interaction as soon
as inter-procedural information is required may
place a heavy burden on the user, especially
if source code is not available. However, these problems
will be alleviated by the incorporation of inter-procedural analysis 
in environments where complete bytecode programs are available.

\section{Concluding Remarks}
For a more detailed presentation of the techniques used by the prototype bytecode 
parallelization tool {\tt javab}, we refer to~\cite{bikgan5}.
Please keep in mind that {\tt javab} is
a prototype tool, and not a robust commercial product.
We hope, however, that this bytecode parallelization tool
provides an environment with sufficient functionality to 
enable rapid prototyping of new automatic
JVM bytecode parallelization methods. We encourage
users to modify or extend {\tt javab} for  further experimentation with
bytecode parallelization (please refer to the {\tt LICENSE} file
provided with {\tt javab} for details on the
licensing terms). With the `{\tt -v}' flag, {\tt javab}  provides
some information on why particular loops cannot be parallelized. 
We hope that using this option may gain insight in the kind of 
improvements required to
increase the number of loops in JVM bytecodes that can be parallelized
automatically.

New releases of {\tt javab}
(and the Java restructuring compiler {\tt javar}~\cite{bikgana,bikgan4})
are made available at our HP-Java page 
(\verb"http://www.extreme.indiana.edu/hpjava/").
Please send us all your comments, bug reports, experiences,
and suggestions ({\tt ajcbik@extreme.indiana.edu}).

\clearpage

\small
\nocite{budimlic,carpenter,cierniak,fox1,c,unix}
\bibliographystyle{plain}  
\bibliography{biblio}

\end{document}
