How does the dalvik JIT work?

1. Build JIT trace

common_updateProfile is entry function of JIT.

the basic work flow:
1) Get the threshold value, based on hash function, which's argument is Dalvik PC(rPC);
2) If threshold is 0, call dvmJitGetTraceAddrThread() get translation code; otherwise, continuing running Dalvik code(GOTO_OPCODE_IFNE(ip));
3) if dvmJitGetTraceAddrThread() return non-zero, jump to translation by "bxne r0";
4) Otherwise, call dvmJitCheckTraceRequest() to request build translation code. and then, continuing running Dalvik code;

5) If  is on, () was called.

Not all dex opcode check common_updateProfile. The vm begin to jit dex code only when it met below op-code:

• dvmMterpStdRun
• L_OP_PACKED_SWITCH
• L_OP_SPARSE_SWITCH
• L_OP_IF_EQ
• L_OP_IF_NE
• L_OP_IF_LT
• L_OP_IF_GE
• L_OP_IF_GT
• L_OP_IF_LE
• L_OP_IF_EQZ
• L_OP_IF_NEZ
• L_OP_IF_LTZ
• L_OP_IF_GEZ
• L_OP_IF_GTZ
• L_OP_IF_LEZ

When dalvik make a jump, it makes jit check.

if the executing threshold reach special value(40 in ICS).  The dalvik will call () as below logic:

if Thread->subMode == (kSubModeJitTraceBuild | kSubModeJitSV), then
    Thread->jitState = kJitTSelectRequest;
    dvmJitCheckTraceRequest();
endif

dvmJitCheckTraceRequest() will initilize struct 

trace in struct Thread.

dvmJitCheckTraceRequest(){
   ...
1260         switch (self->jitState) {
   1261             case kJitTSelectRequest:
   1262             case kJitTSelectRequestHot:
   1263                 self->jitState = kJitTSelect;
   1264                 self->traceMethod = self->interpSave.method;
   1265                 self->currTraceHead = self->interpSave.pc;
   1266                 self->currTraceRun = 0;
   1267                 self->totalTraceLen = 0;
   1268                 self->currRunHead = self->interpSave.pc;
   1269                 self->currRunLen = 0;
   1270                 self->trace[0].info.frag.startOffset =
   1271                      self->interpSave.pc - self->interpSave.method->insns;
   1272                 self->trace[0].info.frag.numInsts = 0;
   1273                 self->trace[0].info.frag.runEnd = false;
   1274                 self->trace[0].info.frag.hint = kJitHintNone;
   1275                 self->trace[0].isCode = true;
   1276                 self->lastPC = 0;
   1277                 /* Turn on trace selection mode */
   1278                 dvmEnableSubMode(self, kSubModeJitTraceBuild);
}

dvmJitCheckTraceRequest() call dvmEnableSubMode(kSubModeJitTraceBuild) at line

1278. dvmEnableSubMode() call updateInterpBreak() in turn

void updateInterpBreak(Thread* thread, ExecutionSubModes subMode, bool enable)
{
    InterpBreak oldValue, newValue;
    do {
        oldValue = newValue = thread->interpBreak;
        newValue.ctl.breakFlags = kInterpNoBreak;  // Assume full reset
        if (enable)
            newValue.ctl.subMode |= subMode;
        else
            newValue.ctl.subMode &= ~subMode;
        if (newValue.ctl.subMode & SINGLESTEP_BREAK_MASK)
            newValue.ctl.breakFlags |= kInterpSingleStep;
        if (newValue.ctl.subMode & SAFEPOINT_BREAK_MASK)
            newValue.ctl.breakFlags |= kInterpSafePoint;
        newValue.ctl.curHandlerTable = (newValue.ctl.breakFlags) ?
            thread->altHandlerTable : thread->mainHandlerTable;
    } while (dvmQuasiAtomicCas64(oldValue.all, newValue.all,
             &thread->interpBreak.all) != 0);
}

at the end of dvmJitCheckTraceRequest(), the relative state is:

• thread->jitState = kJitTSelect;
• thread->interpBreak.all = kInterpSiggleStep;
• thread->subMode = kSubModeJitTraceBuild;

In addition, at red line, the curHandleTable is set to thread->altHandlerTable. That means dvmCheckBefore() will be called exactly before executing every dalvik code.  dvmCheckBefore(), in turn, call dvmCheckJit() if subMode = kSubModeJitTraceBuild. It is very important for building jit trace.

This is one of dalvik code interpreter snippet in altHandlerTable

19742     ldrb   r3, [rSELF, #offThread_breakFlags]           <==get breakFlag
19743     adrl   lr, dvmAsmInstructionStart + (232 * 64)      <==lr points to real handler
19744     ldr    rIBASE, [rSELF, #offThread_curHandlerTable]
19745     cmp    r3, #0
19746     bxeq   lr                   @ nothing to do - jump to real handler    <==if breakFlag is 0, jmp to real handler
19747     EXPORT_PC()                                                    <==otherwise, call dvmCheckBefore()
19748     mov    r0, rPC              @ arg0
19749     mov    r1, rFP              @ arg1
19750     mov    r2, rSELF            @ arg2
19751     b      dvmCheckBefore       @ (dPC,dFP,self) tail call     <==since lr points to real handle, dvmCheckBefore() return to real handler

In dvmCheckJit(),

...
            self->trace[self->currTraceRun].info.frag.numInsts++;
            self->totalTraceLen++;
            self->currRunLen += len;
...

if met a jmp/invoke/return/switch/throw instruction, the building jit trace will be done:

self->jitState = kJitTSelectEnd;

Once the trace build done, dvmCheckJit() calls dvmCompilerWorkEnqueue() to enqueue the trace to JIT compiler queue. The meanings of the trace fields at this time:

• self->trace[0].info.frag.startOffset: offset from jit start pc to first method instruction;
• self->trace[0].info.frag.numInsts: total number of instructions;
• self->trace[0].info.frag.runEnd = true;
• self->trace[0].info.frag.hint = kJitHintNone;
• self->trace[0].isCode = true;

In essential, the trace record the start dalvik pc offset and number of instruction after start pc.

This is simplest trace description. More complicated traces includes some meta info and multiply trace descriptions. please see insertClassMethodInfo() if met a invoke code during building jit trace.

After that, dvmCheckJit() calls dvmDisableSubMode(self, kSubModeJitTraceBuild) to disable kSubModeJitTraceBuild. at this time, the curHandleTable is restored to thread->mainHandlerTable and stop mode of the single step.

2. Compile JIT trace

Compiling dalvik code in jit trace is in separate thread. The dvmCompilerDoWork(&work) is main function. The concrete compile procedures is complicated, I can't understand it currently. 

The result of compile is saved in ::codeAddress. dalvik has JitEntry array, which is initialized to 4096 in arm arch.

When hot trace was compiled to machine code, dalvik calculates the JitEntry array index based on hash function dvmJitHash():

90 static inline u4 dvmJitHashMask( const u2* p, u4 mask ) {
     91     return ((((u4)p>>12)^(u4)p)>>1) & (mask);
     92 }
     93
     94 static inline u4 dvmJitHash( const u2* p ) {
     95     return dvmJitHashMask( p, gDvmJit.jitTableMask );
     96 }

The input of dvmJitHash() is dalvik PC. If the index is occupied, the dalvik find out next 

free entry and set current u.. = next free index;

The translate code is stored in share memory named by "dalvik-jit-code-cache", the initialized size is 1M.

The codeAddress in jitEntry points to that code cache.

3 Summary

When met jump dex-code, dalvik calculates the executing times for this dex-code. If the 

times is more than 40(in ICS), dalvik lunch JIT trace build process. In that process, the

dalvik is actually in single step mode, call dvmCheckBefore() before real dex-code. In

dvmCheckBeofore(), the number of decx-code is recorded. When dalvik meets jump code

again, the JIT trace build process is ended. The dalvik feed the trace to compiler thread.

The compiler thread output the compile result in array of JitEntry. The index of array is

hash value for dalvik PC value.

Problem?

The trace snippet starts from jmp code and ends in jmp code. The compiler perform on that

small snippet code. No global optimized tech can be applied;