vm/interp/Jit.c

   1 /*
   2  * Copyright (C) 2008 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 #ifdef WITH_JIT
  17
  18 /*
  19  * Target independent portion of Android's Jit
  20  */
  21
  22 #include "Dalvik.h"
  23 #include "Jit.h"
  24
  25
  26 #include "dexdump/OpCodeNames.h"
  27 #include <unistd.h>
  28 #include <pthread.h>
  29 #include <sys/time.h>
  30 #include <signal.h>
  31 #include "compiler/Compiler.h"
  32 #include "compiler/CompilerUtility.h"
  33 #include "compiler/CompilerIR.h"
  34 #include <errno.h>
  35
  36 #if defined(WITH_SELF_VERIFICATION)
  37 /* Allocate space for per-thread ShadowSpace data structures */
  38 void* dvmSelfVerificationShadowSpaceAlloc(Thread* self)
  39 {
  40     self->shadowSpace = (ShadowSpace*) calloc(1, sizeof(ShadowSpace));
  41     if (self->shadowSpace == NULL)
  42         return NULL;
  43
  44     self->shadowSpace->registerSpaceSize = REG_SPACE;
  45     self->shadowSpace->registerSpace =
  46         (int*) calloc(self->shadowSpace->registerSpaceSize, sizeof(int));
  47
  48     return self->shadowSpace->registerSpace;
  49 }
  50
  51 /* Free per-thread ShadowSpace data structures */
  52 void dvmSelfVerificationShadowSpaceFree(Thread* self)
  53 {
  54     free(self->shadowSpace->registerSpace);
  55     free(self->shadowSpace);
  56 }
  57
  58 /*
  59  * Save out PC, FP, InterpState, and registers to shadow space.
  60  * Return a pointer to the shadow space for JIT to use.
  61  */
  62 void* dvmSelfVerificationSaveState(const u2* pc, const void* fp,
  63                                    void* interpStatePtr)
  64 {
  65     Thread *self = dvmThreadSelf();
  66     ShadowSpace *shadowSpace = self->shadowSpace;
  67     InterpState *interpState = (InterpState *) interpStatePtr;
  68     int preBytes = interpState->method->outsSize*4 + sizeof(StackSaveArea);
  69     int postBytes = interpState->method->registersSize*4;
  70
  71     //LOGD("### selfVerificationSaveState(%d) pc: 0x%x fp: 0x%x",
  72     //    self->threadId, (int)pc, (int)fp);
  73
  74     if (shadowSpace->selfVerificationState != kSVSIdle) {
  75         LOGD("~~~ Save: INCORRECT PREVIOUS STATE(%d): %d",
  76             self->threadId, shadowSpace->selfVerificationState);
  77         LOGD("********** SHADOW STATE DUMP **********");
  78         LOGD("* PC: 0x%x FP: 0x%x", (int)pc, (int)fp);
  79     }
  80     shadowSpace->selfVerificationState = kSVSStart;
  81
  82     // Dynamically grow shadow register space if necessary
  83     while (preBytes + postBytes > shadowSpace->registerSpaceSize) {
  84         shadowSpace->registerSpaceSize *= 2;
  85         free(shadowSpace->registerSpace);
  86         shadowSpace->registerSpace =
  87             (int*) calloc(shadowSpace->registerSpaceSize, sizeof(int));
  88     }
  89
  90     // Remember original state
  91     shadowSpace->startPC = pc;
  92     shadowSpace->fp = fp;
  93     shadowSpace->glue = interpStatePtr;
  94     shadowSpace->shadowFP = shadowSpace->registerSpace +
  95                             shadowSpace->registerSpaceSize - postBytes/4;
  96
  97     // Create a copy of the InterpState
  98     memcpy(&(shadowSpace->interpState), interpStatePtr, sizeof(InterpState));
  99     shadowSpace->interpState.fp = shadowSpace->shadowFP;
 100     shadowSpace->interpState.interpStackEnd = (u1*)shadowSpace->registerSpace;
 101
 102     // Create a copy of the stack
 103     memcpy(((char*)shadowSpace->shadowFP)-preBytes, ((char*)fp)-preBytes,
 104         preBytes+postBytes);
 105
 106     // Setup the shadowed heap space
 107     shadowSpace->heapSpaceTail = shadowSpace->heapSpace;
 108
 109     // Reset trace length
 110     shadowSpace->traceLength = 0;
 111
 112     return shadowSpace;
 113 }
 114
 115 /*
 116  * Save ending PC, FP and compiled code exit point to shadow space.
 117  * Return a pointer to the shadow space for JIT to restore state.
 118  */
 119 void* dvmSelfVerificationRestoreState(const u2* pc, const void* fp,
 120                                       SelfVerificationState exitPoint)
 121 {
 122     Thread *self = dvmThreadSelf();
 123     ShadowSpace *shadowSpace = self->shadowSpace;
 124     shadowSpace->endPC = pc;
 125     shadowSpace->endShadowFP = fp;
 126
 127     //LOGD("### selfVerificationRestoreState(%d) pc: 0x%x fp: 0x%x endPC: 0x%x",
 128     //    self->threadId, (int)shadowSpace->startPC, (int)shadowSpace->fp,
 129     //    (int)pc);
 130
 131     if (shadowSpace->selfVerificationState != kSVSStart) {
 132         LOGD("~~~ Restore: INCORRECT PREVIOUS STATE(%d): %d",
 133             self->threadId, shadowSpace->selfVerificationState);
 134         LOGD("********** SHADOW STATE DUMP **********");
 135         LOGD("* Dalvik PC: 0x%x endPC: 0x%x", (int)shadowSpace->startPC,
 136             (int)shadowSpace->endPC);
 137         LOGD("* Interp FP: 0x%x", (int)shadowSpace->fp);
 138         LOGD("* Shadow FP: 0x%x endFP: 0x%x", (int)shadowSpace->shadowFP,
 139             (int)shadowSpace->endShadowFP);
 140     }
 141
 142     // Special case when punting after a single instruction
 143     if (exitPoint == kSVSPunt && pc == shadowSpace->startPC) {
 144         shadowSpace->selfVerificationState = kSVSIdle;
 145     } else {
 146         shadowSpace->selfVerificationState = exitPoint;
 147     }
 148
 149     return shadowSpace;
 150 }
 151
 152 /* Print contents of virtual registers */
 153 static void selfVerificationPrintRegisters(int* addr, int numWords)
 154 {
 155     int i;
 156     for (i = 0; i < numWords; i++) {
 157         LOGD("* 0x%x: (v%d) 0x%8x", (int)(addr+i), i, *(addr+i));
 158     }
 159 }
 160
 161 /* Print values maintained in shadowSpace */
 162 static void selfVerificationDumpState(const u2* pc, Thread* self)
 163 {
 164     ShadowSpace* shadowSpace = self->shadowSpace;
 165     StackSaveArea* stackSave = SAVEAREA_FROM_FP(self->curFrame);
 166     int frameBytes = (int) shadowSpace->registerSpace +
 167                      shadowSpace->registerSpaceSize*4 -
 168                      (int) shadowSpace->shadowFP;
 169     int localRegs = 0;
 170     int frameBytes2 = 0;
 171     if (self->curFrame < shadowSpace->fp) {
 172         localRegs = (stackSave->method->registersSize -
 173                      stackSave->method->insSize)*4;
 174         frameBytes2 = (int) shadowSpace->fp - (int) self->curFrame - localRegs;
 175     }
 176     LOGD("********** SHADOW STATE DUMP **********");
 177     LOGD("* CurrentPC: 0x%x, Offset: 0x%04x", (int)pc,
 178         (int)(pc - stackSave->method->insns));
 179     LOGD("* Class: %s Method: %s", stackSave->method->clazz->descriptor,
 180         stackSave->method->name);
 181     LOGD("* Dalvik PC: 0x%x endPC: 0x%x", (int)shadowSpace->startPC,
 182         (int)shadowSpace->endPC);
 183     LOGD("* Interp FP: 0x%x endFP: 0x%x", (int)shadowSpace->fp,
 184         (int)self->curFrame);
 185     LOGD("* Shadow FP: 0x%x endFP: 0x%x", (int)shadowSpace->shadowFP,
 186         (int)shadowSpace->endShadowFP);
 187     LOGD("* Frame1 Bytes: %d Frame2 Local: %d Bytes: %d", frameBytes,
 188         localRegs, frameBytes2);
 189     LOGD("* Trace length: %d State: %d", shadowSpace->traceLength,
 190         shadowSpace->selfVerificationState);
 191 }
 192
 193 /* Print decoded instructions in the current trace */
 194 static void selfVerificationDumpTrace(const u2* pc, Thread* self)
 195 {
 196     ShadowSpace* shadowSpace = self->shadowSpace;
 197     StackSaveArea* stackSave = SAVEAREA_FROM_FP(self->curFrame);
 198     int i, addr, offset;
 199     DecodedInstruction *decInsn;
 200
 201     LOGD("********** SHADOW TRACE DUMP **********");
 202     for (i = 0; i < shadowSpace->traceLength; i++) {
 203         addr = shadowSpace->trace[i].addr;
 204         offset =  (int)((u2*)addr - stackSave->method->insns);
 205         decInsn = &(shadowSpace->trace[i].decInsn);
 206         /* Not properly decoding instruction, some registers may be garbage */
 207         LOGD("* 0x%x: (0x%04x) %s v%d, v%d, v%d", addr, offset,
 208             getOpcodeName(decInsn->opCode), decInsn->vA, decInsn->vB,
 209             decInsn->vC);
 210     }
 211 }
 212
 213 /* Code is forced into this spin loop when a divergence is detected */
 214 static void selfVerificationSpinLoop()
 215 {
 216     gDvmJit.selfVerificationSpin = true;
 217     while(gDvmJit.selfVerificationSpin) sleep(10);
 218 }
 219
 220 /* Manage self verification while in the debug interpreter */
 221 static bool selfVerificationDebugInterp(const u2* pc, Thread* self)
 222 {
 223     ShadowSpace *shadowSpace = self->shadowSpace;
 224     SelfVerificationState state = shadowSpace->selfVerificationState;
 225
 226     DecodedInstruction decInsn;
 227     dexDecodeInstruction(gDvm.instrFormat, pc, &decInsn);
 228
 229     //LOGD("### DbgIntp(%d): PC: 0x%x endPC: 0x%x state: %d len: %d %s",
 230     //    self->threadId, (int)pc, (int)shadowSpace->endPC, state,
 231     //    shadowSpace->traceLength, getOpcodeName(decInsn.opCode));
 232
 233     if (state == kSVSIdle || state == kSVSStart) {
 234         LOGD("~~~ DbgIntrp: INCORRECT PREVIOUS STATE(%d): %d",
 235             self->threadId, state);
 236         selfVerificationDumpState(pc, self);
 237         selfVerificationDumpTrace(pc, self);
 238     }
 239
 240     /* Skip endPC once when trace has a backward branch */
 241     if ((state == kSVSBackwardBranch && pc == shadowSpace->endPC) ||
 242         state != kSVSBackwardBranch) {
 243         shadowSpace->selfVerificationState = kSVSDebugInterp;
 244     }
 245
 246     /* Check that the current pc is the end of the trace */
 247     if ((state == kSVSSingleStep || state == kSVSDebugInterp) &&
 248         pc == shadowSpace->endPC) {
 249
 250         shadowSpace->selfVerificationState = kSVSIdle;
 251
 252         /* Check register space */
 253         int frameBytes = (int) shadowSpace->registerSpace +
 254                          shadowSpace->registerSpaceSize*4 -
 255                          (int) shadowSpace->shadowFP;
 256         if (memcmp(shadowSpace->fp, shadowSpace->shadowFP, frameBytes)) {
 257             LOGD("~~~ DbgIntp(%d): REGISTERS UNEQUAL!", self->threadId);
 258             selfVerificationDumpState(pc, self);
 259             selfVerificationDumpTrace(pc, self);
 260             LOGD("*** Interp Registers: addr: 0x%x bytes: %d",
 261                 (int)shadowSpace->fp, frameBytes);
 262             selfVerificationPrintRegisters((int*)shadowSpace->fp, frameBytes/4);
 263             LOGD("*** Shadow Registers: addr: 0x%x bytes: %d",
 264                 (int)shadowSpace->shadowFP, frameBytes);
 265             selfVerificationPrintRegisters((int*)shadowSpace->shadowFP,
 266                 frameBytes/4);
 267             selfVerificationSpinLoop();
 268         }
 269         /* Check new frame if it exists (invokes only) */
 270         if (self->curFrame < shadowSpace->fp) {
 271             StackSaveArea* stackSave = SAVEAREA_FROM_FP(self->curFrame);
 272             int localRegs = (stackSave->method->registersSize -
 273                              stackSave->method->insSize)*4;
 274             int frameBytes2 = (int) shadowSpace->fp -
 275                               (int) self->curFrame - localRegs;
 276             if (memcmp(((char*)self->curFrame)+localRegs,
 277                 ((char*)shadowSpace->endShadowFP)+localRegs, frameBytes2)) {
 278                 LOGD("~~~ DbgIntp(%d): REGISTERS (FRAME2) UNEQUAL!",
 279                     self->threadId);
 280                 selfVerificationDumpState(pc, self);
 281                 selfVerificationDumpTrace(pc, self);
 282                 LOGD("*** Interp Registers: addr: 0x%x l: %d bytes: %d",
 283                     (int)self->curFrame, localRegs, frameBytes2);
 284                 selfVerificationPrintRegisters((int*)self->curFrame,
 285                     (frameBytes2+localRegs)/4);
 286                 LOGD("*** Shadow Registers: addr: 0x%x l: %d bytes: %d",
 287                     (int)shadowSpace->endShadowFP, localRegs, frameBytes2);
 288                 selfVerificationPrintRegisters((int*)shadowSpace->endShadowFP,
 289                     (frameBytes2+localRegs)/4);
 290                 selfVerificationSpinLoop();
 291             }
 292         }
 293
 294         /* Check memory space */
 295         bool memDiff = false;
 296         ShadowHeap* heapSpacePtr;
 297         for (heapSpacePtr = shadowSpace->heapSpace;
 298              heapSpacePtr != shadowSpace->heapSpaceTail; heapSpacePtr++) {
 299             int memData = *((unsigned int*) heapSpacePtr->addr);
 300             if (heapSpacePtr->data != memData) {
 301                 LOGD("~~~ DbgIntp(%d): MEMORY UNEQUAL!", self->threadId);
 302                 LOGD("* Addr: 0x%x Intrp Data: 0x%x Jit Data: 0x%x",
 303                     heapSpacePtr->addr, memData, heapSpacePtr->data);
 304                 selfVerificationDumpState(pc, self);
 305                 selfVerificationDumpTrace(pc, self);
 306                 memDiff = true;
 307             }
 308         }
 309         if (memDiff) selfVerificationSpinLoop();
 310         return true;
 311
 312     /* If end not been reached, make sure max length not exceeded */
 313     } else if (shadowSpace->traceLength >= JIT_MAX_TRACE_LEN) {
 314         LOGD("~~~ DbgIntp(%d): CONTROL DIVERGENCE!", self->threadId);
 315         LOGD("* startPC: 0x%x endPC: 0x%x currPC: 0x%x",
 316             (int)shadowSpace->startPC, (int)shadowSpace->endPC, (int)pc);
 317         selfVerificationDumpState(pc, self);
 318         selfVerificationDumpTrace(pc, self);
 319         selfVerificationSpinLoop();
 320
 321         return true;
 322     }
 323     /* Log the instruction address and decoded instruction for debug */
 324     shadowSpace->trace[shadowSpace->traceLength].addr = (int)pc;
 325     shadowSpace->trace[shadowSpace->traceLength].decInsn = decInsn;
 326     shadowSpace->traceLength++;
 327
 328     return false;
 329 }
 330 #endif
 331
 332 int dvmJitStartup(void)
 333 {
 334     unsigned int i;
 335     bool res = true;  /* Assume success */
 336
 337     // Create the compiler thread and setup miscellaneous chores */
 338     res &= dvmCompilerStartup();
 339
 340     dvmInitMutex(&gDvmJit.tableLock);
 341     if (res && gDvm.executionMode == kExecutionModeJit) {
 342         JitEntry *pJitTable = NULL;
 343         unsigned char *pJitProfTable = NULL;
 344         // Power of 2?
 345         assert(gDvmJit.jitTableSize &&
 346                !(gDvmJit.jitTableSize & (gDvmJit.jitTableSize - 1)));
 347         dvmLockMutex(&gDvmJit.tableLock);
 348         pJitTable = (JitEntry*)
 349                     calloc(gDvmJit.jitTableSize, sizeof(*pJitTable));
 350         if (!pJitTable) {
 351             LOGE("jit table allocation failed\n");
 352             res = false;
 353             goto done;
 354         }
 355         /*
 356          * NOTE: the profile table must only be allocated once, globally.
 357          * Profiling is turned on and off by nulling out gDvm.pJitProfTable
 358          * and then restoring its original value.  However, this action
 359          * is not syncronized for speed so threads may continue to hold
 360          * and update the profile table after profiling has been turned
 361          * off by null'ng the global pointer.  Be aware.
 362          */
 363         pJitProfTable = (unsigned char *)malloc(JIT_PROF_SIZE);
 364         if (!pJitProfTable) {
 365             LOGE("jit prof table allocation failed\n");
 366             res = false;
 367             goto done;
 368         }
 369         memset(pJitProfTable,0,JIT_PROF_SIZE);
 370         for (i=0; i < gDvmJit.jitTableSize; i++) {
 371            pJitTable[i].u.info.chain = gDvmJit.jitTableSize;
 372         }
 373         /* Is chain field wide enough for termination pattern? */
 374         assert(pJitTable[0].u.info.chain == gDvmJit.jitTableSize);
 375
 376 done:
 377         gDvmJit.pJitEntryTable = pJitTable;
 378         gDvmJit.jitTableMask = gDvmJit.jitTableSize - 1;
 379         gDvmJit.jitTableEntriesUsed = 0;
 380         gDvmJit.pProfTableCopy = gDvmJit.pProfTable = pJitProfTable;
 381         dvmUnlockMutex(&gDvmJit.tableLock);
 382     }
 383     return res;
 384 }
 385
 386 /*
 387  * If one of our fixed tables or the translation buffer fills up,
 388  * call this routine to avoid wasting cycles on future translation requests.
 389  */
 390 void dvmJitStopTranslationRequests()
 391 {
 392     /*
 393      * Note 1: This won't necessarily stop all translation requests, and
 394      * operates on a delayed mechanism.  Running threads look to the copy
 395      * of this value in their private InterpState structures and won't see
 396      * this change until it is refreshed (which happens on interpreter
 397      * entry).
 398      * Note 2: This is a one-shot memory leak on this table. Because this is a
 399      * permanent off switch for Jit profiling, it is a one-time leak of 1K
 400      * bytes, and no further attempt will be made to re-allocate it.  Can't
 401      * free it because some thread may be holding a reference.
 402      */
 403     gDvmJit.pProfTable = gDvmJit.pProfTableCopy = NULL;
 404 }
 405
 406 #if defined(EXIT_STATS)
 407 /* Convenience function to increment counter from assembly code */
 408 void dvmBumpNoChain()
 409 {
 410     gDvm.jitNoChainExit++;
 411 }
 412
 413 /* Convenience function to increment counter from assembly code */
 414 void dvmBumpNormal()
 415 {
 416     gDvm.jitNormalExit++;
 417 }
 418
 419 /* Convenience function to increment counter from assembly code */
 420 void dvmBumpPunt(int from)
 421 {
 422     gDvm.jitPuntExit++;
 423 }
 424 #endif
 425
 426 /* Dumps debugging & tuning stats to the log */
 427 void dvmJitStats()
 428 {
 429     int i;
 430     int hit;
 431     int not_hit;
 432     int chains;
 433     if (gDvmJit.pJitEntryTable) {
 434         for (i=0, chains=hit=not_hit=0;
 435              i < (int) gDvmJit.jitTableSize;
 436              i++) {
 437             if (gDvmJit.pJitEntryTable[i].dPC != 0)
 438                 hit++;
 439             else
 440                 not_hit++;
 441             if (gDvmJit.pJitEntryTable[i].u.info.chain != gDvmJit.jitTableSize)
 442                 chains++;
 443         }
 444         LOGD(
 445          "JIT: %d traces, %d slots, %d chains, %d maxQ, %d thresh, %s",
 446          hit, not_hit + hit, chains, gDvmJit.compilerMaxQueued,
 447          gDvmJit.threshold, gDvmJit.blockingMode ? "Blocking" : "Non-blocking");
 448 #if defined(EXIT_STATS)
 449         LOGD(
 450          "JIT: Lookups: %d hits, %d misses; %d NoChain, %d normal, %d punt",
 451          gDvmJit.addrLookupsFound, gDvmJit.addrLookupsNotFound,
 452          gDvmJit.noChainExit, gDvmJit.normalExit, gDvmJit.puntExit);
 453 #endif
 454         LOGD("JIT: %d Translation chains", gDvmJit.translationChains);
 455 #if defined(INVOKE_STATS)
 456         LOGD("JIT: Invoke: %d chainable, %d pred. chain, %d native, "
 457              "%d return",
 458              gDvmJit.invokeChain, gDvmJit.invokePredictedChain,
 459              gDvmJit.invokeNative, gDvmJit.returnOp);
 460 #endif
 461         if (gDvmJit.profile) {
 462             dvmCompilerSortAndPrintTraceProfiles();
 463         }
 464     }
 465 }
 466
 467
 468 /*
 469  * Final JIT shutdown.  Only do this once, and do not attempt to restart
 470  * the JIT later.
 471  */
 472 void dvmJitShutdown(void)
 473 {
 474     /* Shutdown the compiler thread */
 475     dvmCompilerShutdown();
 476
 477     dvmCompilerDumpStats();
 478
 479     dvmDestroyMutex(&gDvmJit.tableLock);
 480
 481     if (gDvmJit.pJitEntryTable) {
 482         free(gDvmJit.pJitEntryTable);
 483         gDvmJit.pJitEntryTable = NULL;
 484     }
 485
 486     if (gDvmJit.pProfTable) {
 487         free(gDvmJit.pProfTable);
 488         gDvmJit.pProfTable = NULL;
 489     }
 490 }
 491
 492 /*
 493  * Adds to the current trace request one instruction at a time, just
 494  * before that instruction is interpreted.  This is the primary trace
 495  * selection function.  NOTE: return instruction are handled a little
 496  * differently.  In general, instructions are "proposed" to be added
 497  * to the current trace prior to interpretation.  If the interpreter
 498  * then successfully completes the instruction, is will be considered
 499  * part of the request.  This allows us to examine machine state prior
 500  * to interpretation, and also abort the trace request if the instruction
 501  * throws or does something unexpected.  However, return instructions
 502  * will cause an immediate end to the translation request - which will
 503  * be passed to the compiler before the return completes.  This is done
 504  * in response to special handling of returns by the interpreter (and
 505  * because returns cannot throw in a way that causes problems for the
 506  * translated code.
 507  */
 508 int dvmCheckJit(const u2* pc, Thread* self, InterpState* interpState)
 509 {
 510     int flags,i,len;
 511     int switchInterp = false;
 512     int debugOrProfile = (gDvm.debuggerActive || self->suspendCount
 513 #if defined(WITH_PROFILER)
 514                           || gDvm.activeProfilers
 515 #endif
 516             );
 517     /* Prepare to handle last PC and stage the current PC */
 518     const u2 *lastPC = interpState->lastPC;
 519     interpState->lastPC = pc;
 520
 521     switch (interpState->jitState) {
 522         char* nopStr;
 523         int target;
 524         int offset;
 525         DecodedInstruction decInsn;
 526         case kJitTSelect:
 527             /* First instruction - just remember the PC and exit */
 528             if (lastPC == NULL) break;
 529             /* Grow the trace around the last PC if jitState is kJitTSelect */
 530             dexDecodeInstruction(gDvm.instrFormat, lastPC, &decInsn);
 531 #if defined(SHOW_TRACE)
 532             LOGD("TraceGen: adding %s",getOpcodeName(decInsn.opCode));
 533 #endif
 534             flags = dexGetInstrFlags(gDvm.instrFlags, decInsn.opCode);
 535             len = dexGetInstrOrTableWidthAbs(gDvm.instrWidth, lastPC);
 536             offset = lastPC - interpState->method->insns;
 537             assert((unsigned) offset <
 538                    dvmGetMethodInsnsSize(interpState->method));
 539             if (lastPC != interpState->currRunHead + interpState->currRunLen) {
 540                 int currTraceRun;
 541                 /* We need to start a new trace run */
 542                 currTraceRun = ++interpState->currTraceRun;
 543                 interpState->currRunLen = 0;
 544                 interpState->currRunHead = (u2*)lastPC;
 545                 interpState->trace[currTraceRun].frag.startOffset = offset;
 546                 interpState->trace[currTraceRun].frag.numInsts = 0;
 547                 interpState->trace[currTraceRun].frag.runEnd = false;
 548                 interpState->trace[currTraceRun].frag.hint = kJitHintNone;
 549             }
 550             interpState->trace[interpState->currTraceRun].frag.numInsts++;
 551             interpState->totalTraceLen++;
 552             interpState->currRunLen += len;
 553
 554             /* Will probably never hit this with the current trace buildier */
 555             if (interpState->currTraceRun == (MAX_JIT_RUN_LEN - 1)) {
 556                 interpState->jitState = kJitTSelectEnd;
 557             }
 558
 559             if (  ((flags & kInstrUnconditional) == 0) &&
 560                   /* don't end trace on INVOKE_DIRECT_EMPTY  */
 561                   (decInsn.opCode != OP_INVOKE_DIRECT_EMPTY) &&
 562                   ((flags & (kInstrCanBranch |
 563                              kInstrCanSwitch |
 564                              kInstrCanReturn |
 565                              kInstrInvoke)) != 0)) {
 566                     interpState->jitState = kJitTSelectEnd;
 567 #if defined(SHOW_TRACE)
 568             LOGD("TraceGen: ending on %s, basic block end",
 569                  getOpcodeName(decInsn.opCode));
 570 #endif
 571             }
 572             if (decInsn.opCode == OP_THROW) {
 573                 interpState->jitState = kJitTSelectEnd;
 574             }
 575             if (interpState->totalTraceLen >= JIT_MAX_TRACE_LEN) {
 576                 interpState->jitState = kJitTSelectEnd;
 577             }
 578             if (debugOrProfile) {
 579                 interpState->jitState = kJitTSelectAbort;
 580                 switchInterp = !debugOrProfile;
 581                 break;
 582             }
 583             if ((flags & kInstrCanReturn) != kInstrCanReturn) {
 584                 break;
 585             }
 586             /* NOTE: intentional fallthrough for returns */
 587         case kJitTSelectEnd:
 588             {
 589                 if (interpState->totalTraceLen == 0) {
 590                     switchInterp = !debugOrProfile;
 591                     break;
 592                 }
 593                 JitTraceDescription* desc =
 594                    (JitTraceDescription*)malloc(sizeof(JitTraceDescription) +
 595                      sizeof(JitTraceRun) * (interpState->currTraceRun+1));
 596                 if (desc == NULL) {
 597                     LOGE("Out of memory in trace selection");
 598                     dvmJitStopTranslationRequests();
 599                     interpState->jitState = kJitTSelectAbort;
 600                     switchInterp = !debugOrProfile;
 601                     break;
 602                 }
 603                 interpState->trace[interpState->currTraceRun].frag.runEnd =
 604                      true;
 605                 interpState->jitState = kJitNormal;
 606                 desc->method = interpState->method;
 607                 memcpy((char*)&(desc->trace[0]),
 608                     (char*)&(interpState->trace[0]),
 609                     sizeof(JitTraceRun) * (interpState->currTraceRun+1));
 610 #if defined(SHOW_TRACE)
 611                 LOGD("TraceGen:  trace done, adding to queue");
 612 #endif
 613                 dvmCompilerWorkEnqueue(
 614                        interpState->currTraceHead,kWorkOrderTrace,desc);
 615                 if (gDvmJit.blockingMode) {
 616                     dvmCompilerDrainQueue();
 617                 }
 618                 switchInterp = !debugOrProfile;
 619             }
 620             break;
 621         case kJitSingleStep:
 622             interpState->jitState = kJitSingleStepEnd;
 623             break;
 624         case kJitSingleStepEnd:
 625             interpState->entryPoint = kInterpEntryResume;
 626             switchInterp = !debugOrProfile;
 627             break;
 628         case kJitTSelectAbort:
 629 #if defined(SHOW_TRACE)
 630             LOGD("TraceGen:  trace abort");
 631 #endif
 632             interpState->jitState = kJitNormal;
 633             switchInterp = !debugOrProfile;
 634             break;
 635         case kJitNormal:
 636             switchInterp = !debugOrProfile;
 637             break;
 638 #if defined(WITH_SELF_VERIFICATION)
 639         case kJitSelfVerification:
 640             if (selfVerificationDebugInterp(pc, self)) {
 641                 interpState->jitState = kJitNormal;
 642                 switchInterp = !debugOrProfile;
 643             }
 644             break;
 645 #endif
 646         /* If JIT is off stay out of interpreter selections */
 647         case kJitOff:
 648             break;
 649         default:
 650             if (!debugOrProfile) {
 651                 LOGE("Unexpected JIT state: %d", interpState->jitState);
 652                 dvmAbort();
 653             }
 654             break;
 655     }
 656     return switchInterp;
 657 }
 658
 659 static inline JitEntry *findJitEntry(const u2* pc)
 660 {
 661     int idx = dvmJitHash(pc);
 662
 663     /* Expect a high hit rate on 1st shot */
 664     if (gDvmJit.pJitEntryTable[idx].dPC == pc)
 665         return &gDvmJit.pJitEntryTable[idx];
 666     else {
 667         int chainEndMarker = gDvmJit.jitTableSize;
 668         while (gDvmJit.pJitEntryTable[idx].u.info.chain != chainEndMarker) {
 669             idx = gDvmJit.pJitEntryTable[idx].u.info.chain;
 670             if (gDvmJit.pJitEntryTable[idx].dPC == pc)
 671                 return &gDvmJit.pJitEntryTable[idx];
 672         }
 673     }
 674     return NULL;
 675 }
 676
 677 JitEntry *dvmFindJitEntry(const u2* pc)
 678 {
 679     return findJitEntry(pc);
 680 }
 681
 682 /*
 683  * If a translated code address exists for the davik byte code
 684  * pointer return it.  This routine needs to be fast.
 685  */
 686 void* dvmJitGetCodeAddr(const u2* dPC)
 687 {
 688     int idx = dvmJitHash(dPC);
 689
 690     /* If anything is suspended, don't re-enter the code cache */
 691     if (gDvm.sumThreadSuspendCount > 0) {
 692         return NULL;
 693     }
 694
 695     /* Expect a high hit rate on 1st shot */
 696     if (gDvmJit.pJitEntryTable[idx].dPC == dPC) {
 697 #if defined(EXIT_STATS)
 698         gDvmJit.addrLookupsFound++;
 699 #endif
 700         return gDvmJit.pJitEntryTable[idx].codeAddress;
 701     } else {
 702         int chainEndMarker = gDvmJit.jitTableSize;
 703         while (gDvmJit.pJitEntryTable[idx].u.info.chain != chainEndMarker) {
 704             idx = gDvmJit.pJitEntryTable[idx].u.info.chain;
 705             if (gDvmJit.pJitEntryTable[idx].dPC == dPC) {
 706 #if defined(EXIT_STATS)
 707                 gDvmJit.addrLookupsFound++;
 708 #endif
 709                 return gDvmJit.pJitEntryTable[idx].codeAddress;
 710             }
 711         }
 712     }
 713 #if defined(EXIT_STATS)
 714     gDvmJit.addrLookupsNotFound++;
 715 #endif
 716     return NULL;
 717 }
 718
 719 /*
 720  * Find an entry in the JitTable, creating if necessary.
 721  * Returns null if table is full.
 722  */
 723 JitEntry *dvmJitLookupAndAdd(const u2* dPC)
 724 {
 725     u4 chainEndMarker = gDvmJit.jitTableSize;
 726     u4 idx = dvmJitHash(dPC);
 727
 728     /* Walk the bucket chain to find an exact match for our PC */
 729     while ((gDvmJit.pJitEntryTable[idx].u.info.chain != chainEndMarker) &&
 730            (gDvmJit.pJitEntryTable[idx].dPC != dPC)) {
 731         idx = gDvmJit.pJitEntryTable[idx].u.info.chain;
 732     }
 733
 734     if (gDvmJit.pJitEntryTable[idx].dPC != dPC) {
 735         /*
 736          * No match.  Aquire jitTableLock and find the last
 737          * slot in the chain. Possibly continue the chain walk in case
 738          * some other thread allocated the slot we were looking
 739          * at previuosly (perhaps even the dPC we're trying to enter).
 740          */
 741         dvmLockMutex(&gDvmJit.tableLock);
 742         /*
 743          * At this point, if .dPC is NULL, then the slot we're
 744          * looking at is the target slot from the primary hash
 745          * (the simple, and common case).  Otherwise we're going
 746          * to have to find a free slot and chain it.
 747          */
 748         MEM_BARRIER(); /* Make sure we reload [].dPC after lock */
 749         if (gDvmJit.pJitEntryTable[idx].dPC != NULL) {
 750             u4 prev;
 751             while (gDvmJit.pJitEntryTable[idx].u.info.chain != chainEndMarker) {
 752                 if (gDvmJit.pJitEntryTable[idx].dPC == dPC) {
 753                     /* Another thread got there first for this dPC */
 754                     dvmUnlockMutex(&gDvmJit.tableLock);
 755                     return &gDvmJit.pJitEntryTable[idx];
 756                 }
 757                 idx = gDvmJit.pJitEntryTable[idx].u.info.chain;
 758             }
 759             /* Here, idx should be pointing to the last cell of an
 760              * active chain whose last member contains a valid dPC */
 761             assert(gDvmJit.pJitEntryTable[idx].dPC != NULL);
 762             /* Linear walk to find a free cell and add it to the end */
 763             prev = idx;
 764             while (true) {
 765                 idx++;
 766                 if (idx == chainEndMarker)
 767                     idx = 0;  /* Wraparound */
 768                 if ((gDvmJit.pJitEntryTable[idx].dPC == NULL) ||
 769                     (idx == prev))
 770                     break;
 771             }
 772             if (idx != prev) {
 773                 JitEntryInfoUnion oldValue;
 774                 JitEntryInfoUnion newValue;
 775                 /*
 776                  * Although we hold the lock so that noone else will
 777                  * be trying to update a chain field, the other fields
 778                  * packed into the word may be in use by other threads.
 779                  */
 780                 do {
 781                     oldValue = gDvmJit.pJitEntryTable[prev].u;
 782                     newValue = oldValue;
 783                     newValue.info.chain = idx;
 784                 } while (!ATOMIC_CMP_SWAP(
 785                          &gDvmJit.pJitEntryTable[prev].u.infoWord,
 786                          oldValue.infoWord, newValue.infoWord));
 787             }
 788         }
 789         if (gDvmJit.pJitEntryTable[idx].dPC == NULL) {
 790            /* Allocate the slot */
 791             gDvmJit.pJitEntryTable[idx].dPC = dPC;
 792             gDvmJit.jitTableEntriesUsed++;
 793         } else {
 794             /* Table is full */
 795             idx = chainEndMarker;
 796         }
 797         dvmUnlockMutex(&gDvmJit.tableLock);
 798     }
 799     return (idx == chainEndMarker) ? NULL : &gDvmJit.pJitEntryTable[idx];
 800 }
 801 /*
 802  * Register the translated code pointer into the JitTable.
 803  * NOTE: Once a codeAddress field transitions from NULL to
 804  * JIT'd code, it must not be altered without first halting all
 805  * threads.  This routine should only be called by the compiler
 806  * thread.
 807  */
 808 void dvmJitSetCodeAddr(const u2* dPC, void *nPC, JitInstructionSetType set) {
 809     JitEntryInfoUnion oldValue;
 810     JitEntryInfoUnion newValue;
 811     JitEntry *jitEntry = dvmJitLookupAndAdd(dPC);
 812     assert(jitEntry);
 813     /* Note: order of update is important */
 814     do {
 815         oldValue = jitEntry->u;
 816         newValue = oldValue;
 817         newValue.info.instructionSet = set;
 818     } while (!ATOMIC_CMP_SWAP(
 819              &jitEntry->u.infoWord,
 820              oldValue.infoWord, newValue.infoWord));
 821     jitEntry->codeAddress = nPC;
 822 }
 823
 824 /*
 825  * Determine if valid trace-bulding request is active.  Return true
 826  * if we need to abort and switch back to the fast interpreter, false
 827  * otherwise.  NOTE: may be called even when trace selection is not being
 828  * requested
 829  */
 830
 831 bool dvmJitCheckTraceRequest(Thread* self, InterpState* interpState)
 832 {
 833     bool res = false;         /* Assume success */
 834     int i;
 835     if (gDvmJit.pJitEntryTable != NULL) {
 836         /* Two-level filtering scheme */
 837         for (i=0; i< JIT_TRACE_THRESH_FILTER_SIZE; i++) {
 838             if (interpState->pc == interpState->threshFilter[i]) {
 839                 break;
 840             }
 841         }
 842         if (i == JIT_TRACE_THRESH_FILTER_SIZE) {
 843             /*
 844              * Use random replacement policy - otherwise we could miss a large
 845              * loop that contains more traces than the size of our filter array.
 846              */
 847             i = rand() % JIT_TRACE_THRESH_FILTER_SIZE;
 848             interpState->threshFilter[i] = interpState->pc;
 849             res = true;
 850         }
 851         /*
 852          * If the compiler is backlogged, or if a debugger or profiler is
 853          * active, cancel any JIT actions
 854          */
 855         if ( res || (gDvmJit.compilerQueueLength >= gDvmJit.compilerHighWater) ||
 856               gDvm.debuggerActive || self->suspendCount
 857 #if defined(WITH_PROFILER)
 858                  || gDvm.activeProfilers
 859 #endif
 860                                              ) {
 861             if (interpState->jitState != kJitOff) {
 862                 interpState->jitState = kJitNormal;
 863             }
 864         } else if (interpState->jitState == kJitTSelectRequest) {
 865             JitEntry *slot = dvmJitLookupAndAdd(interpState->pc);
 866             if (slot == NULL) {
 867                 /*
 868                  * Table is full.  This should have been
 869                  * detected by the compiler thread and the table
 870                  * resized before we run into it here.  Assume bad things
 871                  * are afoot and disable profiling.
 872                  */
 873                 interpState->jitState = kJitTSelectAbort;
 874                 LOGD("JIT: JitTable full, disabling profiling");
 875                 dvmJitStopTranslationRequests();
 876             } else if (slot->u.info.traceRequested) {
 877                 /* Trace already requested - revert to interpreter */
 878                 interpState->jitState = kJitTSelectAbort;
 879             } else {
 880                 /* Mark request */
 881                 JitEntryInfoUnion oldValue;
 882                 JitEntryInfoUnion newValue;
 883                 do {
 884                     oldValue = slot->u;
 885                     newValue = oldValue;
 886                     newValue.info.traceRequested = true;
 887                 } while (!ATOMIC_CMP_SWAP( &slot->u.infoWord,
 888                          oldValue.infoWord, newValue.infoWord));
 889             }
 890         }
 891         switch (interpState->jitState) {
 892             case kJitTSelectRequest:
 893                  interpState->jitState = kJitTSelect;
 894                  interpState->currTraceHead = interpState->pc;
 895                  interpState->currTraceRun = 0;
 896                  interpState->totalTraceLen = 0;
 897                  interpState->currRunHead = interpState->pc;
 898                  interpState->currRunLen = 0;
 899                  interpState->trace[0].frag.startOffset =
 900                        interpState->pc - interpState->method->insns;
 901                  interpState->trace[0].frag.numInsts = 0;
 902                  interpState->trace[0].frag.runEnd = false;
 903                  interpState->trace[0].frag.hint = kJitHintNone;
 904                  interpState->lastPC = 0;
 905                  break;
 906             case kJitTSelect:
 907             case kJitTSelectAbort:
 908                  res = true;
 909             case kJitSingleStep:
 910             case kJitSingleStepEnd:
 911             case kJitOff:
 912             case kJitNormal:
 913 #if defined(WITH_SELF_VERIFICATION)
 914             case kJitSelfVerification:
 915 #endif
 916                 break;
 917             default:
 918                 LOGE("Unexpected JIT state: %d", interpState->jitState);
 919                 dvmAbort();
 920         }
 921     }
 922     return res;
 923 }
 924
 925 /*
 926  * Resizes the JitTable.  Must be a power of 2, and returns true on failure.
 927  * Stops all threads, and thus is a heavyweight operation.
 928  */
 929 bool dvmJitResizeJitTable( unsigned int size )
 930 {
 931     JitEntry *pNewTable;
 932     JitEntry *pOldTable;
 933     u4 newMask;
 934     unsigned int oldSize;
 935     unsigned int i;
 936
 937     assert(gDvmJit.pJitEntryTable != NULL);
 938     assert(size && !(size & (size - 1)));   /* Is power of 2? */
 939
 940     LOGD("Jit: resizing JitTable from %d to %d", gDvmJit.jitTableSize, size);
 941
 942     newMask = size - 1;
 943
 944     if (size <= gDvmJit.jitTableSize) {
 945         return true;
 946     }
 947
 948     pNewTable = (JitEntry*)calloc(size, sizeof(*pNewTable));
 949     if (pNewTable == NULL) {
 950         return true;
 951     }
 952     for (i=0; i< size; i++) {
 953         pNewTable[i].u.info.chain = size;  /* Initialize chain termination */
 954     }
 955
 956     /* Stop all other interpreting/jit'ng threads */
 957     dvmSuspendAllThreads(SUSPEND_FOR_JIT);
 958
 959     pOldTable = gDvmJit.pJitEntryTable;
 960     oldSize = gDvmJit.jitTableSize;
 961
 962     dvmLockMutex(&gDvmJit.tableLock);
 963     gDvmJit.pJitEntryTable = pNewTable;
 964     gDvmJit.jitTableSize = size;
 965     gDvmJit.jitTableMask = size - 1;
 966     gDvmJit.jitTableEntriesUsed = 0;
 967     dvmUnlockMutex(&gDvmJit.tableLock);
 968
 969     for (i=0; i < oldSize; i++) {
 970         if (pOldTable[i].dPC) {
 971             JitEntry *p;
 972             u2 chain;
 973             p = dvmJitLookupAndAdd(pOldTable[i].dPC);
 974             p->dPC = pOldTable[i].dPC;
 975             /*
 976              * Compiler thread may have just updated the new entry's
 977              * code address field, so don't blindly copy null.
 978              */
 979             if (pOldTable[i].codeAddress != NULL) {
 980                 p->codeAddress = pOldTable[i].codeAddress;
 981             }
 982             /* We need to preserve the new chain field, but copy the rest */
 983             dvmLockMutex(&gDvmJit.tableLock);
 984             chain = p->u.info.chain;
 985             p->u = pOldTable[i].u;
 986             p->u.info.chain = chain;
 987             dvmUnlockMutex(&gDvmJit.tableLock);
 988         }
 989     }
 990
 991     free(pOldTable);
 992
 993     /* Restart the world */
 994     dvmResumeAllThreads(SUSPEND_FOR_JIT);
 995
 996     return false;
 997 }
 998
 999 /*
1000  * Float/double conversion requires clamping to min and max of integer form.  If
1001  * target doesn't support this normally, use these.
1002  */
1003 s8 dvmJitd2l(double d)
1004 {
1005     static const double kMaxLong = (double)(s8)0x7fffffffffffffffULL;
1006     static const double kMinLong = (double)(s8)0x8000000000000000ULL;
1007     if (d >= kMaxLong)
1008         return (s8)0x7fffffffffffffffULL;
1009     else if (d <= kMinLong)
1010         return (s8)0x8000000000000000ULL;
1011     else if (d != d) // NaN case
1012         return 0;
1013     else
1014         return (s8)d;
1015 }
1016
1017 s8 dvmJitf2l(float f)
1018 {
1019     static const float kMaxLong = (float)(s8)0x7fffffffffffffffULL;
1020     static const float kMinLong = (float)(s8)0x8000000000000000ULL;
1021     if (f >= kMaxLong)
1022         return (s8)0x7fffffffffffffffULL;
1023     else if (f <= kMinLong)
1024         return (s8)0x8000000000000000ULL;
1025     else if (f != f) // NaN case
1026         return 0;
1027     else
1028         return (s8)f;
1029 }
1030
1031
1032 #endif /* WITH_JIT */