dalvik jit compiler register allocation algorithm?

[Jack Harvard]

I tried to understand the register allocation algorithm used in Dalvik JIT compiler, it looks it's not using the linear scanning register allocation as in Java SE Embedded Client JIT, as Dalvik bytecode is already register based (albeit virtual register based?), while the Java bytecode is stack-based. The source code said simple local register allocation, and it's done at the MIR level, wondering what the local register allocation algorithm is used.

[Liu Xin]

hi, Jack, 

i think it uses local RA by default(arm). i am not sure other platforms. 

thanks,

--lx

On Fri, May 10, 2013 at 6:36 AM, Jack Harvard <jack.h...@gmail.com> wrote:

I tried to understand the register allocation algorithm used in Dalvik JIT compiler, it looks it's not using the linear scanning register allocation as in Java SE Embedded Client JIT, as Dalvik bytecode is already register based (albeit virtual register based?), while the Java bytecode is stack-based. The source code said simple local register allocation, and it's done at the MIR level, wondering what the local register allocation algorithm is used.

--
You received this message because you are subscribed to the Google Groups "android-platform" group.
To unsubscribe from this group and stop receiving emails from it, send an email to android-platfo...@googlegroups.com.
To post to this group, send email to android-...@googlegroups.com.
Visit this group at http://groups.google.com/group/android-platform?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

[Jack Harvard]

How does local register allocation compare to linear scan register allocation?

Jack Harvard

[Liu Xin]

backing to 2.3, when dalvik first introduced jit compiler, there was a linear scan ra. the code was there but was not on.  it seems that the performance was not good in google 's evaluation.

i don't think performance is the primary consideration for dalvik, given the fact that arm cortex processors are so powerful now. actually, i think  dx generates bad code from bytecode to dex.

--lx

[Jack Harvard]

On 10 May 2013, at 18:26, Liu Xin wrote:

> backing to 2.3, when dalvik first introduced jit compiler, there was a linear scan ra. the code was there but was not on. it seems that the performance was not good in google 's evaluation.
>
> i don't think performance is the primary consideration for dalvik, given the fact that arm cortex processors are so powerful now. actually, i think dx generates bad code from bytecode to dex.

Can you elaborate on the bytecode to dex point?

[Liu Xin]

if you use baksmali to disassemble a classes.dex, you can easily spot some ld/st/ld  instruction sequences. 

thanks,

--lx

 

[Kristopher Micinski]

That's true. Conversion to Dalvik actually seems to be pretty naive.
It doesn't matter because these peephole optimizations can be done at
any number of levels after the bytecode: optimization within VM, JIT,
etc.. I've also seen that bytecode conversion seems pretty naïve (not
talking about the JIT allocation strategy here, but in conversion to
bytecode) I routinely saw register allocations that were suboptimal
given simple rd analysis and graph coloring.

Kris