\documentclass{slides}
\usepackage{multicol}
\topmargin=-10pt
\textheight=630pt
\raggedright
\parindent=0pt
\thicklines
\hyphenpenalty=500
\begin{document}
\newlength{\ItemSkip} \ItemSkip=0pt
\def\Item{\\[1.2\ItemSkip]\hspace*{0.8em}$\bullet$\hspace{0.6em}}

\setlength{\unitlength}{1ex}
\def\Slide#1{\eject\begin{center}{\large #1}\end{center}\par}

\Slide{A Gcc-based Java Implementation}

{\it Implementing Java as just another language}

{\hskip 1em}

Per Bothner

{\tt <bothner@cygnus.com>}

Cygnus Solutions

\Slide{Usual Java implementation model}

\begin{picture}(40,28)
\put(6,24){\framebox(16,4){{\tt .java}{\small{} (source)}}}
\put(14,24){\vector(0,-1){4}}% from .java to javac
\put(14,18){\oval(12,4)}\put(8,16){\makebox(12,4){\tt javac}}
\put(14,16){\vector(0,-1){4}}% from javac to .class
\put(6,8){\framebox(16,4){{\tt .class}{\small{} (bytecode)}}}
\put(14,16){\vector(0,-1){4}}% from .class to Java VM
\put(24,8){\framebox(16,4){{\tt libjava.so}}}
\put(16,8){\vector(1,-1){4}}% from .class to Java VM
\put(30,8){\vector(-1,-1){4}}% from libjava.so to Java VM
\put(23,2){\oval(12,4)}\put(17,0){\makebox(12,4){\tt Java VM}}
\end{picture}

%{\tt javac} compiles Java source code to
%{\tt .class} files containing {\it byte-codes}.

%A {.class} file is an abstract machine-independent
%encode of a single Java class, including its code.

%{\tt java} interpreter/VM [Virtual Machine] dynamically loads {\tt .class}
%files as needed, and interprets the bytecodes.

%New classes can be dynamically loaded into a running
%Java VM, perhaps by a browser loading {\tt .class}
%files over the Net.

%A {\tt Securitymanager} can be used to control the permissions
%available to dynamically-loaded code.

This is simple, portable, slow.

\Slide{Java using traditional techniques}

%A ``Just-in-Time'' (JIT) compiler has the same interface.
%Classes are stored and transmitted as portable {\tt .class} files.
%However, before the first time a method is executed, its bytecodes
%are translated into native code ``on-the-fly''.  However, the compiled
%code is not saved, and is only available during that particular
%run of the Java VM.

%The advantages of the traditional interpreter or JIT
%are portability and dynamic loading.

Many people are more interested in Java as a better C or
simpler C++.  They are less interested in dynamic loading
or the use of bytecodes for portable distribution.

For them, traditional compilation
techniques might provide faster execution.  Even when
dynamic loading is needed ({\it e.g.} a browser), it
makes sense to pre-compile
the standard libraries (such as {\tt java.lang} and the AWT).

Cygnus is writing a new Java front-end for {\tt gcc}, the
GNU compiler, which already supports C, C++, Fortran77,
Ada, Pascal, Chill, on dozens of architectures.

The run-time environment is based on Kaffe, a free Java VM.

%Why pre-compile isteda of JIT:
%\Item Compiling takes time.  Even a fast JIT will take
%extra start-up time.
%\Item Because JIT has to be fast, it cannot do aggressive optimization,
%so the resulting code will be lot slower.

\Slide{The Big Picture}

\begin{picture}(40,55)
\put(40,52){\oval(8,4)}\put(38,50){\makebox(4,4){??}}
\put(40,50){\vector(-1,-1){3}}% from ?? to .class
\put(-1,50){\framebox(14,4){{\tt .java}{\small{} (source)}}}
\put(13,52){\vector(1,0){5}}% from .java to javac
\put(11,49){\makebox(8,3){{\small\it or}}}
\put(24,52){\oval(12,4)}\put(18,50){\makebox(12,4){\tt javac}}
\put(30,52){\vector(1,-1){5}}% from javac to .class
\put(28,43){\framebox(16,4){{\tt .class}{\small{} (bytecode)}}}
\put(32,43){\vector(-2,-1){6}} % from .class to cc1java
\put(13,50){\vector(1,-1){10}}% from .java to cc1java
\put(11,43){\makebox(8,2){{\small (future)}}}
\put(22,38){\oval(12,4)}\put(16,36){\makebox(12,4){\tt cc1java}}
\put(18,36){\vector(-2,-1){4}}% from cc1java to .s
\put(-1,30){\framebox(16,4){{\tt .s}{\small{} (assembly)}}}
\put(13,30){\vector(2,-1){4}} % from .s to as
\put(22,26){\oval(12,4)}\put(16,24){\makebox(12,4){\tt as}}
\put(18,24){\vector(-2,-1){6}}% from as to .o
\put(-1,17){\framebox(16,4){{\tt .o}{\small{} (object)}}}
\put(32,17){\vector(-2,-1){6}} % from .o to ld
\put(25,17){\framebox(16,4){{\tt libkaffe.so}}}
\put(40,17){\vector(0,-1){17}}% from libkaffe.so to Kaffe VM
\put(13,17){\vector(2,-1){6}}% from libkaffe to ld
\put(22,12){\oval(12,4)}\put(16,10){\makebox(12,4){\tt ld}}
\put(22,10){\vector(-1,-1){10}}% from ld to executable
\put(24,10){\vector(2,-1){6}}% from ld to .so
\put(19,7){\makebox(8,3){{\small\it or}}}
\put(-1,-4){\framebox(16,4){{\small{} (executable)}}}
\put(22,3){\framebox(16,4){{\tt .so}{\small{} (DLL)}}}
\put(37,3){\vector(0,-1){3}}% from .so to Kaffe VM
\put(43,43){\vector(0,-1){43}}% from .class to Kaffe VM
\put(39,-2){\oval(12,4)}\put(32,-4){\makebox(12,4){\tt Kaffe VM}}
\end{picture}

\Slide{What about Just-In-Time Compilers?}

A ``Just-in-Time'' (JIT) compiler translates bytecodes to
native code ``on-the-fly'' {\it inside} the VM.

This maintains the simple user model,\\
(it uses portable bytecodes externally),\\
yet speeds up Java execution substantially.

While bytecodes are great for interchange,\\
pre-compilation is better for heavily used libraries and applications:
\Item JIT imposes a start-up penalty each time the application is run.
%(you need to compile all its classes).
\Item JIT cannot do optimizations that take much time
or memory.
\Item The JIT machinery uses memory that may be costly
in some environments.
\Item Porting an good JIT is a substantial effort.  Gcc
has already been widely ported.

\Slide{Example}

{\raggedcolumns
\begin{multicols}{2}
{\small Java Source:}
{\small
\begin{verbatim}
class Fib {
  static int fib (int i)
  {
    int x0 = 1;
    int x1 = 1;
    while (--i >= 0) {
      int x2 = x0 + x1;
      x0 = x1;
      x1 = x2;
    }
    return x0;
  }
}
\end{verbatim}
}

\vskip 6.6ex

{\small Gcc {\tt -O2} code (Sparc):}

{\tiny
\begin{verbatim}
Fib_fib_0:
        mov 1,%o1
        mov 1,%g3
.LL3:   addcc %o0,-1,%o0
        bneg .LL4
        add %o1,%g3,%g2
        mov %g3,%o1
        b .LL3
        mov %g2,%g3
.LL4:   retl
        mov %o1,%o0
\end{verbatim}
}
{\small (10 instructions)}

{\small Kaffe JIT code:}

{\tiny
\begin{verbatim}
    save  %sp,-136,%sp
    mov  1,%l0
    mov  %l0,%l1
    mov  1,%l0
    mov  %l0,%l2
    st  %i1,[%fp+0x48]
    st  %l1,[%fp-40]
    st  %l2,[%fp-36]
    b  L1
    nop 
L2: ld  [%fp-40],%l3
    mov  %l3,%l4
    ld  [%fp-36],%l5
    mov  %l5,%l6
    addcc  %l4,%l6,%l4
    mov  %l4,%l7
    mov  %l5,%l4
    mov  %l4,%l3
    mov  %l7,%l4
    mov  %l4,%l5
    st  %l3,[%fp-40]
    st  %l5,[%fp-36]
    st  %l7,[%fp-32]
L1: ld  [%fp+0x48],%i0
    addcc  %i0,-1,%i0
    mov  %i0,%i2
    st  %i0,[%fp + 0x48]
    cmp  %i2,0
    bge  L2
    nop 
    ld  [%fp-40],%i3
    mov  %i3,%i4
    mov  %i4,%i0
    ret 
    restore 
\end{verbatim}
}
{\small (35 instructions)}
\end{multicols}
}

\Slide{The Compiler}

{\tt cc1java} is a new language front-end
for {\tt gcc}.  It uses the existing {\tt gcc} framework,
and shares most of its code, including the standard {\tt gcc}
optimizer and code generator.

{\tt cc1java} reads bytecodes ({\tt .class} files) and produces
assembly code.

A future version of {\tt cc1java} will be able to read either
Java source or bytecodes.  For now, we use Sun's {\tt javac}
to create bytecodes.

\Slide{Transforming bytecodes}

Bytecode abstract instructions manipulate untyped local variable
slots and stack slots.

Data-flow analysis recovers for a given PC the SP
and type in each slot.
%(The Java bytecode verifier does something similar.)

For each slot and low-level type we associate
a {\tt gcc} virtual register.

Example:  ``{\tt iadd}'' adds two {\tt int}s on top of the stack.

If (stack-slot 0, {\tt int}) is in virtual register 50;
(stack-slot 1, {\tt int}) is in virtual register 51;
and SP is 2; then the generated code is:

\begin{verbatim}
vreg50 := vreg50 + vreg51
\end{verbatim}

Register allocation assigns virtual registers to
hardware registers or stack frame slots.
The Java stack operations are compiled away.

\Slide{Bytecodes to abstract tree nodes}

A refinement is to only allocate virtual registers
{\it between} basic blocks.\\
Within a basic block, we maintain a ``local'' stack of {\tt tree}
(abstract syntax) nodes.

Thus the {\tt iadd} becomes:

\begin{verbatim}
tree arg1 = pop_value (int_type_node);
tree arg2 = pop_value (int_type_node);
push_value (fold (build (PLUS_EXPR,
        int_type_node, arg1, arg2)));
\end{verbatim}

The local stack is maintained by \verb'push_value'
and \verb'pop_value'.
We construct {\tt tree} nodes using {\tt build},
and do constant folding using {\tt fold};
both are standard {\tt gcc} functions.

At the end of a basic block, the local stack
(usually empty) is copied to the home virtual registers.

This optimization allows constant folding,
and generates fewer unneeded temporaries.

\Slide{Class reflective data}

A {\tt .class} contains descriptions of the superclass, fields,
and methods of a class.

Such data is represented in the Java runtime using
various run-time data-structures.

The most efficient way for the compiler to make such data
available is to generate initialized static data that follow
the VM internal representation.  That makes startup fast,
without requiring dynamic memory allocation.

For example:
\begin{verbatim}
public class Foo extends Bar {
  public int a;
  public int f(int j) { return a+j; }
};
\end{verbatim}

compiles into assembly code equivalent to:
\begin{verbatim}
int Foo_f (Foo* this, int j)
{ return this->a + j; }

struct Method Foo_methods[1] = {{
   /* name: */   "f";
   /* code: */   (Code) &Foo_f;
   /* access: */ PUBLIC,
   /* etc */     ... 
}};

struct Class Foo_class = {
   /* name: */        "Foo",
   /* num_methods: */ 1,
   /* methods: */     Foo_methods,
   /* super: */       &Bar_class,
   /* num_fields: */  1,
   /* etc */          ...
};

static {
  RegisterClass (&Foo_class, "Foo");
}
\end{verbatim}

%\Slide{Linking}

\Slide{Run-time}

Compiled Java code depends on the specific layouts and
data structures of a Java runtime environment.

(Could compile to standard Native Method Interface,
but that has major overheads.)

Because Java code can dynamically download {\tt .class}
files, we essentially need a complete VM.

If the VM has a JIT, we can use the same calling 
convention for statically compiled and dynamically loaded code.

We are using Kaffe, a free VM developed by Tim Wilkinson.
This has a JIT and has been ported to many architectures.

We are making various changes to improve Kaffe, including
adding support for pre-compiled statically allocated classes.

\Slide{Debugging}

We will enhance {\tt gdb}, the GNU debugger, to understand Java.
This allows debugging mixed-language applications.

The {\tt cc1java} compiler already knows how to emit debugging
information ({\tt stabs}, {\tt coff}, {\tt dwarf}) that {\tt gdb} can read.
Thus we get basic debugging ``for free.''

Debugging Java raises similar issues as debugging C++:
Gdb needs a Java expression parser; needs to know how object
and classes are laid out; know how to call methods; etc.

Debugging dynamically loaded code is a complication.
In that case, gdb needs to be able to extract debugging
information from the run-time data structures.
Some changes in the VM will be needed to ease this.

%Much debugging information is duplicated between the
%run-time reflective data structures, and the traditional
%debug section of the executable.  In the future,
%we will suppress some of the latter.

\Slide{Status}

Basic structure of compiler works, including parsing bytecodes,
generating trees, emitting assembler and debugging information.
Not all bytecodes are implemented yet, and only some of the
reflective data is being emitted.

The Kaffe VM is available for many platforms.  We have made
numerous improvements to simplify the data structures and interfaces,
and to make it more suitable for pre-compiled code.

\end{document}
