Utility.cpp revision 062bf509a77fce9dfcb7e7b2e401cf2a124d83d5 
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
20static ArenaMemBlock *arenaHead, *currentArena;
21static int numArenaBlocks;
22
23/* Allocate the initial memory block for arena-based allocation */
24bool dvmCompilerHeapInit(void)
25{
26    assert(arenaHead == NULL);
27    arenaHead =
28        (ArenaMemBlock *) malloc(sizeof(ArenaMemBlock) + ARENA_DEFAULT_SIZE);
29    if (arenaHead == NULL) {
30        LOGE("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 */
43void * dvmCompilerNew(size_t size, bool zero)
44{
45    size = (size + 3) & ~3;
46retry:
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            LOGE("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            LOGI("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 */
90void 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 */
101void 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 */
110static 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 */
126void 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
135void dvmGrowableListIteratorInit(GrowableList *gList,
136                                 GrowableListIterator *iterator)
137{
138    iterator->list = gList;
139    iterator->idx = 0;
140    iterator->size = gList->numUsed;
141}
142
143intptr_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
150intptr_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 */
157void 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 */
206static 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 */
238void 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 */
270BitVector* 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 */
296bool 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 */
326bool dvmCompilerClearBit(BitVector *pBits, unsigned int num)
327{
328    if (num >= pBits->storageSize * sizeof(u4) * 8) {
329        LOGE("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 */
340void dvmCompilerMarkAllBits(BitVector *pBits, bool set)
341{
342    int value = set ? -1 : 0;
343    memset(pBits->storage, value, pBits->storageSize * (int)sizeof(u4));
344}
345
346void dvmDebugBitVector(char *msg, const BitVector *bv, int length)
347{
348    int i;
349
350    LOGE("%s", msg);
351    for (i = 0; i < length; i++) {
352        if (dvmIsBitSet(bv, i)) {
353            LOGE("    Bit %d is set", i);
354        }
355    }
356}
357
358void dvmCompilerAbort(CompilationUnit *cUnit)
359{
360    LOGE("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
370void dvmDumpBlockBitVector(const GrowableList *blocks, char *msg,
371                           const BitVector *bv, int length)
372{
373    int i;
374
375    LOGE("%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            LOGE("Bit %d / %s is set", i, blockName);
383        }
384    }
385}
386
387void 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