Home | History | Annotate | Download | only in compiler 
      1 /*
      2  * Copyright (C) 2009 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 
     17 #include "Dalvik.h"
     18 #include "CompilerInternals.h"
     19 
     20 static ArenaMemBlock *arenaHead, *currentArena;
     21 static int numArenaBlocks;
     22 
     23 /* Allocate the initial memory block for arena-based allocation */
     24 bool dvmCompilerHeapInit(void)
     25 {
     26     assert(arenaHead == NULL);
     27     arenaHead =
     28         (ArenaMemBlock *) malloc(sizeof(ArenaMemBlock) + ARENA_DEFAULT_SIZE);
     29     if (arenaHead == NULL) {
     30         ALOGE("No memory left to create compiler heap memory");
     31         return false;
     32     }
     33     arenaHead->blockSize = ARENA_DEFAULT_SIZE;
     34     currentArena = arenaHead;
     35     currentArena->bytesAllocated = 0;
     36     currentArena->next = NULL;
     37     numArenaBlocks = 1;
     38 
     39     return true;
     40 }
     41 
     42 /* Arena-based malloc for compilation tasks */
     43 void * dvmCompilerNew(size_t size, bool zero)
     44 {
     45     size = (size + 3) & ~3;
     46 retry:
     47     /* Normal case - space is available in the current page */
     48     if (size + currentArena->bytesAllocated <= currentArena->blockSize) {
     49         void *ptr;
     50         ptr = &currentArena->ptr[currentArena->bytesAllocated];
     51         currentArena->bytesAllocated += size;
     52         if (zero) {
     53             memset(ptr, 0, size);
     54         }
     55         return ptr;
     56     } else {
     57         /*
     58          * See if there are previously allocated arena blocks before the last
     59          * reset
     60          */
     61         if (currentArena->next) {
     62             currentArena = currentArena->next;
     63             goto retry;
     64         }
     65 
     66         size_t blockSize = (size < ARENA_DEFAULT_SIZE) ?
     67                           ARENA_DEFAULT_SIZE : size;
     68         /* Time to allocate a new arena */
     69         ArenaMemBlock *newArena = (ArenaMemBlock *)
     70             malloc(sizeof(ArenaMemBlock) + blockSize);
     71         if (newArena == NULL) {
     72             ALOGE("Arena allocation failure");
     73             dvmAbort();
     74         }
     75         newArena->blockSize = blockSize;
     76         newArena->bytesAllocated = 0;
     77         newArena->next = NULL;
     78         currentArena->next = newArena;
     79         currentArena = newArena;
     80         numArenaBlocks++;
     81         if (numArenaBlocks > 10)
     82             ALOGI("Total arena pages for JIT: %d", numArenaBlocks);
     83         goto retry;
     84     }
     85     /* Should not reach here */
     86     dvmAbort();
     87 }
     88 
     89 /* Reclaim all the arena blocks allocated so far */
     90 void dvmCompilerArenaReset(void)
     91 {
     92     ArenaMemBlock *block;
     93 
     94     for (block = arenaHead; block; block = block->next) {
     95         block->bytesAllocated = 0;
     96     }
     97     currentArena = arenaHead;
     98 }
     99 
    100 /* Growable List initialization */
    101 void dvmInitGrowableList(GrowableList *gList, size_t initLength)
    102 {
    103     gList->numAllocated = initLength;
    104     gList->numUsed = 0;
    105     gList->elemList = (intptr_t *) dvmCompilerNew(sizeof(intptr_t) * initLength,
    106                                                   true);
    107 }
    108 
    109 /* Expand the capacity of a growable list */
    110 static void expandGrowableList(GrowableList *gList)
    111 {
    112     int newLength = gList->numAllocated;
    113     if (newLength < 128) {
    114         newLength <<= 1;
    115     } else {
    116         newLength += 128;
    117     }
    118     intptr_t *newArray =
    119         (intptr_t *) dvmCompilerNew(sizeof(intptr_t) * newLength, true);
    120     memcpy(newArray, gList->elemList, sizeof(intptr_t) * gList->numAllocated);
    121     gList->numAllocated = newLength;
    122     gList->elemList = newArray;
    123 }
    124 
    125 /* Insert a new element into the growable list */
    126 void dvmInsertGrowableList(GrowableList *gList, intptr_t elem)
    127 {
    128     assert(gList->numAllocated != 0);
    129     if (gList->numUsed == gList->numAllocated) {
    130         expandGrowableList(gList);
    131     }
    132     gList->elemList[gList->numUsed++] = elem;
    133 }
    134 
    135 void dvmGrowableListIteratorInit(GrowableList *gList,
    136                                  GrowableListIterator *iterator)
    137 {
    138     iterator->list = gList;
    139     iterator->idx = 0;
    140     iterator->size = gList->numUsed;
    141 }
    142 
    143 intptr_t dvmGrowableListIteratorNext(GrowableListIterator *iterator)
    144 {
    145     assert(iterator->size == iterator->list->numUsed);
    146     if (iterator->idx == iterator->size) return 0;
    147     return iterator->list->elemList[iterator->idx++];
    148 }
    149 
    150 intptr_t dvmGrowableListGetElement(const GrowableList *gList, size_t idx)
    151 {
    152     assert(idx < gList->numUsed);
    153     return gList->elemList[idx];
    154 }
    155 
    156 /* Debug Utility - dump a compilation unit */
    157 void dvmCompilerDumpCompilationUnit(CompilationUnit *cUnit)
    158 {
    159     BasicBlock *bb;
    160     const char *blockTypeNames[] = {
    161         "Normal Chaining Cell",
    162         "Hot Chaining Cell",
    163         "Singleton Chaining Cell",
    164         "Predicted Chaining Cell",
    165         "Backward Branch",
    166         "Chaining Cell Gap",
    167         "N/A",
    168         "Entry Block",
    169         "Code Block",
    170         "Exit Block",
    171         "PC Reconstruction",
    172         "Exception Handling",
    173     };
    174 
    175     ALOGD("Compiling %s %s", cUnit->method->clazz->descriptor,
    176          cUnit->method->name);
    177     ALOGD("%d insns", dvmGetMethodInsnsSize(cUnit->method));
    178     ALOGD("%d blocks in total", cUnit->numBlocks);
    179     GrowableListIterator iterator;
    180 
    181     dvmGrowableListIteratorInit(&cUnit->blockList, &iterator);
    182 
    183     while (true) {
    184         bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
    185         if (bb == NULL) break;
    186         ALOGD("Block %d (%s) (insn %04x - %04x%s)",
    187              bb->id,
    188              blockTypeNames[bb->blockType],
    189              bb->startOffset,
    190              bb->lastMIRInsn ? bb->lastMIRInsn->offset : bb->startOffset,
    191              bb->lastMIRInsn ? "" : " empty");
    192         if (bb->taken) {
    193             ALOGD("  Taken branch: block %d (%04x)",
    194                  bb->taken->id, bb->taken->startOffset);
    195         }
    196         if (bb->fallThrough) {
    197             ALOGD("  Fallthrough : block %d (%04x)",
    198                  bb->fallThrough->id, bb->fallThrough->startOffset);
    199         }
    200     }
    201 }
    202 
    203 /*
    204  * dvmHashForeach callback.
    205  */
    206 static int dumpMethodStats(void *compilerMethodStats, void *totalMethodStats)
    207 {
    208     CompilerMethodStats *methodStats =
    209         (CompilerMethodStats *) compilerMethodStats;
    210     CompilerMethodStats *totalStats =
    211         (CompilerMethodStats *) totalMethodStats;
    212 
    213     totalStats->dalvikSize += methodStats->dalvikSize;
    214     totalStats->compiledDalvikSize += methodStats->compiledDalvikSize;
    215     totalStats->nativeSize += methodStats->nativeSize;
    216 
    217     /* Enable the following when fine-tuning the JIT performance */
    218 #if 0
    219     int limit = (methodStats->dalvikSize >> 2) * 3;
    220 
    221     /* If over 3/4 of the Dalvik code is compiled, print something */
    222     if (methodStats->compiledDalvikSize >= limit) {
    223         ALOGD("Method stats: %s%s, %d/%d (compiled/total Dalvik), %d (native)",
    224              methodStats->method->clazz->descriptor,
    225              methodStats->method->name,
    226              methodStats->compiledDalvikSize,
    227              methodStats->dalvikSize,
    228              methodStats->nativeSize);
    229     }
    230 #endif
    231     return 0;
    232 }
    233 
    234 /*
    235  * Dump the current stats of the compiler, including number of bytes used in
    236  * the code cache, arena size, and work queue length, and various JIT stats.
    237  */
    238 void dvmCompilerDumpStats(void)
    239 {
    240     CompilerMethodStats totalMethodStats;
    241 
    242     memset(&totalMethodStats, 0, sizeof(CompilerMethodStats));
    243     ALOGD("%d compilations using %d + %d bytes",
    244          gDvmJit.numCompilations,
    245          gDvmJit.templateSize,
    246          gDvmJit.codeCacheByteUsed - gDvmJit.templateSize);
    247     ALOGD("Compiler arena uses %d blocks (%d bytes each)",
    248          numArenaBlocks, ARENA_DEFAULT_SIZE);
    249     ALOGD("Compiler work queue length is %d/%d", gDvmJit.compilerQueueLength,
    250          gDvmJit.compilerMaxQueued);
    251     dvmJitStats();
    252     dvmCompilerArchDump();
    253     if (gDvmJit.methodStatsTable) {
    254         dvmHashForeach(gDvmJit.methodStatsTable, dumpMethodStats,
    255                        &totalMethodStats);
    256         ALOGD("Code size stats: %d/%d (compiled/total Dalvik), %d (native)",
    257              totalMethodStats.compiledDalvikSize,
    258              totalMethodStats.dalvikSize,
    259              totalMethodStats.nativeSize);
    260     }
    261 }
    262 
    263 /*
    264  * Allocate a bit vector with enough space to hold at least the specified
    265  * number of bits.
    266  *
    267  * NOTE: this is the sister implementation of dvmAllocBitVector. In this version
    268  * memory is allocated from the compiler arena.
    269  */
    270 BitVector* dvmCompilerAllocBitVector(unsigned int startBits, bool expandable)
    271 {
    272     BitVector* bv;
    273     unsigned int count;
    274 
    275     assert(sizeof(bv->storage[0]) == 4);        /* assuming 32-bit units */
    276 
    277     bv = (BitVector*) dvmCompilerNew(sizeof(BitVector), false);
    278 
    279     count = (startBits + 31) >> 5;
    280 
    281     bv->storageSize = count;
    282     bv->expandable = expandable;
    283     bv->storage = (u4*) dvmCompilerNew(count * sizeof(u4), true);
    284     return bv;
    285 }
    286 
    287 /*
    288  * Mark the specified bit as "set".
    289  *
    290  * Returns "false" if the bit is outside the range of the vector and we're
    291  * not allowed to expand.
    292  *
    293  * NOTE: this is the sister implementation of dvmSetBit. In this version
    294  * memory is allocated from the compiler arena.
    295  */
    296 bool dvmCompilerSetBit(BitVector *pBits, unsigned int num)
    297 {
    298     if (num >= pBits->storageSize * sizeof(u4) * 8) {
    299         if (!pBits->expandable)
    300             dvmAbort();
    301 
    302         /* Round up to word boundaries for "num+1" bits */
    303         unsigned int newSize = (num + 1 + 31) >> 5;
    304         assert(newSize > pBits->storageSize);
    305         u4 *newStorage = (u4*)dvmCompilerNew(newSize * sizeof(u4), false);
    306         memcpy(newStorage, pBits->storage, pBits->storageSize * sizeof(u4));
    307         memset(&newStorage[pBits->storageSize], 0,
    308                (newSize - pBits->storageSize) * sizeof(u4));
    309         pBits->storage = newStorage;
    310         pBits->storageSize = newSize;
    311     }
    312 
    313     pBits->storage[num >> 5] |= 1 << (num & 0x1f);
    314     return true;
    315 }
    316 
    317 /*
    318  * Mark the specified bit as "unset".
    319  *
    320  * Returns "false" if the bit is outside the range of the vector and we're
    321  * not allowed to expand.
    322  *
    323  * NOTE: this is the sister implementation of dvmClearBit. In this version
    324  * memory is allocated from the compiler arena.
    325  */
    326 bool dvmCompilerClearBit(BitVector *pBits, unsigned int num)
    327 {
    328     if (num >= pBits->storageSize * sizeof(u4) * 8) {
    329         ALOGE("Trying to clear a bit that is not set in the vector yet!");
    330         dvmAbort();
    331     }
    332 
    333     pBits->storage[num >> 5] &= ~(1 << (num & 0x1f));
    334     return true;
    335 }
    336 
    337 /*
    338  * If set is true, mark all bits as 1. Otherwise mark all bits as 0.
    339  */
    340 void dvmCompilerMarkAllBits(BitVector *pBits, bool set)
    341 {
    342     int value = set ? -1 : 0;
    343     memset(pBits->storage, value, pBits->storageSize * (int)sizeof(u4));
    344 }
    345 
    346 void dvmDebugBitVector(char *msg, const BitVector *bv, int length)
    347 {
    348     int i;
    349 
    350     ALOGE("%s", msg);
    351     for (i = 0; i < length; i++) {
    352         if (dvmIsBitSet(bv, i)) {
    353             ALOGE("    Bit %d is set", i);
    354         }
    355     }
    356 }
    357 
    358 void dvmCompilerAbort(CompilationUnit *cUnit)
    359 {
    360     ALOGE("Jit: aborting trace compilation, reverting to interpreter");
    361     /* Force a traceback in debug builds */
    362     assert(0);
    363     /*
    364      * Abort translation and force to interpret-only for this trace
    365      * Matching setjmp in compiler thread work loop in Compiler.c.
    366      */
    367     longjmp(*cUnit->bailPtr, 1);
    368 }
    369 
    370 void dvmDumpBlockBitVector(const GrowableList *blocks, char *msg,
    371                            const BitVector *bv, int length)
    372 {
    373     int i;
    374 
    375     ALOGE("%s", msg);
    376     for (i = 0; i < length; i++) {
    377         if (dvmIsBitSet(bv, i)) {
    378             BasicBlock *bb =
    379                 (BasicBlock *) dvmGrowableListGetElement(blocks, i);
    380             char blockName[BLOCK_NAME_LEN];
    381             dvmGetBlockName(bb, blockName);
    382             ALOGE("Bit %d / %s is set", i, blockName);
    383         }
    384     }
    385 }
    386 
    387 void dvmGetBlockName(BasicBlock *bb, char *name)
    388 {
    389     switch (bb->blockType) {
    390         case kEntryBlock:
    391             snprintf(name, BLOCK_NAME_LEN, "entry");
    392             break;
    393         case kExitBlock:
    394             snprintf(name, BLOCK_NAME_LEN, "exit");
    395             break;
    396         case kDalvikByteCode:
    397             snprintf(name, BLOCK_NAME_LEN, "block%04x", bb->startOffset);
    398             break;
    399         case kChainingCellNormal:
    400             snprintf(name, BLOCK_NAME_LEN, "chain%04x", bb->startOffset);
    401             break;
    402         case kExceptionHandling:
    403             snprintf(name, BLOCK_NAME_LEN, "exception%04x", bb->startOffset);
    404             break;
    405         default:
    406             snprintf(name, BLOCK_NAME_LEN, "??");
    407             break;
    408     }
    409 }
    410