JIT optimization framework (was: Re: [Sablevm-user] bug report...)

[Andrew P. <apu...@ac...>]

> "John Leuner" <je...@pi...>  wrote:
> Andrew, I've been developing a JVM for the past while 
> (kissme.sourceforge.net), it's implemented in C and targeted at (free) 
> UNIX. 

Hi, John.

> Unfortunately I had to stop working on this project for two months
> due to a sports injury but I've recovered enough to carry on working 
> now. 

That's unfortunate. I'm sorry to hear that.

> If you're interested in the code or just discussing jits or
> whatever, just let me know. 

Both. :)

I've downloaded your 0.07 source and I'll have a look next week when I 
have time.

As for my interest in JIT technology, I've been inspired by the
OpenJIT project (www.openjit.org) to implement a JIT framework where
the JIT, code generator, and optimizer are all first-class Java
objects. Normally I am not taken to duplicating the work of others,
but this is cool technology that really should be available under the 
GPL. I have not looked at the OpenJIT source, so this will be a 
"clean-room" effort in the respect. I'm investigating if that status
also applies to work with Java in general.

I note that you generate assembly text and then compile it. I was
thinking of doing something more along the lines of the following:

  - Partition bytecodes into basic blocks while building a control
    flow graph.

  - Optionally run the standard Java code safety verification process, 
    if this has been requested, e.g. "jvm -verify ..."

  - Convert bytecodes into register transfer lists, mapping values on
    the operand stack to symbolic registers.

  - Hand off the RTL to "plug-in" optimization modules. What
    optimizations are actually performed depend very much on how 
    quickly I can get them to operate. Some classic optimizations are
    very time-intensive. Initially I was thinking:

      - Constant folding, constant propagation, copy propagation, and 
        value numbering.

      - Code straightening and jump threading.

      - Common subexpression elimination (maybe).

      - Dead code elimination (maybe).

      - Replacement of certain bytecode patterns with precooked 
        assembly templates, e.g. for x86:

            aload $value; invokevirtual "ntohl" ->
                asm ("bswap %0" : "=r" (value) : "0" (value))

            aload $value; invokevirtual "ntohs" ->
                asm ("xchgb %b0,%h0" : "=q" (value) :  "0" (value))

        or for Alpha:

            aload $value; invokevirtual "ntohs" ->
                asm ("insbl %2,1,%1; extbl %2,1,%0; or $2,$1,$2"
                     : "=r"(t1), "=&r"(t2) : "r"(x))

  - Finally, hand over the munged RTL to an emitter which emits native 
    code directly into space allocated on the Java heap. The emitter 
    would assign real registers from symbolic ones using one of the
    graph coloring algorithms. If that kind of thing is too expensive, 
    there are alternatives.

  - For Alpha, a final peephole optimization pass is required because
    instruction scheduling is very important for that platform.

All of that may be a bit much for a JIT, but whether or not that is
true is what I want to find out. :)

I would also want to add a module for converting variable references
to immediate constants if the values are known at runtime. Perhaps
there will also be an API for specifying such values. Code like this:

   if (case_a_is_true) {
       /* a long block of code follows */
   } else {
       /* more code */
   }

could be processed into:

   /* case_a_is_true is constant and always false */
   /* more code */

Implementing all of the optimization framework in Java means
everything is very dynamic and -- best of all -- can be self-
bootstrapped into native code for maximum performance.


Andrew Purtell
from home -- apu...@ac...