This is Ben, one of the engineers working on the JIT @ Google. When Bill and I started on this project, the goal was to deliver a working JIT as soon as possible with minimal impact to resource contention (eg memory footprint, CPU hijacked by the compiler thread) so that it can run on low-end devices as well. Therefore we used a very primitive trace based model. That is, the compilation entity passed to the JIT compiler is a basic block, sometimes as short as a single instruction. Such traces will be stitched together at runtime through a technique called chaining so that the interpreter and code cache lookup won’t be invoked often. To some degree the major source of speedup comes from eliminating the repeated interpreter parsing overhead on frequently executed code paths.
That said, we do have quite a few local optimizations implemented with the Froyo JIT:
- Register allocation (8 registers for v5te target since the JIT produces Thumb code / 16 registers for v7)
- Scheduling (eg redundant ld/st elimination for Dalvik registers, load hoisting, store sinking)
- Redundant null check elimination (if such redundancy can be found in a basic block).
- Loop formation and optimization for simple counted loops (ie no side-exit in the loop body). For such loops, array accesses based on extended induction variables are optimized so that null and range checks are only performed in the loop prologue.
- One entry inline cache per virtual callsite w/ dynamic patching at runtime.
- Peephole optimizations like power-reduction on literal operands for mul/div.
In Gingerbread we added simple inlining for getters/setters. Since the underlying JIT frontend is still simple trace based, if the callee has branches in there it won’t be inlined. But the inline cache mechanism is implemented so that virtual getters/setters can be inlined without problems.
We are currently working on enlarging the compilation scope beyond a simple trace so that the compiler has a larger window for code analysis and optimization. Stay tuned.