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

[Etienne M. G. <eg...@j-...>]

Andrew Purtell wrote:
> 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.

Have you looked at the "Soot" framework
(http://www.sable.mcgill.ca/soot/)?  It does already provide more than
this, including most analyses you need.  It's internal representation is
"stackless" 3-address codes, with "typed" local variables.  We have
already a few papers about this.  It might be a good starting point. 
Currently, Soot statically analyses whole applications with no dynamic
class loading, but you could probably adapt it to dynamic code.

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

Assuming SableVM already executes the bytecodes (while you are
optimizing them on another thread), this should have already been done,
so you shouldn't care about verification in the JIT.

>   - 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))
> 

Some of these are probably better left to a higher 3-address
representation (see Soot).  Others might fit well with a back-end,
including some peep-hole optimizations.

>   - 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. :)

As I said in an earlier message, I do not think that JIT compiling every
method is a good way to go.  Ideally, you want the optimizer to pick
frequently executed code, then take the time to crunch this as best as
it can.  The idea is, if the interpreter is fast enough, then this
should be OK, as short programs will execute fast enough, and long
running programs will benefit from an aggressive optimizer.


Etienne


> 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...
> 
> _______________________________________________
> Sablevm-user mailing list
> Sab...@li...
> http://lists.sourceforge.net/mailman/listinfo/sablevm-user

-- 
----------------------------------------------------------------------
Etienne M. Gagnon, M.Sc.                     e-mail: eg...@j-...
Author of SableVM:                             http://www.sablevm.org/
----------------------------------------------------------------------