Nov 17 2009, 6:53 am
From: Bill Buzbee <buz...@android.com>
Date: Mon, 16 Nov 2009 14:53:50 -0800 (PST)
Local: Tues, Nov 17 2009 6:53 am
Subject: Dalvik JIT Compiler

As some of you have noticed, the latest Android Open Source Project tree (eclair) includes source code for a Dalvik JIT compiler.  The Dalvik team has been actively investigating what kind of JIT would work best over a wide range of memory- and power-constrained portable Android devices, and the code in AOSP master is an old snapshot of what we consider a promising proof-of-concept.  It is a trace-based JIT, compiling only hot code traces rather than method-at-a-time strategy typically found on server-class JITs.  It attempts to minimize heap usage, and it requires no persistent storage.  The goal is to give a quick performance boost using very little heap and battery.

The JIT has progressed significantly since the snapshot in AOSP eclair, and we're working on pushing out a more current version. Meanwhile, if you'd like to play with the prototype, you can build it by creating a buildspec.mk file in your AOSP root which includes the line "WITH_JIT := true".

Note that the prototype JIT had not been extensively tested at the time the snapshot was taken, so you can expect some breakage.  Also, it contains few optimizations other than the basic elimination of the interpreter's fetch/decode cycle.  We're looking forward to getting a newer version into the AOSP tree.

Bill Buzbee, Ben Cheng & the rest of the Dalvik team

Nov 21 2009, 3:34 am
From: Ben Cheng <bcch...@android.com>
Date: Fri, 20 Nov 2009 11:34:09 -0800
Local: Sat, Nov 21 2009 3:34 am
Subject: Re: Dalvik JIT Compiler

Hi Tomei,

Please see my replies inline:

On Fri, Nov 20, 2009 at 10:05 AM, Tomei <tomei.ninge...@gmail.com> wrote:
> Hi Ben,

> For "switchable between JIT and interpreter at bytecode level" -- is
> this a just convenience way for developing/debugging the JIT, or part
> of a fundamental design (i.e., to support single-stepping inside the
> debugger). I hope it's the former, or else it seems performance gain
> will be quite limited.

It is just a convenient way to develop/debug the JIT. Once a trace is cut for compilation, the JIT'ed instructions are allowed to move across the original bytecode boundaries. For example, we have implemented ld/st scheduling to aggressively hoist loads and sink stores until inserted scheduling barriers or memory instructions that cannot be disambiguated. Similarly, redundant stores to the Dalvik registers can also be eliminated so that not all computed results are written back to memory.

We use the "easy switch" feature to handle heavy bytecode instructions like array initializations. Instead of inflating the codegen routine to handle it inline, we issue a single-step instruction so that all compiled instructions prior to that are optimized as usual but memory state is guaranteed to be updated prior to the array initialization instruction. Then we use the interpreter to handle it (most of the time will be spent in memcpy after all), and offer a chance to jump back to the same compilation unit and continue from the next instruction in the trace.

> How much overhead does the trace collection add to interpretation?
> There's a large part of the framework code that's executed exactly
> once during app initialization. Will app start-up be hurt? With method-
> based JIT it's quit easy to turn off JIT-sampling until the app has
> painted the first screen, etc. However, with trace-based JIT, I
> imagine that such a strategy would be much harder to do.

We have two levels of trace collection mechanism in the interpreter. The first level hashes the branch target address to update a counter in a low-cost way, and the second level kicks in only after the first-level counter has saturated to show hotness. As a result, the overhead introduced to the interpreter should be very small.

> What would be the worst case scenario for trace-based compilation? For
> example, if I have a large switch statement like this

>   switch (x) { // case 0 .. 255
>   case 1:  very simple code; break;
>   case 2:  very simple code; break;
>   case 3:  very simple code; break;
>   ...
>   case 255:  very simple code; break;
>  }

> can this be handled well?

I am glad you use this code snippet as an example as it shows a benefit of the trace based JIT mechanism. When a switch statement turns hot, we compile all the cases first (ie form an empty dispatch table) where each case occupies a fixed-amount and small overhead in the code cache. Later whenever a corresponding "very simple code; break;" turns hot we compile it and chain the entry in the dispatch table to the newly constructed compilation. In this way we don't waste space and CPU cycles on rarely exercised code in a big switch statement. However, this optimization didn't make it to the Eclair snapshot in time so it is currently absent in the JIT until the next code drop.

Cheers,
-Ben

Thanks!

对JIT不是很了解，能否推荐些学习资料

JIT compilers form a continuum, from very fast compilers producing mediocre code to slow compilers producing highly optimized code. Still, it is possible to divide this continuum roughly in two, calling one side true JITs and the other traditional compilers. This naming conveys the generally true fact that fast JIT compilers are written from scratch for use as dynamic compilers in virtual machines. Compilation speed is usually the paramount concern for such compilers. On the other hand, many of the slower, highly-optimizing compilers in use in VMs are actually traditional static compilers adapted and pressed into use as JIT compilers.

The continuum continues, of course, within these categories. Template-based JIT compilers produce a fixed code pattern for each virtual machine bytecode, doing almost no optimization but running extremely fast. More aggressive JIT compilers introduce some optimizations, but only those that preserve compilation speed. Often this means performing only optimizations that can be accomplished in a single linear code-generation pass.