
\documentclass{article}

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

\title{
%{\tt javar} Manual (version 1.3BETA)\thanks{
{\tt javar}: A Prototype Java Restructuring Compiler\thanks{
This project is supported by DARPA under contract ARPA F19628-94-C-0057
through a subcontract from Syracuse University.
}
}

\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 describes the prototype
restructuring compiler {\tt javar}, which can be used
to make implicit parallelism in a Java program explicit
by means of multi-threading.  Although the prototype does
\emph{not\/} provide a complete Java front-end
(unicode escapes are not supported
and only limited semantic analysis has been
implemented) and relies \emph{completely\/} on the
identification of `implicit' parallelism
by means of annotations, we hope that the
research tool still provides sufficient functionality to
make  the parallelization of Java programs
less complex and less error-prone.
\end{abstract}

\section{Introduction}
In this paper, we describe our prototype research
tool {\tt javar}, a simple Java restructuring compiler
(written in C) that can automatically  transform a Java program into 
a form in which  implicit parallelism 
is made explicit by means of multi-threading~\cite{javatm,javahow,javanut,
javalang,javaconc,
javaun,javahand,javaexp,javathreads,javatricks}.
Although, ideally, the \emph{detection\/} of implicit parallelism
is also done automatically, in the prototype
the programmer must identify all `implicit' parallelism 
by means of annotations. The transformations that
make this parallelism explicit, however,
are done automatically by {\tt javar},
which simplifies the task of the programmer substantially
and makes the parallelization less error-prone. 

In figure~\ref{javar}, we illustrate our approach
to automatically exploiting implicit parallelism
in Java programs. A Java program {\tt MyClass.java} is used as input
of our source to source Java restructuring compiler {\tt javar}.
Thereafter, the compiler transforms the input program
into a form that uses the multi-threading mechanism
of Java to make all implicit parallelism explicit.
Because parallelism is expressed in Java itself,
the transformed program can still be compiled into byte-code
by any Java compiler ({\tt javac} in the figure), and subsequently interpreted by
any  byte-code interpreter ({\tt java} in the figure,
or, alternatively, an interpreter that is embedded in a 
browser or appletviewer). Speedup can be obtained on any platform 
that supports the true parallel execution of threads.

\plaat{t}
\resizebox{9cm}{!}{\includegraphics{javar.ps}}
\taalp{Restructuring, compiling, and interpreting}{javar}

Because filenames are essential in Java, the
transformed program is stored in the file 
{\tt MyClass.java} after a copy of the
original program has been saved in a
file {\tt MyClass.orig}. In case changes to
the original program are required,
this latter file must be renamed into {\tt MyClass.java} again
before {\tt javar} can be re-applied to the program.

\section{{\tt javar} Command}
The compiler {\tt javar} is invoked as follows:

\code
\verb"javar [-cnopvw] [file ...]" \\
\edoc

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

The options have the following meaning:

\begin{itemize}
\item \verb"-c" : Enforces {\tt javar} to preserve comments in the program text.\footnote{
In the current version, only comments that appear
before class-, interface-, constructor-, and member-declarations 
are preserved (and these comments may float a little in the output program text).}
\item \verb"-n" : Enforces {\tt javar} to print the derived meaning
		  of names in a program.
\item \verb"-o" : Enforces the generation of output for each compilation unit.
\item \verb"-p" : Enforces the generation of parallel code.
\item \verb"-v" : Enforces {\tt javar} to print messages
		  about its activities. 
\item \verb"-w" : Enforces the generation of an HTML presentation
		   of all compilation units.
\end{itemize}

Without the `{\tt -o}' option, {\tt javar}
can be used for syntax and limited
semantic analysis (e.g. `{\tt javar MyClass.java}'),
and for parallel code generation without output
(e.g. `{\tt javar -p MyClass.java}').
With the `{\tt -o}' option, {\tt javar}
renames each input file {\tt MyClass.java}
into {\tt MyClass.orig} and generates
the output for this file in {\tt MyClass.java} again,
so that {\tt javar} can be used as a `pretty-printer' that presents each
Java program in some rigid format (e.g. `{\tt javar -o *.java}'), or
as a parallelizing compiler (e.g. `{\tt javar -op *.java}'). Finally,
the `{\tt -w}' option can be used to construct an 
HTML representation of all compilation
units. This HTML representation (with root file `{\tt index.html}')
is placed in the directory defined by the environment variable 
{\tt JAVAR\_HTML} (or the current directory by default).

If no files are specified, {\tt javar} reads
from standard input and, if the option `{\tt -o}'
is given, writes to standard output, which
enables the use of {\tt javar} used in 
Unix pipes or  input-output redirections~\cite{unix}
(e.g. {\tt javar -o < filein > fileout}).
All errors, messages, and output enforced
by the `{\tt -v}' or `{\tt -n}' option are written to standard error.
If {\tt javar} cannot rename a file {\tt MyClass.java}
into {\tt MyClass.orig} because this latter file
already exists, {\tt javar} assumes that the conversion
already has been done. In this case, the programmer
must first rename {\tt MyClass.orig} into {\tt MyClass.java}
if the former file indeed contains the original program,
or, otherwise, the programmer must first deal with the
conflicting file {\tt MyClass.orig} in some other manner. 

A nonzero exit status is returned by {\tt javar}
if an error is encountered
in \emph{any\/} of the compilation units,  and
a zero exit status otherwise.
Invoking {\tt javar} as a rapid syntax and limited semantic analyzer 
before the Java compiler {\tt javac} for all compilation
units defined by the arguments of a UNIX shell script, for example,
can be implemented as follows:

\code
\begin{tabular}{l}
\verb"javar $*" \\
\verb"if [ $? -eq 0 ]" \\
\verb"then" \\
\verb"  javac -O $*" \\
\verb"fi" \\
\end{tabular}
\edoc

\section{Parallel Loops}
As illustrated below, a parallel loop is identified using the
loop annotation `{\tt /*par*/}' 
(which is simply ignored by other Java compilers)
before a for-loop:

\code
\begin{tabular}{l}
\verb"/*par*/" \\
\verb"for (int i = 500; i > 0; i -= 3)" \\
\verb"   body(i);" 
\end{tabular}
\edoc

\subsection{Loop Annotations}\label{annot}
A comma-separated list of the following constructs
can be optionally used in  between the `{\tt /*par}'  and the
`{\tt */}' of a loop annotation:

\begin{itemize}
\item `{\tt threads = <int>}' : 
	Defines the number of threads that must  be
	used for parallel execution
        (e.g. `{\tt /*par threads = 2 */}').
	The default value is 4.
\item one of `{\tt block}', `{\tt cyclic}', or `{\tt guided}' :
      Defines either block scheduling, cyclic scheduling, or
      guided self-scheduling as the scheduling policy
      for the parallel loop
   (see e.g.~\cite{pol,wolfe,wolfe96,zima}).
      The default policy is guided self-scheduling.
\item `{\tt multi = <int>}' : 
	Enforces the generation of
        multi-version code where at run-time either
	the serial or parallel version of the
	loop is executed depending on the
	number of iterations. The parameter defines
	the threshold (e.g. `{\tt /*par multi = 150 */}').
	 The default value is~0 (i.e. no multi-version code).
\item `{\tt ( <name> )}' :  
Enforces the generation of a parallel loop that 
catches any exception assignable to the specified exception that 
is thrown in one of the threads of the loop, and
 explicitly re-throws this exception 
in the thread that initiated the parallel loop.
\item `{\tt sync = <int>}' :
	Defines the number of synchronization
	variables that are required for DOACROSS-like execution
	 (e.g. `{\tt /*par sync = 2 */}').
	 The default value is~0 (i.e. DOALL-like execution).
\item one of `{\tt sups\_wait}' or `{\tt busy\_wait}':
Defines either a suspended-waiting (the default) or a busy-waiting
implementation of random synchronization in a DOACROSS-like loop.
\end{itemize}

An arbitrary stride may be used for DOALL-loops, whereas
each DOACROSS-loop must have stride-1.
Within the body of a DOACROSS-like parallel loop,
the following two loop annotations can be used
to insert random synchronization
(see e.g.~\cite{midkiff2,wolfe96,zima}) that enforces
certain loop-carried data dependences:

\begin{itemize}
\item `{\tt /*post <int> */}' : 
	Annotation  `{\tt /*post k */}' inserts
	a {\bf post}-statement that during
	each iteration {\tt i} will set
	the {\tt i}th bit of the {\tt k}th synchronization
	variable (where ${\tt 0} \leq {\tt k} < {\tt n}$
	in case  `{\tt sync = n}' has been set).
\item `{\tt /*wait <int>, <expr> */}'  : 
	Annotation  `{\tt /*wait k, j */}' inserts
	a {\bf wait}-statement that will block
	until the  {\tt j}th bit of the {\tt k}th synchronization
	variable has been set (where ${\tt 0} \leq {\tt k} < {\tt n}$
	in case  `{\tt sync = n}' has been set).
\end{itemize}

For example, the annotations shown below convert
the {\tt i}-loop into a cyclic-scheduled DOACROSS-loop
in which a busy-waiting implementation of random synchronization
enforces the  static flow dependences
$S_1 \delta_< S_2$ and $S_3 \delta_< S_2$ with
dependence distance~8 and~9, respectively:

\code
\begin{tabular}{l}
\verb"      /*par sync = 2, cyclic, busy_wait */" \\
\verb"      for (int i = 9; i < N-8; i++) {" \\
\verb"S1:     a[i+8] /= 3.0D; " \\
\verb"        /*post 0 */                               // post(ASYNC, i)" \\
\verb"        /*wait 0, i-8 */                          // wait(ASYNC, i-8)" \\
\verb"        /*wait 1, i-9 */                          // wait(CSYNC, i-9)" \\
\verb"S2:     d[i]   += c[i-9] * a[i];" \\
\verb"S3:     c[i]   /= 8.0D;" \\
\verb"        /*post 1 */                               // post(CSYNC, i)" \\
\verb"      }" \\
\end{tabular}
\edoc

Because random synchronization annotations are
effectively handled as statements by {\tt javar},  
all labels that appear \emph{directly before\/} such annotations
will be associated with the corresponding statements
after parallelization
(rather than with the first real Java statement in the original program). 

\subsection{Actual Loop Parallelization}
In the prototype version of {\tt javar}, it is 
\emph{the responsibility
of the programmer\/} to identify the DOALL- and DOACROSS-like and
parallel loops in a program and, for the latter kind
of loops, to provide the appropriate random synchronization annotations.
Each parallel loop in a Java program is simply processed
by {\tt javar}  without further ascertaining whether the
parallelization  actually preserves the
semantics of the original program. 

The source to source restructuring compiler
{\tt javar} uses the method described in~\cite{bikgana}
to make loop parallelism explicit
by means of multi-threading. Given a parallel loop,
the following steps are taken: (i) the annotation is examined,
(ii) the loop is analyzed to determine
whether the method of~\cite{bikgana} is applicable
and, (iii) parallel code is generated.

\subsubsection{Examination of Parallel Loop Annotation}
A compile-time error occurs, if no or an invalid value
is supplied for any of the
constructs `{\tt threads}', `{\tt sync}', or `{\tt multi}',
in case a value is supplied if none is required,
in case an unknown keyword appears in the loop
annotation, or if an annotation `{\tt /*par*/}'
does not appear directly before a for-loop.

For example, {\tt javar} generates the following
error for the fragment shown below:

\code
\begin{tabular}{l}
\verb"  ..." \\
\verb"  /*par sync=10, cpu=5 */                  // <- line 14" \\
\verb"  for (int i = 0; i < N; i++)" \\
\verb"     a[i] = 10.0;" \\
\verb"  ..." \\
\verb" " \\
\verb"> javar -op Loop.java" \\
\verb"javar :: [line 14, Loop.java] cannot process cpu in loop annotation" \\
\verb"javar :: no output for Loop.java" \\
\end{tabular}
\edoc

Specifications of parallel 
loops \emph{within\/} another parallel loop 
are ignored (also in the serial branch of multi-version code).
Likewise, {\tt javar} ignores random synchronization annotations that appear
\emph{outside\/} parallel loops or that operate
on undeclared synchronization variables.

\subsubsection{Analysis of Loop}
If the `{\tt -p}' flag is given, the following
tests are performed for each parallel loop to determine
whether the method of~\cite{bikgana} is applicable:

\begin{enumerate} \item[(1)] The loop header must have the form
`{\tt for (int i = init; e1; e2)}',
where  \\
{\tt e1} is any of {\tt i<high}, or {\tt i<=high}, {\tt high>i}, or {\tt high>=i} 
and {\tt e2} is  {\tt i++} or {\tt i+=stride}, or  \\
 {\tt e1} is either {\tt i>low}, {\tt i>=low}, 
{\tt low<i}, or {\tt low<=i}   and
 {\tt e2} is  {\tt i--} or {\tt i-=stride}. \\
Loop index {\tt i} may not occur in {\tt init}, {\tt low}, or {\tt high}.
\end{enumerate}

Failure to adhere to this form results in a compile-time error.
Below we give some examples of loops that must be rewritten
before {\tt javar} can be used for parallelization: 

\begin{flushleft} \scriptsize
\begin{tabular}{l|l|l}
Original Loop & Rewritten Loop & Comments \\
\hline 
\verb"int i;" & & \\
\verb"for (i = 0; i < 100; i++)" & 
          \verb"for (int i = 0; i < 100; i++)" & use a  locally \\
\verb"   body(i);"   &
          \verb"   body(i);"                   & declared loop index \\
\hline
\verb"for (int k = 500; k >= 3-2*k; k--)" & 
          \verb"for (int k = 500; k >= 1; k--)" & use simple \\
\verb"   body(k);"   &
          \verb"   body(k);"                   & comparisons \\
\end{tabular}
\end{flushleft}

In order to allow {\tt javar} to re-use the loop bound
expressions in several integer arithmetic operations
(for example, to implement loop normalization),
the following constraints are also imposed on the loop:

\begin{enumerate}
\item[(2)] The initialization expression
{\tt init} and the bound expression {\tt low}
or {\tt high} must be 
\emph{loop-invariant integer\/} expressions.
If used, {\tt stride} must be a positive integer literal.
\end{enumerate}

As illustrated below, loops that do not adhere
to these constraints must be rewritten first:

\begin{flushleft} \scriptsize
\begin{tabular}{l|l|l}
Original Loop & Rewritten Loop & Comments \\
\hline 
 &          \verb"int lw = low++;"               &   \\
\verb"for (int i = low++; i <= up; i++)" &
         \verb"for (int i = lw; i <= up; i++)"  & avoid side effects in \\
\verb"  body(i);"  & \verb"  body(i);"   & initialization expression \\
\hline 
\verb"for (int d = 0.0; d < 11.5; d += 1.0)" & 
         \verb"for (int d = 0; d < 12; d++)"  & use integer  \\
\verb"  body(d);"  & \verb"  body(d);"        & bounds and stride \\
\hline 
\verb"int s = 3;" & 
\verb"int s = 3;" & \\
\verb"for (int i = 100; i > 0; i -= s)" & 
         \verb"for (int i = 100; i > 0; i -= 3)"  & use positive integer  \\
\verb"  body(i);"  & \verb"  body(i);"            & literal as stride \\
\end{tabular}
\end{flushleft}

In this prototype implementation, {\tt javar} conservatively
assumes that field accesses, array element accesses, and method
invocations are not loop invariant. Moreover, {\tt javar}
assumes that a \emph{non-local\/} variable may be changed by
\emph{any\/} method invocation in the loop-body. For example,  below
we present a fragment in which {\tt javar} cannot detect
the trivial loop invariance of the upper bound {\tt N * N}:

\code
\begin{tabular}{l}
\verb"public class Init {" \\
\verb"  int[] a;" \\
\verb"  int   N;" \\
\verb"  public void init() {" \\
\verb"    int[] b;" \\
\verb"    /*par block */" \\
\verb"    for (int k = 0;  k < N * N; k++)" \\
\verb"      b[k] = Math.abs( a[k] );                    // <- line 9" \\
\verb"  }" \\
\verb"}" \\
\verb" " \\
\verb"> javar -op Init.java" \\
\verb"javar :: [line 9, Init.java] parallelization prohibited by potential change of N in Math.abs()" \\
\verb"javar :: no output for Init.java" \\
\end{tabular}
\edoc

This problem is easily resolved, however, by
storing the loop invariant upper bound in 
a local variable `{\tt int b = N * N;}'
and replacing the comparison with `{\tt k < b}',
because {\tt javar} sees that the local variable
cannot be changed during execution of the loop.
Moreover, because {\tt javar} may fail
to determine the type of an initialization or
bound expression,  in some cases a warning
informs the programmer that the parallelization is 
only correct under the assumption that loop bounds are integers.

The  method of~\cite{bikgana} also
imposes the following constraint on parallel loops:

\begin{enumerate}
\item[(3)] The values of all local variables that
are declared \emph{outside\/} the loop, but
referred to \emph{within} the loop-body must remain
unaltered during execution of the loop (thereby \emph{not\/} counting any changes
to elements or fields of array or object references).
\end{enumerate}

Just as an academic example,
{\tt javar} can still apply loop parallelization
to the following {\tt i}-loop because the value  of
{\tt s}, of {\tt a} itself,
and of {\tt o} itself remain unaltered during execution of the loop
(although the loop-carried output dependence on {\tt o.field}
makes it is unlikely that parallelization of this loop is truly desired):

\code
\begin{tabular}{l}
\verb"void method(double s) {" \\
\verb"  SomeObject o = new SomeObject();" \\
\verb"  double[][] a = new double[100][100];" \\
\verb"  /*par*/ " \\
\verb"  for (int i = 0; i < 100; i++)" \\
\verb"    for (int j = 0; j < 100; j++)" \\
\verb"      a[i][j] = s * o.field++;" \\
\verb"}" \\
\end{tabular}
\edoc

Parallelization would be disabled
if a statement like `{\tt s++}', `{\tt a = ...}' or
`{\tt o = ...}' would occur in the loop-body
(note, however, that in such cases there is even less 
likely any parallelism in the loop). 
This constraint is imposed because the parallelization performed by {\tt javar} 
in essence consists of letting a number of threads execute a newly generated
class or instance method for different subsets of iterations.

All dynamically allocated data, class and instance variables, the loop index 
and all variables declared \emph{inside\/} the loop-body
remain visible in this new method. The value
of local data declared outside the loop but referred
to within the loop-body, however, must be explicitly passed
to this new method. Constraints (3) avoid
the requirement to propagate changes of such local variables
back to the main thread.

Finally, to avoid problems in transferring control back
to the initial thread, {\tt javar} imposes
the following constraint on parallel loops
(typically only violated in serial loops anyway): 

\begin{enumerate}
\item[(4)] 
The loop-body does not contain
a {\tt break}-, {\tt continue}-, or {\tt return}-statement.
\end{enumerate}

Loop parallelization can be applied,
however, to loops in which exceptions may be thrown
(either implicitly or explicitly),
although the programmer must list all exceptions
that have to be explicitly transferred back to the thread
that initiated the parallel loop.

In the following fragment, for instance, the programmer has
specified that in the parallel loop,  exception {\tt RuntimeException}
must be explicitly transferred back to the initial thread:

\code
\begin{tabular}{l}
\verb"static void method(int len, int[] a, int[] b) {" \\
\verb"  try {" \\
\verb"    /*par (RuntimeException) */" \\
\verb"    for (int i = 0; i < len; i++)" \\
\verb"      a[i] = 1 / b[i];" \\
\verb"    }" \\
\verb!    catch(RuntimeException e) { System.out.println("a has not been initialized"); }! \\
\verb"}" \\
\end{tabular}
\edoc

If an exception that is not assignable~\cite{javalang}
to any of the exceptions listed in the loop
annotation may be thrown during parallel execution of a loop,
then (i) in case of a \emph{checked\/} exception,
the transformed program is \emph{not\/} valid Java
because {\tt javar} did not add
a {\tt throws} declaration  to the method
used to execute different iterations of the
loop in parallel, or (ii) in case of an \emph{unchecked\/} exception,
one of the threads may invoke the
method {\tt uncaughtException()} at run-time.
Likewise, if a \emph{checked\/} exception that is not explicitly handled
in the context of the parallel loop is listed, the
transformed program is also not valid Java.
For all exceptions that are explicitly transferred back
to the initial thread, the programmer must be aware  that  
because the order in which iterations
of a parallel loop are executed  is completely unpredictable,
\emph{no\/} assumptions about which iterations have or have not been executed 
successfully can be made in any subsequent explicit exception handling.

\subsubsection{Parallel Code Generation}
Eventually, if the flags `{\tt -op}' are given
and all parallel loops  satisfy the constraints given
in the previous section, {\tt javar} generates a Java program
in which parallelism is made explicit using multi-threading. 
This new program requires the package
`{\tt parlooppack}'  (supplied
in the {\tt EXAMPLES} directory). Make sure that this
package, containing some auxiliary classes
that support the parallel execution of loops,
is accessible during compilation and
execution of the new parallel program
(see~\cite{bikgana} for a detailed presentation
of this package).

\section{Parallel Multi-way Recursive Methods}
The prototype {\tt javar} also provides
some elementary support to exploit parallelism
in so-called parallel multi-way recursive methods.
We refer to a \emph{non}-private, \emph{un}-synchronized, and
\emph{final\/} method (i.e. overriding or hiding is not possible)
of the following form, where the different recursive method invocations
in between executing  {\tt pre\_code} and {\tt post\_code}
can be done in parallel as a {\bf parallel multi-way recursive method}:

\code
\begin{tabular}{l}
\verb"class MyClass {" \\
\verb"  ..." \\
\verb"  [qualifiers] type myMethod(type1 f1, ..., typek fk) {" \\
\verb"     if (cond)" \\
\verb"       ... alt_code ..." \\
\verb"     else {" \\
\verb"       ... pre_code ..." \\
\verb"       /*par_inv*/ " \\
\verb"       {" \\
\verb"         r1 = target1.myMethod(a11, ..., a1k)" \\
\verb"         ..." \\
\verb"         rn = targetn.myMethod(an1, ..., ank)" \\
\verb"        }" \\
\verb"       ... post_code ..." \\
\verb"     }" \\
\verb"  }" \\
\verb"}" \\
\end{tabular}
\edoc

Each {\tt targeti} either denotes (implicitly) `{\tt MyClass}'
if {\tt myMethod()} is a class method,
or otherwise an arbitrary variable of type {\tt MyClass},
including (an implicit) {\tt this}. If {\tt myMethod()} 
is a {\tt void}-method,  there are no assignments to the
different  {\tt ri}.  As illustrated above,
the sequence of self-invocations that may be done in parallel 
is identified using the method annotation  `{\tt /*par\_inv*/}'
before a block that contains these self-invocations.

\subsection{Method Annotations}
A comma-separated list of the following constructs
can be optionally used in  between the `{\tt /*par\_inv}'  and the
`{\tt */}' of a method annotation:

\begin{itemize}
\item `{\tt cut\_depth = <int>}' : 
	Defines the depth in the method invocation tree
	until which new threads must be forked
	to execute self-invocations in parallel
        (e.g. `{\tt /*par cut\_depth = 2 */}').
	The default value is 1.
\item one of `{\tt no\_serial\_copy}' or `{\tt serial\_copy}' :
Defines whether after the cut-depth,
a method with some overhead may be used
for executing the remaining invocations in a serial
fashion (the default), or whether this overhead
must be avoided 
at the expense of some code duplication
by executing a copy of the original
method at this stage.
\item `{\tt ( <name> )}' :  
Enforces the generation of a parallel method that 
catches any exception assignable to the specified exception that 
is thrown in one of the threads of the method, and
 explicitly re-throws this exception 
 in the thread that initiated the parallel method.
\end{itemize}

Several sequences of parallel self-invocations may be
defined in one method (although only the optional constructs
of the lexically first sequence are used during code
generation).  Parallel loops that appear within
parallel methods and vice versa are simply ignored.

\subsection{Actual Method Parallelization}
As for loops, it is \emph{the responsibility
of the programmer\/} to identify parallel methods.
The prototype uses the method described in~\cite{bikgana}
to make this method parallelism explicit by means of
multi-threading without ascertaining whether the parallelization
is actually valid. Currently, code is generated that
uses a simple static allocation scheme to assign parallel method
invocations to threads (some initial experimentation with dynamic
allocation schemes failed due to the overhead of passing work to other threads).

In this release of {\tt javar}, only straight-line code
consisting of self-invocations, possibly assigning
to \emph{simple\/} variables in case of a method with a result,
may occur in the sequence of parallel self-invocations, as is
illustrated below:

\code
\begin{tabular}{l}
{\tt void}-method: \\
\verb" " \\
\verb"/*par_inv cut_depth=2*/" \\
\verb"{" \\
\verb"  myMethod(a11, ..., a1k);" \\
\verb"  myMethod(a21, ..., a2k);" \\
\verb"}" \\
\end{tabular}
\verb"                   "   
\begin{tabular}{l}
method with result: \\
\verb" " \\
\verb"/*par_inv cut_depth=2*/" \\
\verb"{" \\
\verb"  r1 = myMethod(a11, ..., a1k);" \\
\verb"  r2 = myMethod(a21, ..., a2k);" \\
\verb"}" \\
\end{tabular}
\edoc

Furthermore, the type of each actual argument {\tt aij} must
be equal to the type {\tt typej} of the formal argument {\tt fj} of
{\tt myMethod()} (because {\tt javar} does currently not account for method
invocation conversion~\cite[ch5]{javalang}, explicit casting
may be required to obtain a valid sequence).

\section{HTML Representation}
If the `{\tt -w}' option is given, 
an HTML representation of all compilation
units that are supplied to the {\tt javar} command is generated.
This HTML representation (with root file `{\tt index.html}')
is placed in the directory defined by the environment variable 
{\tt JAVAR\_HTML} (or the current directory by default).

Constructing an HTML representation in {\tt /tmp}
for all Java compilation
units that appear in the current directory and all its sub-directories,
for instance, can be done in UNIX as follows:

\code
\begin{tabular}{l}
\verb"setenv JAVAR_HTML /tmp" \\
\verb:javar -w `find . -type f -name "*.java" -print`:  \\
\end{tabular}
\edoc

An HTML representation that is organized
into packages is constructed for 
the source code of all these compilation units,
together with an HTML representation
of a list of all classes
and methods (with signatures) that allows
for easy access into the source code representation.

\section{Concluding Remarks}
We would like to stress that this prototype version of
{\tt javar} does \emph{not\/} provide a full front-end
for the Java programming language 
(unicode escapes are not supported and
only a limited semantic  analysis of the program
is performed).  Therefore, we suggest that applying 
{\tt javar} to a program is postponed until after a program has been 
thoroughly tested using a full Java compiler
(on the other hand, because {\tt javar} usually runs faster
than the interpreted execution of {\tt javac}, our prototype 
 can be used as a rapid syntax and 
limited semantic checker during initial editing of a program).
Moreover, the prototype  cannot detect implicit parallelism
 automatically by means of data dependence
analysis. Instead it relies completely on the identification
of `implicit' parallelism by means of annotations.
Finally, although very unlikely, 
due to the local character of the transformations, 
conflicts between new identifiers and  other identifiers 
that have to be resolved by the programmer could arise.

Despite the shortcomings of the prototype, 
however, we hope that this research
tool provides sufficient functionality to 
make  the parallelization of Java programs
less complex and less error-prone. 
The results of some initial experiments with {\tt javar}
are reported in~\cite{bikgana}

New releases  of our prototype Java restructuring compiler {\tt javar}
(and a prototype bytecode parallelization tool {\tt javab})
will be made available at the HP-Java page at the Indiana University
(\verb"http://www.extreme.indiana.edu/hpjava/").
Please send all your comments, bug reports, experiences,
and suggestions to: {\tt ajcbik@extreme.indiana.edu}

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

\end{document}

