High level documentation for the just-in-time compiler, version 3.

Introduction
------------

The jit3 just-in-time compiler is used to translate Java byte codes
into native machine code, resulting in a significant speedup over the
interpreter.  However, unlike the interpreter, the compiler must be
ported by hand to new architectures and operating systems.  This
document attempts to give a high level overview of the layout and
control flow of the jit3 compiler, more detailed information can be
found at:

  http://www.cs.pdx.edu/~sanseri/kaffe/kaffe.html
  http://egp.free.fr/port-kaffe/port-kaffe-0.2.html
  http://www2.biglobe.ne.jp/~inaba/trampolines.html


Configure
---------

If the jit3 engine is available for your architecture it will
automatically be enabled.  This detection is done by testing for the
existence of the "config/${host_cpu}/jit3-${host_cpu}.def" and
"config/${host_cpu}/${host_os}/jit3-md.h" files.  If you would like to
disable the jit3 engine you can revert to the original jit or
interpreter by passing the "--with-engine" argument to configure.

Enabling the jitter will also make other options available, such as,
cross language debugging and profiling.  These options can assist a
great deal when analyzing the generated code.  For more information,
consult the FAQ.profiler, FAQ.xdebugging, and FAQ.xprofiler files
found in this directory.


Usage
-----

Nothing special needs to be done to make use of the jit3 engine,
enabling the system in configure is enough.


Implementation
--------------

The root of the compiler is the "translate" function found in the
kaffe/kaffevm/jit3/machine.c file.  The core of the compiler consists
of three stages:  byte code analysis, generating instructions, and
linking the generated code into the VM.

The first stage, byte code analysis, is performed by the verifyMethod
function in kaffe/kaffevm/code-analyse.c.  This function generates a
"codeinfo" structure that contains information about the stack
requirements of the method, usage information for any locals, and
attributes associated with individual byte codes.

Once the byte code has been analyzed the process of translating
individual instructions can begin.  The translation is done separately
for each basic block and occurs in two passes, first, the byte codes
are mapped onto an intermediate function set by the
kaffe/kaffevm/kaffe.def file (which is included by
kaffe/kaffevm/jit3/funcs.c).  These intermediate functions and macros
then generate a list of "sequence" objects which contain function
pointers to the architecture dependent back end.  Lastly, when the
translator reaches the end of a basic block the set of generated
sequence structures are iterated over causing the back end to emit the
appropriate instruction sequences.

Finally, when all of the basic blocks have been processed, the
resulting native code is copied to its final resting place and linking
is initiated.  Linking the code involves rewriting the generated
instructions using information that is only available at the end of
code generation.  For example, addresses referred to in the code may
have changed when it was copied to its new location or stack frame
offsets and sizes may have changed during the generation of successive
basic blocks.

Psuedo code for the translate() function:

  translate(Method *xmeth, errorInfo *einfo)
  {
    codeInfo = verifyMethod(xmeth); // Analyze the byte code.

    /* Clear the memory used to store in progress native code. */
    nativecode.clear();
    /* Iterate over each byte code. */
    foreach bytecode in xmeth.bcode
    {
      switch( bytecode )
      {
        /* 
	 * Interpret each byte using a series of calls to intermediate
	 * functions and macros that will append to the "sequences"
	 * list.
	 */
        #include "kaffe.def"
      }
      if( codeinfo.startofbasicblock(pc) )
      {
        /*
	 * We're at the end of a basic block, emit the current set of
	 * translated instructions.
	 */
	sequences.walk(nativecode);
	sequences.reset(); // Empty the list
      }
    }
    /* Emit any pending instructions from the last basic block. */
    sequences.walk();
    /* Allocate a final resting place for the code. */
    dest = gc_malloc(nativecode.size);
    /* Copy from our scratch space. */
    memcpy(dest, nativecode);
    /* Link the labels using the new location of the code. */
    labels.link(dest);
  }

As an alternative to translating byte codes, the intermediate layer
can be used directly to generate methods required by the VM.  For
example, the JNI and KNI wrapper functions as generated by the
kaffe/kaffevm/jni.c file use the "pusharg" and similar functions
defined by the intermediate layer to push the arguments on the stack
and call the function.

Extra Detail:

Besides the straight forward translation of instructions, the jitter
can also generate a "constant pool" for each method and a series of
"fake" calls for triggering exceptions.  The constant pool is used to
hold constants referenced by the method, but are to large to inline in
the instruction stream.  For example, a 32 bit number, like
"0xdeadbeef", will not fit into the load immediate instruction
provided by the PowerPC.  Instead, the number is stored in memory
prepended to the method so that it can be loaded based on a PC value
minus some offset.  The "fake" calls are used to move calls to
exception functions out of the main line code while still maintaining
a proper return address.  For example, in the x86 back end, the
conditional branch used to detect a bad array index is unable to
directly call "soft_badarrayindex()".  Therefore, it jumps to the fake
call which pushes the PC of the offending instruction and calls the
exception function.  If the proper PC wasn't pushed, then any
generated stack traces would not show the correct source of the
exception.  Unfortunately, generating fake calls for each test can
result in a lot of redundant code.  Alternatively, architectures that
support branch and link instructions can use them to reach the fake
call where it will branch directly to the soft function.

File Layout
-----------

  kaffe/kaffevm/jit3 - The home directory of the jitter.
  XXX The "organization" in here generally sucks.

  kaffe/kaffevm/jit3/basecode.[ch] - Code generation primitives,
  including:  start/end function, start/end blocks, monitor
  enter/exit, functions for generating sequence structures.

  kaffe/kaffevm/jit3/checks.h - Empty macros for satisfying the checks
  done in the kaffe.def file.

  kaffe/kaffevm/jit3/codeproto.h - Prototypes for the intermediate
  layer functions.

  kaffe/kaffevm/jit3/constpool.[ch] - Functions for manipulating the
  method's constant pool.  Constants, such as addresses, integers, and
  doubles can be added to the pool which are then copied to an area
  preceding the method code.

  kaffe/kaffevm/jit3/funcs.c - Wrapper for
  config/${host_cpu}/jit3-${host_cpu}.def file.  Defines the following
  variables and macros:

    define_insn(n, i) - Define the implementation of an architecture
    specific intermediate instruction.  This just resolves down to a
    function prototype of the form "void i (sequence *s)" and the "n"
    value is just for documentation purposes.

    codeblock - The memory area used to store native code as it is
    generated.  It is resized automatically if the native code grows
    beyond the current size.

    CODEPC - The current index into codeblock.

    OUT, BOUT, WOUT, LOUT, QOUT - Macros that store values given by
    arguments into the current position and automatically increment
    the CODEPC value.  For example, using "LOUT(0x45)" in the
    architecture defs file will put the 32 bit value "0x45" into the
    current position in the code block and increment CODEPC by four.

  kaffe/kaffevm/jit3/icode.c - The implementation of the intermediate
  functions.  These functions generate "sequence" structures that
  refer to the architecture specific functions.

  kaffe/kaffevm/jit3/labels.[ch] - Functions for manipulating label
  objects.  A label is used to rewrite code at the end of translation,
  for example, to set the destination of a forward branch.

  kaffe/kaffevm/jit3/machine.c - Contains the translate() function and
  its supporting functions, the functions for walking the list of
  sequences, functions for creating fake calls, and anything else that
  people were too lazy to separate into another file.

  kaffe/kaffevm/jit3/registers.[ch] - The register allocator.

  kaffe/kaffevm/jit3/seq.[ch] - Functions for creating sequence
  objects.

  kaffe/kaffevm/jit3/slots.[ch] - Functions for manipulating slot
  objects.  A slot is used to track a function locals, arguments, and
  temporaries.

  config/${host_cpu}/jit.h - Primary jitter header file.

    ${host_cpu}_do_fixup_trampoline() - A prototype for a function,
    usually written in asm, that is called by the trampoline to save
    the arguments to an untranslated method and call
    soft_fixup_trampoline with the method pointer and the trampoline
    address to fix.

    methodTrampoline - A structure that can wholly contain the
    trampoline code, method pointer, and the pointer pointing to
    this trampoline.

    FILL_IN_TRAMPOLINE(t, m, w) - A macro used to fill out the
    trampoline object, t, with the method, m, and the pointer to the
    trampoline pointer, w.

    FIXUP_TRAMPOLINE_DECL - A macro that defines the parameters to the
    soft_fixup_trampoline function.

    FIXUP_TRAMPOLINE_INIT - A macro that sets the "meth" and "where"
    locals in soft_fixup_trampoline to the "m" and "w" values given in
    FILL_IN_TRAMPOLINE.

    L${label_type} - A series of macros that define architecture
    dependent label types.
    XXX Needs to be a define and not an enum or anything like that
    since the file is included in places where "labels.h" isn't.

    EXTRA_LABELS(P, V, L) - A macro used to translate architecture
    dependent labels, where, "P" is a pointer to the code to modify,
    "V" is the computed value of the label, and "L" is the label
    object.

    SLOT2LOCALOFFSET(N) - A macro that translates a slot index, N, to
    a stack frame offset.

    SLOT2ARGOFFSET(N) - A macro that translates a method argument
    index, N, to a stack frame offset.

    KAFFEJIT_TO_NATIVE(M) - XXX Unknown.

    FLUSH_DCACHE(code_start, code_end) - A macro that can be used to
    flush the data cache between "code_start" and "code_end" of any
    instructions generated by the jitter.
    XXX Needs to be a define since it gets #ifdef'd.

    PUSHARG_FORWARDS - A macro that, when defined, causes icode
    functions to push arguments starting at index zero.  Otherwise,
    the arguments are pushed starting at the end of the list.

  config/${host_cpu}/${host_os}/jit3-md.h - An operating system
  specific header file.  Usually just includes ${host_cpu}/jit.h.

  config/${host_cpu}/jit3-icode.h - A header file that describes the
  capabilities of the architecture's jit3 back end.  The rangecheck()
  macros are used to decide which immediates can be inlined directly
  in the instruction stream or added to the constant pool.  And, the
  HAVE macros tell the core library which intermediate instructions it
  can handle directly and which ones need to be emulated.

  config/${host_cpu}/jit3-${host_cpu}.def - The jit3 back end,
  typically, it contains a number of functions defined using the
  "define_insn()" macro.  Basically, these functions implement the
  intermediate instructions by emitting instructions specific to the
  native instruction set.