From eddemain@daisy.uwaterloo.ca Sat Mar 28 11:09 EST 1998
Received: from daisy.uwaterloo.ca (eddemain@daisy.uwaterloo.ca [129.97.140.58]) by postoffice.npac.syr.edu (8.7.5/8.7.1) with ESMTP id LAA05788 for <kea@npac.syr.edu>; Sat, 28 Mar 1998 11:09:40 -0500 (EST)
Received: (from eddemain@localhost)
	by daisy.uwaterloo.ca (8.8.8/8.8.8) id LAA03805
	for kea@npac.syr.edu; Sat, 28 Mar 1998 11:09:40 -0500 (EST)
From: Erik Demaine <eddemain@daisy.uwaterloo.ca>
Message-Id: <199803281609.LAA03805@daisy.uwaterloo.ca>
Subject: Java special issue for CPE (LaTeX)
To: kea@npac.syr.edu
Date: Sat, 28 Mar 1998 11:09:40 -0500 (EST)
X-Mailer: ELM [version 2.4 PL25]
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII
Content-Length: 44126
Status: R

Please find enclosed the LaTeX source for the text of my paper, for submission
to the Java special issue of Concurrency: Practice and Experience.

You should have already received the PostScript.


Contact author information:

        Erik Demaine
        Department of Computer Science
        University of Waterloo
        Waterloo, Ontario N2L 3G1  CANADA
        tel: 519-725-5939
        fax: 519-885-1208

Erik
-- 
Erik Demaine              \(  e-mail: eddemain@daisy.uwaterloo.ca (PGP avail.)
Dept. of Computer Science  \) URL: http://daisy.uwaterloo.ca/~eddemain/
University of Waterloo     (\  "I don't know why; it seems to be harder to lie
Waterloo, ON Canada N2L 3G1 )\  to other people than yourself." -Neil Robertson
---------------------------------- CUT HERE ----------------------------------
\documentclass [11pt] {article}

% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

% C mode
\newcommand{\code}[1]{{\tt #1}}
\newenvironment{Ccode}{\vtop\bgroup \noindent \footnotesize \tt
    \hsize=0pt \Cindentcnt=0 \Cdelaycnt=0
    \setbox7=\hbox \bgroup \ignorespaces}
    {\Cendline \egroup}
\newcount\Cindentcnt
\newcount\Cdelaycnt
\newcount\Ctemp
\def\Ciskip{16pt}
\def\Ci{\hbox{\hskip \Ciskip}}
\def\Cindent{%\the\Ctemp
\ifnum \Ctemp>0 \global\advance\Ctemp by -1 \Ci \Cindent \fi}
\def\Cendline{\egroup \ifnum \wd7 > \hsize \hsize=\wd7 \fi \box7}
\def\Cnewline{\Cendline \vskip 0pt \setbox7=\hbox \bgroup
    \Ctemp=\Cindentcnt \Cindent}
\def\Clbrace{\{ \global\advance\Cindentcnt by 1 \Cnewline}
\def\Crbrace{\global\advance\Cindentcnt by -1 \hskip -\Ciskip \} \Cnewline}
\def\Capplydelay{\global\advance\Cindentcnt by \Cdelaycnt  \global\Cdelaycnt=0}
\def\Csemi{; \Capplydelay \Cnewline}
\def\Ccont{\global\advance\Cindentcnt by 1 \global\advance\Cdelaycnt by -1
    \Cnewline}

% Typesetting concerns
\let\latexcite=\cite
\def\cite{\nolinebreak\latexcite}
\let\latexref=\ref
\def\ref{\nolinebreak\latexref}

% Figures and tables
\newcommand{\halfup}[1]{\raisebox{1.5ex}[0pt]{#1}}
\newcommand{\centervbox}[1]{%
    \hbox {%
        \setbox0=\hbox{#1}%
        \dimen0=0.5\dp0
        \advance\dimen0 by -0.5\ht0
        %\setbox1=\hbox{\raise \dimen0 \copy0}
        %\wlog{was \the\ht0 , \the\dp0}
        %\wlog{now \the\ht1 , \the\dp1}
        \raise \dimen0 \box0
    }%
}
\newcommand{\topvbox}[1]{%
    \hbox {%
        \setbox0=\vbox{#1}%
        \lower \ht0 \box0
    }%
}
\newcommand{\doublefig}[4]{\hbox to \hsize {#1 #2 #3 #4 #1}}
\newcommand{\doublelabelfig}[6]{%
    \hbox to \hsize {%
        #1%
        \setbox0=\hbox{#2}%
        \setbox1=\hbox{#5}%
        \ifnum \dp0 > \dp1
            \dimen0=\dp0
        \else
            \dimen0=\dp1
        \fi
        \dp0=\dimen0
        \dp1=\dimen0
        \labeledfig{\box0}{#3}%
        #4%
        \labeledfig{\box1}{#6}%
        #1%
    }%
}
\newcommand{\labeledfig}[2]{%
    \vtop {%
        \setbox0=\hbox{#1}
        \setbox1=\hbox{#2}
        \hsize=\wd0
        \copy0
        \hbox {%
            \hskip 0.5\wd0
            \hskip -0.5\wd1
            \box1
        }
    }
}

% Misc. for this document
\newenvironment{cc2java}
    {\hbox to \hsize \bgroup \hfill \begin{c2java}}
    {\end{c2java} \hfill \egroup}
\newenvironment{c2java}{%\vtop\bgroup
     \footnotesize \tt \def\To{& $\mapsto$ &} %\let\And=\\
     \begin{tabular}{lll} \textrm{\normalsize C} & & \textrm{\normalsize Java}
     \\ \cline{1--1} \cline{3--3}}
    {\hline \end{tabular}}%\egroup}

\title {C to Java: Converting Pointers into References}
\author {Erik D. Demaine \\
         Department of Computer Science \\
         University of Waterloo \\
         Waterloo, Ontario N2L 3G1, Canada \\
         eddemaine@uwaterloo.ca}
\date {}

\begin{document}
\maketitle

\begin{abstract}
We consider the problem of converting C pointers to the less flexible concept
of references.  Our main application is converting scientific applications from
C to Java.  We provide a general method to model essentially all features of
pointers using references.  The model is easily implemented in Java.  We give
optimizations that map key facilities like arrays and structures onto the
obvious Java equivalents, arrays and objects.  These improvements make the
conversion ``optimal'' for all typed pointers.  For untyped pointers, we can
still fall back on the general model, hence providing general automatic
conversion from C to Java code, whose efficiency improves with the quality of
the C code.
\end{abstract}

\section {Introduction}

The C language is well known for its overly flexible pointers.  A pointer may
represent the address of an individual value, an array, a structure, or a
position in an array or structure.  Pointers can be cast into other pointer
types or integers, split into pieces and later rejoined, and can take part in
arithmetic operations.  While this gives the programmer immense flexibility,
most of these abilities are considered unnecessary, and when used are
dangerous and lead to code that is difficult to debug.

For this reason, many modern languages such as Java support a much more
restricted model called \emph{references}.  The programmer has limited access
to the references themselves; typically, one can only assign to a reference
andtest whether two references point to the same object.  Other uses of a
reference are implicitly about the object it refers to; usually, the programmer
does not explicitly dereference or take the address of an object.  This leads
to significantly safer and simpler code.

Since C is popular, there is a lot of code written in it.  Many want to extend
such programs and exploit features of more modern programming languages.  For
example, one may want to port an application to Java for demonstration on the
World Wide Web.  Since C and Java are similar in syntax, the main difficulty in
converting between the two is the conversion between major concepts, in
particular pointers and references.

In this paper, we discuss automatic conversion of pointers into references,
with the application of converting C code into Java.  Our main focus is on
translating scientific applications written in C.  A significant example of
such a program is SuperLU \cite{Demmel97, SuperLUug}, a state-of-the-art
general sparse linear solver released in 1997 and available only in C.

The rest of this paper is outlined as follows.  Section \ref{RelatedWork}
surveys related work.  In Section \ref{BlockModel}, we give a general and
flexible conversion model that provides nearly full conversion from C to Java.
Section \ref{Improved} discusses how this can be improved to be ``optimal'' for
most applications.  We conclude in Section \ref{Conclusion}.

\section {Related Work}
\label{RelatedWork}

Much work has been done on converting Java to C for optimization purposes; see
for example Harissa \cite{Muller97}, j2c \cite{j2c}, JCC \cite{JCC}, and Toba
\cite{Toba}.  However, little has been done on the reverse direction.  Of
particular relevance are c2j \cite{Laffra96} and c2j++ \cite{c2j++}.  Both are
tools for translating C++ to Java.  c2j++ is based on c2j; the main difference
is that c2j++ is written in Java, whereas c2j is written in C++.

Unfortunately, the tools are limited.  They essentially ignore the problem of
pointers, which is the main difficulty of C-to-Java conversion.  For example,
they simply remove all pointer dereferences, that is, remove asterisks and
convert ``\code{->}'' to ``\code{.}''.  This is often correct when dealing with
objects and pointers to objects, but (for example) never works for arrays.  For
scientific applications, arrays are perhaps the most important and common data
structure, so their conversion is important.  Indeed, we pay much attention to
their efficient representation in Java in this paper.

Another related project is a recent Fortran-to-Java converter f2j \cite{Fox97}.
It is of interest because it uses an intermediate representation of C, that is,
it converts Fortran code into C, and converts the result to Java.  However,
this was done purely for convenience (since a Fortran-to-C converter was
already available), and does not support general C to Java conversion; in
particular, pointers are completely avoided.  In comparison to our work, it
also implements facilities for call-by-reference and multi-dimensional arrays,
but the methods they use do not work in general (for both Fortran and C).

A couple of minor results in this paper have been partially achieved before.
%
Section \ref{CBR} discusses possible methods for passing basic values such as
integers to functions by reference in Java.  We know of one system supporting
this, EPP \cite{Ichisugi97}.  EPP is a framework for Java preprocessors and one
example, called ref \cite{EPPref}, adds an operator ``\code{\&}'' for passing
values by reference.  It implements this using one-element arrays, but in such
a way that does not allow taking general addresses of basic values, unlike our
methods in Section \ref{CBR}.

Section \ref{CBR} also gives the results from a benchmark we wrote, comparing
the various options for call-by-reference in Java.  A related
``microbenchmark'' has been developed by Griswold and Phillips \cite{JavaProf}.

\section {Block Model}
\label{BlockModel}

This section defines what we call the \emph{block model} of pointers.  It
allows us to abstract essentially all features of C pointers into a simple
theoretical framework.  The few limitations are discussed in Section
\ref{Limitations}.

At any time in the model, the memory consists of a collection of independent
``top-level'' blocks.  Blocks can be dynamically created.  Each block consists
of a basic C value (character, integer, or floating-point value of some size),
a pointer, or a structure containing several sub-blocks.  A particular kind of
structure of interest is the array, where each sub-block has the same type.
Pointers can either be the special value \code{null} or refer to a (not
necessarily top-level) block.

Let us introduce some notation for this model.  We write $*p$ to denote the
block pointed to by $p$.  Note that $p$ is also a block, since pointers are
stored in blocks, and we associate blocks with their values.  Hence, we can
construct pointers to pointers, and so on.  We write $b = (b_1, \dots, b_n)$
when $b$ is a structure block with sub-blocks $b_1, \dots, b_n$.

We can now consider how pointers in such a model can be mapped onto references.

\subsection {Pointer Comparison and Arithmetic}

Suppose we want to determine whether $p \leq q$ for two pointers $p$ and $q$.
More generally, we will define the relation $\&b \leq \&c$, where $\&b$ denotes
the \emph{address} of a block $b$.  This makes sense if $b$ and $c$ are in the
same top-level block.  The ordering of addresses is defined by the following
two properties.  (As is common, $a < b$ means $a \leq b$ and $b \not\leq a$.)

    \begin{enumerate}
    \item If $b = (b_1, \dots, b_n)$, then $\&b_1 = \&b$ and
        $\&b_i < \&b_{i+1}$ for all $1 \leq i < n$.
    \item The relation $\leq$ is transitive; that is, if $\&b_1 \leq \&b_2$ and
        $\&b_2 \leq \&b_3$ then $\&b_1 \leq \&b_3$.
    \end{enumerate}

If we want to define $\leq$ over all addresses, we could assign some order to
the top-level blocks.  For example, we could define that $\&b < \&c$ for two
top-level blocks $b$ and $c$ if $b$ was created before $c$.

Note that this ordering of addresses also makes it easy to add integers to
pointers.  Basically, adding $n$ to a pointer $p$ involves finding the
$n^\mathrm{th}$ successor of $p$.  However, we must take into account that each
time we find the successor, we skip over a block of arbitrary size, whereas we
want to skip over a particular number of bytes ($n$ times the size of $p$'s
type).  Similarly, we can define the difference of two pointers
$p$ and $q$; it is simply the $n$ such that $p=q+n$.  In general, we can
support pointer arithmetic.

\subsection {Stack}

The block model only models heaps.  What about variables allocated on the
stack?  One possibility is to model each stack element as a heap allocation.
In fact, while this adds extra overhead, it is the most efficient general
method.  This is because, while Java has a stack, it does not support taking
the address of anything on the stack \cite{Gosling96}.  Objects cannot be
allocated on the stack (unlike C++ for example); only references to objects can
be allocated on the stack.  One cannot pass basic values by reference or
otherwise find their addresses.  Hence, all objects whose addresses are used at
some point, which is all that our model is supposed to cover, must indeed be on
the heap in Java.  That is, if we encounter a stack object in the C source
whose address is used, we must convert it into a heap allocation if we plan on
converting to Java.

\subsection {Implementation in Java}
\label{BlockModelInJava}

The block model is easy to implement in Java.  We make an abstract class
\code{Block}, which includes an entry \code{parent} of type \code{StructB}.
\code{StructB} is a final class extending \code{Block}, consisting of an array
of children.  There are several other final classes extending \code{Block}.
For example, \code{IntB} represents a block consisting of a single integer
\code{val}, and \code{PointerB} represents a block pointing to some other block
\code{target}.  One can then define how to compare two pointers, increment a
pointer, and in general do arithmetic on pointers, as we have described.  An
example of the conversion process is given in Figure \ref{BlockEx}.

\begin{figure}[ht]
\doublelabelfig{\hfill}{%
    \begin{Ccode}
    main () \Clbrace
        int a[4] = \{1,2,3,0\}\Csemi
        printf ("\%d$\backslash$n", sum (a))\Csemi
    \Crbrace
    int sum (int *a) \Clbrace
        int s = 0\Csemi
        while (*a != 0) \Ccont
            s += *(a++)\Csemi
        return s\Csemi
    \Crbrace
    \end{Ccode}%
}{(a)}{\hfill}{%
    \begin{Ccode}
    main () \Clbrace
        IntB[] a\_ = \{new IntB (1), new IntB (2), \Ccont
            new IntB (3), new IntB (0)\}\Csemi
        StructB a = new StructB (a\_)\Csemi
        System.out.println (sum (new PointerB (a)))\Csemi
    \Crbrace
    int sum (PointerB a) \Clbrace
        int s = 0\Csemi
        while (((IntB) a.target).val != 0) \Clbrace
            s += ((IntB) a.target).val\Csemi
            a.increment ()\Csemi
        \Crbrace
        return s\Csemi
    \Crbrace
    \end{Ccode}%
}{(b)}
\caption {\em \label{BlockEx}
    Example of block model.  (a) Input C code.  (b) Resulting Java code.}
\end{figure}

This implementation has a limitation with dynamic allocation: we must know the
type of block at the time of creation.  This can be difficult with calls to the
C \code{malloc} function, since only a number of bytes is passed in.
Fortunately, most dynamic allocations are of the form \code{malloc (n * sizeof
(type))}, which indicates that we should allocate a structure block with
\code{n} entries of the specified type.  In other words, we can modify the
definition of \code{sizeof} to indicate type information.  Most of the time,
this will be sufficient.

However, in C one could call \code{malloc (n1 * sizeof (type1) + n2 * sizeof
(type2))}.  This suggests a structure block with
$\code{n1}+\code{n2}$ elements, but it does not indicate the relative order of
\code{type1} and \code{type2} elements; they may be interspersed arbitrarily.
To solve this case, we can create an \emph{unknown block}, that is, an object
of type \code{UnknownB}.  Such a block stores its size in bytes and a
\code{Block[]} array of that size.  Initially all elements of the array are
\code{null}, and as sections of the allocated space get used, the corresponding
blocks get created.

This allows dynamic determination of sub-block types.  It induces some overhead
since we must check whether an array entry is \code{null} before using it, and
if it is, we must create the block first.  However, most dynamic allocations
declare the type ahead of time, so we should rarely have to use this mechanism.

\subsection{Extensions}

\label{Limitations}
The block model illustrates that we can automatically convert essentially any C
code into Java.  It supports almost all ``safe'' C code, modelling basic C
types, pointers, and structures.  Pointers are untyped, so they can be cast in
the code as desired (including support for the \code{void *} type).  However,
the block model does not support union types or casting between integers and
pointers.  In general, such features represent extremely unwieldy type mangling
that is fortunately uncommon in ``well-written'' code.  Hence, the lack of such
support is usually of limited importance.

However, there are several possible modifications to the block model that
support more C features.  For example, the most common form of union types,
where only one entry is valid at any time, can be represented by an unknown
block with one entry.  Before accessing it, we check whether the entry is of
the correct type, and if not replace it with a newly created block.

Another possibility, which fully supports C pointers including casting between
integers, is to store all addressable memory in an \code{Object[]} array.  Then
a pointer is simply an index into this array, measured in bytes.  As a result,
we can trivially convert between pointers and integers, perform pointer
arithmetic and comparison, etc.  The main difficulty with this approach is
supporting dynamic allocation of blocks with unknown types; if supported, we
must check whether the array entry is \code{null} before every access to
addressable memory.  In constrast, the block model only had to do this for the
blocks that had unknown types at creation time.

In conclusion, there are several possible strategies for general conversion,
each with varying levels of flexibility and efficiency.  Indeed, there are
probably several approaches yet to be discovered, and the most appropriate
model likely depends on the application.  In the next section, we will see how
to achieve extremely efficient conversion for the most common uses of pointers
in scientific applications, such as arrays.

\section {Improved Conversion}
\label{Improved}

The block model is extremely general, but the code it generates can be much
more complicated than required.  In particular, it can be much slower than the
original C.

For example, consider the conversion in Figure \ref{BlockEx}.  The main problem
with the resulting Java code is that it does not exploit Java's existing
facilities for arrays.  It creates several objects to duplicate the heap,
representing it at the user level, for pointer-manipulation purposes.  The
reason for this is that the converter does not know, when converting
\code{sum}'s code, that \code{a} is an array.  If it knew, it could perform the
conversion in Figure \ref{ImprovedEx}.

\begin{figure}[ht]
\doublelabelfig{\hfill}{%
    \begin{Ccode}
    main () \Clbrace
        int a[4] = \{1,2,3,0\}\Csemi
        printf ("\%d$\backslash$n", sum (a))\Csemi
    \Crbrace
    int sum (int *a) \Clbrace
        int s = 0\Csemi
        while (*a != 0) \Ccont
            s += *(a++)\Csemi
        return s\Csemi
    \Crbrace
    \end{Ccode}%
}{(a)}{\hfill}{%
    \begin{Ccode}
    main () \Clbrace
        int[] a = \{1,2,3,0\}\Csemi
        System.out.println (sum (a))\Csemi
    \Crbrace
    int sum (int[] a) \Clbrace
        int a\_i = 0\Csemi
        int s = 0\Csemi
        while (a[a\_i] != 0) \Ccont
            s += a[a\_i++]\Csemi
        return s\Csemi
    \Crbrace
    \end{Ccode}%
}{(b)}
\caption {\em \label{ImprovedEx}
    Example of the improved conversion.  (a) Input C code.
    (b) Resulting Java code.}
\end{figure}

We can not expect much better code than this; it is simple and efficient.  The
goal of this section is to generate such a perfect mapping of C facilities onto
Java features.  Indeed, the methods of this section will perform the optimal
conversion above.

\subsection {Call-By-Reference} % block = one thing; can use array or object.
% Really either section ``Arrays'' or section ``Structures'' but need it as
% a starting point for these sections.
% For single-threaded programs, can pull additional tricks.
\label{CBR}

Passing values by reference is perhaps the most fundamental use of C pointers.
In Java, values are passed by reference if and only if they are objects or
arrays.  The first question we must ask, then, is how to pass \emph{basic}
variables (that is, variables of basic type such as integer) by reference in
Java.  Let us call a variable \emph{addressable} if its address is taken at
some point in the C source.  Otherwise, we do not need to worry about the
variable.

The most obvious method is to replace all addressable basic variables with
objects that simply contain an entry of that type (Figure \ref{CBRviaObject}).
When such a variable is declared, it must be created using the \code{new}
operator.  If we wish to use or modify the value of the variable, we use or
modify the entry in the corresponding object.  The address of the variable is
simply the corresponding object.

\begin{figure}[ht]
\doublefig{\hfill}{%
    \centervbox {%
        \begin{Ccode}
        public final class Int \Clbrace
            public Int (int val) \Clbrace
                this.val = val\Csemi
            \Crbrace
            public int val\Csemi
        \Crbrace
        \end{Ccode}%
    }%
}{\hfill}{%
\centervbox{%
    \begin{c2java}
    int var;          \To Int var = new Int (); \\
    int ivar = 5;     \To Int ivar = new Int (5); \\
    var++;            \To var.val++; \\
    f (\&var);        \To f (var); \\
    int *ptr = \&var; \To Int ptr = var; \\
    (*ptr)++;         \To ptr.val++; \\
    f (ptr);          \To f (ptr); \\
    \end{c2java}%
}%
}
\caption {\em \label{CBRviaObject}
    Call-by-reference using objects.}
\end{figure}

A similar method is to replace addressable basic variables with one-element
arrays (Figure \ref{CBRviaArray}).  Again, their declarations must now include
creations with the \code{new} operator.  Accessing the variable corresponds
to accessing the first element of the array, and the address of the variable is
the array itself.  Indeed, the array method is nearly identical to the object
method, replacing ``\code{Int}'' with ``\code{int[]}.''

\begin{figure}[ht]
\begin{cc2java}
int var;          \To int[] var = new int[1]; \\
int ivar = 5;     \To int[] ivar = \{5\}; \\
var++;            \To var[0]++; \\
f (\&var);        \To f (var); \\
int *ptr = \&var; \To int[] ptr = var; \\
(*ptr)++;         \To ptr[0]++; \\
f (ptr);          \To f (ptr); \\
\end{cc2java}
\caption {\em \label{CBRviaArray}
    Call-by-reference using arrays.}
\end{figure}

Objects and arrays are likely the only general methods for addressing basic
variables.  We could imagine achieving call-by-reference by passing copies of
basic variables, instead of their pointers, and having the new values returned
(e.g., through global variables for single-threaded programs).  However, it
does not seem possible to provide the desired semantics in general; for
example, how could a pointer then be stored in a variable?

An obvious question is which of the two methods is more efficient in current
Java implementations.  To answer this, we ran a simple benchmark to compare the
time for incrementing the first entry of an array versus incrementing the entry
of an object.  We also compared with the time for incrementing a basic integer
variable.  For accurate evaluation, we had to loop over several iterations and
divide the (user CPU) time by the number of iterations.  For correct
evaluation, we subtracted the time to simply run through an empty loop of
the same length.

The results are given in Table \ref{SimpleBench}.  Objects win over arrays most
of the time, so we will likely choose them when possible.  The difference is
small on interpreted JVM's, but is more significant on the JVM with JIT (Just
In Time) compilation.  We likely want to leave the choice as an option to the
conversion process, in case the relative performance differs on other machines.

\begin{table}[ht]
\centerline {
\begin{tabular}{|l|c|r|r|r|} \hline
% These numbers already have the (Nothing) loop cost subtracted off.
Machine and JVM      & Opt. & Integer & \multicolumn{1}{|c|}{Object}
                                      & \multicolumn{1}{|c|}{Array}  \\ \hline
% [[[espresso]]]
% seconds for 10^9 its:       20.6      162.6      225.5
Sun SPARCstation 20  & None & 20.6 ns & 162.6 ns & 225.5 ns \\ \cline{2--5}
% seconds for 10^9 its:       20.3      163.4      232.0
Sun's 1.1.1 with JIT & --O  & 20.3 ns & 163.4 ns & 232.0 ns \\ \hline
% [[[bronte]]]
% seconds for 10^7 its:       2.34      9.22       11.70
IBM RS/6000 25T      & None & 23.4 us &  92.2 us & 117.0 us \\ \cline{2--5}
% seconds for 10^7 its:       2.54      9.12       11.69
IBM's 1.1.1 port     & --O  & 25.4 us &  91.2 us & 116.9 us \\ \hline
% [[[daisy]]]
% seconds for 10^7 its:       2.081     16.938     14.212
DEC Alpha 3000/800S  & None & 20.8 us & 169.4 us & 142.1 us \\ \cline{2--5}
% seconds for 10^7 its:       2.070     16.065     16.449
DEC's 1.0.1 port     & --O  & 20.7 us & 160.7 us & 164.5 us \\ \hline
\end{tabular}
}
\caption {\em \label{SimpleBench}
    Benchmark results comparing the access time for basic integers and
    elements of objects and arrays.  The code was compiled with \code{javac}
    from Sun's JDK.  ``Opt.''\ gives the optimization level.
    Curiously, higher optimization causes worse performance in some cases,
    and this phenomenon is reproducible.}
\end{table}

\subsection {Arrays} % mapping them to arrays - includes call-by-reference.
                     % Can use them when never make a+i or something and put
                     % that somewhere (in variable, passed to function, etc.)

Our main focus is on scientific applications, which mainly use basic numbers
and arrays of numbers.  Hence, these two kinds of values should receive special
attention with regard to optimization.  Basic C numbers are easily converted
into efficient Java.  The concern of this section is to map C arrays onto Java
arrays whenever possible.

One problem is that a C array with entries of type $t$ is really just a pointer
to a block of type $t$.  This makes it unclear when a pointer $p$ in fact
represents an array.  If $*p$ is of basic type such as integer or even a
pointer, we can simply assume that it represents an array, since pointers to
basic values alone can also be represented by arrays.  The other possibility is
when $*p$ is a structure block, which we shall consider in Section
\ref{Structures}.

Hence, we can map the C type $t *$ (pointer to type $t$) to the Java type $J(t
*) = J(t) \mathtt{[\,]}$ (Figure \ref{AllArray}).  Any addressable variable
\code{v} of type $t$ must also be mapped to this type, and references to
\code{v} are replaced by \code{v[0]}, which the \code{\&} operator converts
back to \code{v}.

\begin{figure}[ht]
\begin{cc2java}
int a[5];       \To int[] a = new int[5]; \\
%a[2] = 5;       \To a[2] = 5; \\
int *p = a;     \To int[] p = a; \\
p++;            \To \textrm{Not allowed.} \\ \relax
*p = 5;         \To p[0] = 5; \\
p[2] = 10;      \To p[2] = 10; \\
int i;          \To int[] i = new int[1]; \\
i = 5;          \To i[0] = 5; \\
p = \&i;        \To p = i; \\
\end{cc2java}
\caption {\em \label{AllArray}
  Mapping C arrays to Java arrays, requiring addressable basic integers to
  be mapped to arrays.  Pointing to elements of an array is not allowed.}
\end{figure}

\subsection {Indexable Arrays} % arrays + int index
% Important point is ``what is `+'?''
% Most obvious/simplest: encapsulate in object
% ==> if you have array of arrays, obvious what to do
% However, don't need this extra level of indirection, UNLESS returning pointer
%       from function.
% Just have an array and an index lieing around; can pass as two args, or store
%       in two variables, etc.
% Show what to do for array of arrays: int[][], int[], and int

While Java arrays $J(t) \mathtt{[\,]}$ adequately represent pointers to basic
variables and pointers to arrays, they do not fully represent the C type $t *$.
This is because Java arrays are not \emph{translatable}.  That is, we cannot
make an array that refers to a subsection of an existing array.  In contrast, C
allows one to add an integer (such as 1) to a pointer that points to an array,
causing it to point to a particular element of the array.
Such practice is common (for example, in SuperLU \cite{Demmel97,SuperLUug}),
since in C it allows efficient access to individual elements of arrays; that
is, repeatedly accessing \code{a[i]} is made faster by assigning \code{p =
\&a[i]} (or \code{p = a+i}) and then repeatedly accessing \code{*p}.  We
cannot make such an optimization in Java, but we still want to convert such
code into Java.

Our solution, called \emph{indexable arrays}, is to add an integer index to an
array, together forming the Java notion of a pointer (to a basic type).  That
is, $J(t *) = \{J(t) \mathtt{[\,]}, \mathtt{int}\}$, where the braces denote
some kind of structure.  In general, the structure will be represented by an
object with two entries (Figure \ref{IAviaObject}).  Note that basic variables
have to be mapped to arrays in the rare case when their address is stored in a
pointer that also at some time points to an array.

\begin{figure}[ht]
\doublefig{}{%
    \centervbox {%
        \begin{Ccode}
        public class IntPointer \Clbrace
            public IntPointer (int[] a, int i) \Clbrace
                this.a = a\Csemi
                this.i = t\Csemi
            \Crbrace
            public int[] a\Csemi
            public int i\Csemi
        \Crbrace
        \end{Ccode}%
    }%
}{\hfill}{%
    \centervbox {%
        \begin{c2java}
        int a[5];       \To int[] a = new int [5]; \\
        %a[2] = 5;       \To a[2] = 5; \\
        int *p = a;     \To IntPointer p = \\
                         && \qquad new IntPointer (a, 0); \\
        p++;            \To p.i++; \\ \relax
        *p = 5;         \To p.a[p.i] = 5; \\
        p[2] = 10;      \To p.a[p.i+2] = 10; \\
        int i;          \To int[] i = new int[1]; \\
        i = 5;          \To i[0] = 5; \\
        p = \&i;        \To p.a = i; p.i = 0; \\
        \end{c2java}%
    }%
}
\caption {\em \label{IAviaObject}
  Indexable arrays using objects, requiring some basic integers to be mapped
  to arrays.}
\end{figure}

One possible optimization, called \emph{unrolling}, removes a level of
indirection by replacing the structure with two individual variables (Figure
\ref{UnrolledIA}).  This improves efficiency, except when we return a pointer
into an array from a function, in which case we must temporarily switch to the
object representation.

\begin{figure}[ht]
\begin{cc2java}
int a[5];       \To int[] a = new int[5]; \\
a[2] = 5;       \To a[2] = 5; \\
int *p = a;     \To int[] p = a; \\
                 && int p\_i = 0; \\
p++;            \To p\_i++; \\
\relax
*p = 5;         \To p[p\_i] = 5; \\
p[2] = 10;      \To p[p\_i+2] = 10; \\
int i;          \To int[] i = new int[1]; \\
i = 5;          \To i[0] = 5; \\
p = \&i;        \To p = i; \\
                 && p\_i = 0; \\
f (p);          \To f (p, p\_i); \\
p = g ();       \To IntPointer temp = g (); \\
                 && p = temp.a; \\
                 && p\_i = temp.i; \\
return p;       \To return new IntPointer (p, p\_i); \\
\end{cc2java}
\caption {\em \label{UnrolledIA}
    Unrolled indexable arrays.  Returning indexable arrays from functions
    requires special care.}
\end{figure}

Pointers to particular elements of arrays clearly add extra overhead that we
would like to avoid for normal pointers to beginnings of arrays.  That is, we
do not want to force all pointers to have an extra index variable.  Note that
at conversion time, we can determine whether pointers may at some time point to
a particular element of an array, and hence require the extra variable.
Similarly, we can check if a variable of basic type can be addressed by simply
using objects, which are typically more efficient.  For function arguments we
can make a special optimization, by copying the function for each type of
arguments with which it is called (Figure~\ref{FunctionCopy}).  This allows
effective optimization of the special cases, even if multiple cases are
exploited.  In the worst case, which is rare, function copying results in
quadratic code expansion.

\begin{figure}[ht]
\begin{cc2java}
int i;                  \To Int i; \\
f (\&i);                \To f (i); \\
int a[5];               \To int[] a = new int[5]; \\
f (a);                  \To f (a); \\
int *p = \&a[2];        \To int[] p = a; \\
                         && int p\_i = 2; \\
f (p);                  \To f (p, p\_i); \\
void f (int *i) \{      \To void f (Int i) \{ i.val = 5; \} \\
\Ci *i = 5;              && void f (int[] i) \{ i[0] = 5; \} \\
\}                       && void f (int[] i, int i\_i) \{ i[i\_i] = 5; \} \\
\end{cc2java}
\caption {\em \label{FunctionCopy}
    Copying functions to optimize for special cases.  We make three copies of
    \code{f} because of the three different types of calls to \code{f}.  Note
    the use of Java's function overloading.}
\end{figure}

\subsection {Multi-dimensional Arrays}

Multi-dimensional C arrays are in fact one-dimensional arrays with syntactic
sugar for accessing elements.  For example, if we declare \code{int a[3][4]},
then both \code{a} and \code{a[2]} have types corresponding to \code{int *}.
In contrast, Java's multi-dimensional arrays have depth.  For example,
\code{int[][] a = new int[4][]} declares \code{a} as a four-element array of
references to arrays; each entry of \code{a} is initially \code{null}.
Hence, multi-dimensional C arrays must be converted to one-dimensional Java
arrays (Figure \ref{MultiDimArrays}).

\begin{figure}[ht]
\begin{cc2java}
int a[3][4];            \To int[] a = new int[3*4]; \\
int b[3][4] = \{\{1,2\},\{3\},\{4,5,6,7\}\};
                        \To int[] b = \{1,2,0,0,3,0,0,0,4,5,6,7\}; \\
a[1][2] = b[2][1];      \To a[1*4+2] = b[2*4+1]; \\
int *p = a;             \To int[] p = a; \\
int *q = b[2];          \To int[] q = b; \\
                         && int q\_i = 2*4; \\
                                       %\halfup{\quad OR \quad
                                       %IntArray q = new IntArray (b, 2*4);} \\
\end{cc2java}
\caption {\em \label{MultiDimArrays}
    Converting multi-dimensional C arrays to one-dimensional Java arrays.}
    %The last conversion depends on whether we unfold.}
\end{figure}

\subsection {Structures} % mapping them to objects - also includes call-by-ref.
\label{Structures}
%\subsection {Indexable Structures} % make members indexable: reasonable
%                                   % (usually only a few entries).
% If you turn them into objects or arrays anyway, don't need extra level of
%       indirection caused by outermost object--can unroll(fold).
% Note though: since each entry is very different, only some may need to be
%       made indexable (i.e., only index to certain entries--look at code to
%       determine which, of course).
% Example: indexable array of non-indexable structures.  Have array for first
%       element of structure, array for second element, etc.
% If array is size one, you've indirected each element; don't have to (for
%       non-indexable structure), might as well just use an Object for that.

C structures quite obviously map to Java objects (Figure
\ref{StructviaObject}(a)).  Any elements of a structure are converted as if
they represented variables.  For example, in Figure \ref{StructviaObject}, the
address of entry \code{i} of \code{struct T} is taken; hence, it must be
converted to be addressable, which involves converting the type of entry
\code{i} from \code{int} to \code{Int} (an object with an \code{int} in it).  A
similar transformation would occur if a structure had an indexable array as an
entry, for example.  In addition, we must clone (that is, duplicate) any
structures that are passed by value, since objects can only be passed by
reference in Java.

\begin{figure}[ht]
\doublelabelfig{}{%
  \begin{c2java}
  struct S \{             \To class S implements \\
                           && \ \ \ \ \ \ \ \ Clonable \{ \\
  \Ci char c;              && \Ci char c; \\
  \Ci int i;               && \Ci int i; \\
  \};                      && \} \\
  struct S x;             \To S x = new S (); \\
  f (x);                  \To f (x.clone ()); \\
  struct S *p = \&x;      \To S p = x; \\
  g (p);                  \To g (p); \\
  x.i = 5;                \To x.i = 5;\\
  p->i++;                 \To p.i++; \\
  struct T \{             \To class T \{ \\
  \Ci char c;              && \Ci char c; \\
  \Ci int i;               && \Ci Int i = new Int (); \\
  \};                      && \} \\
  struct T y;             \To T y = new T (); \\
  y.i = 5;                \To y.i.val = 5; \\
  f (\&y.i);              \To f (y.i); \\
  \end{c2java}%
}{(a)}{\hfill}{%
  \begin{c2java}
  struct S \{             \To char x\_c; \\
  \Ci char c;              && int x\_i; \\
  \Ci int i; \\
  \} x; \\
  f (x);                  \To f (x\_c, x\_i); \\
  x.i = 5;                \To x\_i = 5; \\
  x = g ();               \To S temp = g (); \\
                           && x\_c = temp.c; \\
                           && x\_i = temp.i; \\
  struct T \{             \To char y\_c; \\
  \Ci char c;              && Int y\_i; \\
  \Ci int i; \\
  \} y; \\
  y.i = 5;                 && y\_i.val = 5; \\
  f (\&y.i);              \To f (y\_i); \\
  \ \\ \ \\ \ \\
  \end{c2java}%
}{(b)}
\caption {\em \label{StructviaObject}
    Converting C structures to Java objects.  (a) Standard.  (b) Unrolled.}
\end{figure}

As a potential optimization, we can unroll structures that are not addressable
(Figure \ref{StructviaObject}(b)).  This means that we do not have to clone
anything when passing by value.  Of course, we cannot pass an unrolled
structure by reference.  For large structures that are passed between functions
a lot, unrolling may worsen efficiency.  Hence, the user should be able to
specify that certain structures should or should not be unrolled.

\subsection {Untyped Pointers}

For \code{void *} pointers or pointers that are type cast, called
\emph{untyped} pointers, we cannot use the efficient conversion we have
discussed.  Instead, we must resort to the block model of Section
\ref{BlockModelInJava}.  Note that we can detect which pointers must be typed.
If the address of some block $b$ is stored in an untyped pointer, we must
convert the entire top-level block containing $b$ using the block model.  Any
pointers that directly or may indirectly point to such information must also
use the block model.
%, except that presuming the pointer's address is not also
%assigned to a top-level block, it does not need to be mapped to a block; it can
%simply be represented by a \code{Block} object.

Our goal is to use the block model as little as possible.  Indeed,
``well-written'' (in particular scientific) applications should not need it at
all.  Our analysis of SuperLU \cite{Demmel97,SuperLUug}, a good representative
of such applications, indicates that the block model is unnecessary.  In
general, the programmer may want to hand-convert any code that requires the
block model in order to improve efficiency.

\section {Conclusion}
\label{Conclusion}

We have presented a general model for complete and automatic C-to-Java
conversion.  We then considered optimizations to this general conversion, for
the common uses of pointers in scientific applications.  In particular, we can
usually achieve the natural conversions of C arrays into Java arrays and C
structures into Java objects.

The implementation of our models are currently under development.  We are also
working on a converter from C to Fortran 90, which mainly involves the same
problem of converting pointers to references.  In the future, we plan on
extending our work to convert C++ to Java and Fortran 90.

\section* {Acknowledgment}

We thank Alan George and David Taylor for their valuable comments on this
paper.  Alan George also motivated the development of this research.  This work
was supported by the Natural Sciences and Engineering Research Council (NSERC).

%\footnotesize
\let\realbibitem=\bibitem
\def\bibitem{\par \vspace{-1.2ex} \realbibitem}
%\bibliography{proglang,sparse}
%\bibliographystyle{unsrt}

\begin{thebibliography}{10}

\bibitem{Demmel97}
James~W. Demmel, Stanley~C. Eisenstat, John~R. Gilbert, Xiaoye~S. Li, and
  Joseph W.~H. Liu.
\newblock A supernodal approach to sparse partial pivoting.
\newblock Technical Report UCB//CSD-95-883, Computer Science Division, U. C.
  Berkeley, July 1995.
\newblock To appear in \emph{SIAM J. Matrix Analysis and Applications}.

\bibitem{SuperLUug}
James~W. Demmel, John~R. Gilbert, and Xiaoye~S. Li.
\newblock {\em SuperLU Users' Guide}, November 1997.
\newblock World Wide Web. \texttt{http:/\slash www.netlib.org\slash
  scalapack\slash prototype\slash superlu\_ug.ps}.

\bibitem{Muller97}
Gilles Muller, B\'arbara Moura, Fabrice Bellard, and Charles Consel.
\newblock Harissa: A flexible and efficient {J}ava environment mixing bytecode
  and compiled code.
\newblock In {\em Proceedings of the 3rd Conference on Object-Oriented
  Technologies and Systems}, 1997.

\bibitem{j2c}
Yukio Andoh.
\newblock j2c/{C}afe{B}abe.
\newblock World Wide Web. \texttt{http:/\slash www.webcity.co.jp\slash
  info\slash andoh\slash java\slash j2c.html}.

\bibitem{JCC}
Nik Shaylor.
\newblock {JCC} --- {A} {J}ava to {C} converter, May 1997.
\newblock World Wide Web. \texttt{http:/\slash www.geocities.com\slash
  CapeCanaveral\slash Hangar\slash 4040\slash jcc.html}.

\bibitem{Toba}
Todd~A. Proebsting, Gregg Townsend, Patrick Bridges, John~H. Hartman, Tim
  Newsham, and Scott~A. Watterson.
\newblock Toba: A {J}ava-to-{C} translator.
\newblock World Wide Web. \texttt{http:/\slash www.cs.arizona.edu\slash
  sumatra\slash toba}.

\bibitem{Laffra96}
Chris Laffra.
\newblock {C2J} --- {A} {C++} to {J}ava translator.
\newblock In {\em Advanced Java: Idioms, Pitfalls, Styles and Programming
  Tips}, chapter~4. Prentice Hall Computer Books, 1996.

\bibitem{c2j++}
Ilya Tilevich.
\newblock {C2J++}, {C++} to {J}ava translator written in {J}ava, 1997.
\newblock World Wide Web. \texttt{http:/\slash
  pacevm.dac.pace.edu\slash\textasciitilde ny971734\slash c2j.html}.

\bibitem{Fox97}
Geoffrey Fox, Xiaoming Li, Qiang Zheng, and Wu~Zhigang.
\newblock A prototype of {FORTRAN}-to-{Java} converter.
\newblock In {\em Proceedings of the ACM 1997 Workshop on Java for Science and
  Engineering Computation}, Las Vagas, Nevada, June 1997.

\bibitem{Ichisugi97}
Yuuji Ichisugi and Yves Roudier.
\newblock The extensible {J}ava preprocessor kit and a tiny data-parallel
  {J}ava.
\newblock In {\em Proceedings of the 1997 International Scientific Computing in
  Object-Oriented Parallel Environments Conference}, Marina del Rey,
  California, December 1997.
\newblock World Wide Web. \texttt{http:/\slash www.aist.go.jp\slash ETL\slash
  etl\slash bunsan\slash \textasciitilde ichisugi\slash doc\slash
  iscope97.ps.gz}.

\bibitem{EPPref}
Yuuji Ichisugi.
\newblock epplib/ref.lsp.
\newblock In {\em EPP distribution}, 1997.
\newblock World Wide Web. \texttt{http:/\slash www.aist.go.jp\slash ETL\slash
  etl\slash bunsan\slash \textasciitilde ichisugi\slash}.

\bibitem{JavaProf}
William~G. Griswold and Paul Phillips.
\newblock {UCSD} benchmarks for {J}ava.
\newblock World Wide Web. \texttt{http:/\slash
  www-cse.ucsd.edu\slash\textasciitilde wgg\slash JavaProf\slash
  javaprof.html}.

\bibitem{Gosling96}
J.~Gosling, B.~Joy, and G.~Steele.
\newblock {\em The {J}ava Language Specification}.
\newblock Java Series. Sun Microsystems, 1996.

\end{thebibliography}

\end{document}

