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 "libdex/OpCode.h"
19#include "interp/Jit.h"
20#include "CompilerInternals.h"
21
22/*
23 * Parse an instruction, return the length of the instruction
24 */
25static inline int parseInsn(const u2 *codePtr, DecodedInstruction *decInsn,
26                            bool printMe)
27{
28    u2 instr = *codePtr;
29    OpCode opcode = instr & 0xff;
30    int insnWidth;
31
32    // Don't parse instruction data
33    if (opcode == OP_NOP && instr != 0) {
34        return 0;
35    } else {
36        insnWidth = gDvm.instrWidth[opcode];
37        if (insnWidth < 0) {
38            insnWidth = -insnWidth;
39        }
40    }
41
42    dexDecodeInstruction(gDvm.instrFormat, codePtr, decInsn);
43    if (printMe) {
44        char *decodedString = dvmCompilerGetDalvikDisassembly(decInsn);
45        LOGD("%p: %#06x %s\n", codePtr, opcode, decodedString);
46    }
47    return insnWidth;
48}
49
50#define UNKNOWN_TARGET 0xffffffff
51
52/*
53 * Identify block-ending instructions and collect supplemental information
54 * regarding the following instructions.
55 */
56static inline bool findBlockBoundary(const Method *caller, MIR *insn,
57                                     unsigned int curOffset,
58                                     unsigned int *target, bool *isInvoke,
59                                     const Method **callee)
60{
61    switch (insn->dalvikInsn.opCode) {
62        /* Target is not compile-time constant */
63        case OP_RETURN_VOID:
64        case OP_RETURN:
65        case OP_RETURN_WIDE:
66        case OP_RETURN_OBJECT:
67        case OP_THROW:
68          *target = UNKNOWN_TARGET;
69          break;
70        case OP_INVOKE_VIRTUAL:
71        case OP_INVOKE_VIRTUAL_RANGE:
72        case OP_INVOKE_INTERFACE:
73        case OP_INVOKE_INTERFACE_RANGE:
74        case OP_INVOKE_VIRTUAL_QUICK:
75        case OP_INVOKE_VIRTUAL_QUICK_RANGE:
76            *isInvoke = true;
77            break;
78        case OP_INVOKE_SUPER:
79        case OP_INVOKE_SUPER_RANGE: {
80            int mIndex = caller->clazz->pDvmDex->
81                pResMethods[insn->dalvikInsn.vB]->methodIndex;
82            const Method *calleeMethod =
83                caller->clazz->super->vtable[mIndex];
84
85            if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
86                *target = (unsigned int) calleeMethod->insns;
87            }
88            *isInvoke = true;
89            *callee = calleeMethod;
90            break;
91        }
92        case OP_INVOKE_STATIC:
93        case OP_INVOKE_STATIC_RANGE: {
94            const Method *calleeMethod =
95                caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
96
97            if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
98                *target = (unsigned int) calleeMethod->insns;
99            }
100            *isInvoke = true;
101            *callee = calleeMethod;
102            break;
103        }
104        case OP_INVOKE_SUPER_QUICK:
105        case OP_INVOKE_SUPER_QUICK_RANGE: {
106            const Method *calleeMethod =
107                caller->clazz->super->vtable[insn->dalvikInsn.vB];
108
109            if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
110                *target = (unsigned int) calleeMethod->insns;
111            }
112            *isInvoke = true;
113            *callee = calleeMethod;
114            break;
115        }
116        case OP_INVOKE_DIRECT:
117        case OP_INVOKE_DIRECT_RANGE: {
118            const Method *calleeMethod =
119                caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
120            if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
121                *target = (unsigned int) calleeMethod->insns;
122            }
123            *isInvoke = true;
124            *callee = calleeMethod;
125            break;
126        }
127        case OP_GOTO:
128        case OP_GOTO_16:
129        case OP_GOTO_32:
130            *target = curOffset + (int) insn->dalvikInsn.vA;
131            break;
132
133        case OP_IF_EQ:
134        case OP_IF_NE:
135        case OP_IF_LT:
136        case OP_IF_GE:
137        case OP_IF_GT:
138        case OP_IF_LE:
139            *target = curOffset + (int) insn->dalvikInsn.vC;
140            break;
141
142        case OP_IF_EQZ:
143        case OP_IF_NEZ:
144        case OP_IF_LTZ:
145        case OP_IF_GEZ:
146        case OP_IF_GTZ:
147        case OP_IF_LEZ:
148            *target = curOffset + (int) insn->dalvikInsn.vB;
149            break;
150
151        default:
152            return false;
153    }
154    return true;
155}
156
157static inline bool isGoto(MIR *insn)
158{
159    switch (insn->dalvikInsn.opCode) {
160        case OP_GOTO:
161        case OP_GOTO_16:
162        case OP_GOTO_32:
163            return true;
164        default:
165            return false;
166    }
167}
168
169/*
170 * Identify unconditional branch instructions
171 */
172static inline bool isUnconditionalBranch(MIR *insn)
173{
174    switch (insn->dalvikInsn.opCode) {
175        case OP_RETURN_VOID:
176        case OP_RETURN:
177        case OP_RETURN_WIDE:
178        case OP_RETURN_OBJECT:
179            return true;
180        default:
181            return isGoto(insn);
182    }
183}
184
185/*
186 * dvmHashTableLookup() callback
187 */
188static int compareMethod(const CompilerMethodStats *m1,
189                         const CompilerMethodStats *m2)
190{
191    return (int) m1->method - (int) m2->method;
192}
193
194#if defined(WITH_JIT_TUNING)
195/*
196 * Analyze each method whose traces are ever compiled. Collect a variety of
197 * statistics like the ratio of exercised vs overall code and code bloat
198 * ratios.
199 */
200static CompilerMethodStats *analyzeMethodBody(const Method *method)
201{
202    const DexCode *dexCode = dvmGetMethodCode(method);
203    const u2 *codePtr = dexCode->insns;
204    const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
205    int insnSize = 0;
206    int hashValue = dvmComputeUtf8Hash(method->name);
207
208    CompilerMethodStats dummyMethodEntry; // For hash table lookup
209    CompilerMethodStats *realMethodEntry; // For hash table storage
210
211    /* For lookup only */
212    dummyMethodEntry.method = method;
213    realMethodEntry = dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
214                                         &dummyMethodEntry,
215                                         (HashCompareFunc) compareMethod,
216                                         false);
217
218    /* Part of this method has been compiled before - just return the entry */
219    if (realMethodEntry != NULL) {
220        return realMethodEntry;
221    }
222
223    /*
224     * First time to compile this method - set up a new entry in the hash table
225     */
226    realMethodEntry =
227        (CompilerMethodStats *) calloc(1, sizeof(CompilerMethodStats));
228    realMethodEntry->method = method;
229
230    dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
231                       realMethodEntry,
232                       (HashCompareFunc) compareMethod,
233                       true);
234
235    /* Count the number of instructions */
236    while (codePtr < codeEnd) {
237        DecodedInstruction dalvikInsn;
238        int width = parseInsn(codePtr, &dalvikInsn, false);
239
240        /* Terminate when the data section is seen */
241        if (width == 0)
242            break;
243
244        insnSize += width;
245        codePtr += width;
246    }
247
248    realMethodEntry->dalvikSize = insnSize * 2;
249    return realMethodEntry;
250}
251#endif
252
253/*
254 * Crawl the stack of the thread that requesed compilation to see if any of the
255 * ancestors are on the blacklist.
256 */
257bool filterMethodByCallGraph(Thread *thread, const char *curMethodName)
258{
259    /* Crawl the Dalvik stack frames and compare the method name*/
260    StackSaveArea *ssaPtr = ((StackSaveArea *) thread->curFrame) - 1;
261    while (ssaPtr != ((StackSaveArea *) NULL) - 1) {
262        const Method *method = ssaPtr->method;
263        if (method) {
264            int hashValue = dvmComputeUtf8Hash(method->name);
265            bool found =
266                dvmHashTableLookup(gDvmJit.methodTable, hashValue,
267                               (char *) method->name,
268                               (HashCompareFunc) strcmp, false) !=
269                NULL;
270            if (found) {
271                LOGD("Method %s (--> %s) found on the JIT %s list",
272                     method->name, curMethodName,
273                     gDvmJit.includeSelectedMethod ? "white" : "black");
274                return true;
275            }
276
277        }
278        ssaPtr = ((StackSaveArea *) ssaPtr->prevFrame) - 1;
279    };
280    return false;
281}
282
283/*
284 * Main entry point to start trace compilation. Basic blocks are constructed
285 * first and they will be passed to the codegen routines to convert Dalvik
286 * bytecode into machine code.
287 */
288bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts,
289                     JitTranslationInfo *info, jmp_buf *bailPtr)
290{
291    const DexCode *dexCode = dvmGetMethodCode(desc->method);
292    const JitTraceRun* currRun = &desc->trace[0];
293    unsigned int curOffset = currRun->frag.startOffset;
294    unsigned int numInsts = currRun->frag.numInsts;
295    const u2 *codePtr = dexCode->insns + curOffset;
296    int traceSize = 0;  // # of half-words
297    const u2 *startCodePtr = codePtr;
298    BasicBlock *startBB, *curBB, *lastBB;
299    int numBlocks = 0;
300    static int compilationId;
301    CompilationUnit cUnit;
302#if defined(WITH_JIT_TUNING)
303    CompilerMethodStats *methodStats;
304#endif
305
306    /* If we've already compiled this trace, just return success */
307    if (dvmJitGetCodeAddr(startCodePtr) && !info->discardResult) {
308        return true;
309    }
310
311    compilationId++;
312    memset(&cUnit, 0, sizeof(CompilationUnit));
313
314#if defined(WITH_JIT_TUNING)
315    /* Locate the entry to store compilation statistics for this method */
316    methodStats = analyzeMethodBody(desc->method);
317#endif
318
319    /* Set the recover buffer pointer */
320    cUnit.bailPtr = bailPtr;
321
322    /* Initialize the printMe flag */
323    cUnit.printMe = gDvmJit.printMe;
324
325    /* Initialize the profile flag */
326    cUnit.executionCount = gDvmJit.profile;
327
328    /* Identify traces that we don't want to compile */
329    if (gDvmJit.methodTable) {
330        int len = strlen(desc->method->clazz->descriptor) +
331                  strlen(desc->method->name) + 1;
332        char *fullSignature = dvmCompilerNew(len, true);
333        strcpy(fullSignature, desc->method->clazz->descriptor);
334        strcat(fullSignature, desc->method->name);
335
336        int hashValue = dvmComputeUtf8Hash(fullSignature);
337
338        /*
339         * Doing three levels of screening to see whether we want to skip
340         * compiling this method
341         */
342
343        /* First, check the full "class;method" signature */
344        bool methodFound =
345            dvmHashTableLookup(gDvmJit.methodTable, hashValue,
346                               fullSignature, (HashCompareFunc) strcmp,
347                               false) !=
348            NULL;
349
350        /* Full signature not found - check the enclosing class */
351        if (methodFound == false) {
352            int hashValue = dvmComputeUtf8Hash(desc->method->clazz->descriptor);
353            methodFound =
354                dvmHashTableLookup(gDvmJit.methodTable, hashValue,
355                               (char *) desc->method->clazz->descriptor,
356                               (HashCompareFunc) strcmp, false) !=
357                NULL;
358            /* Enclosing class not found - check the method name */
359            if (methodFound == false) {
360                int hashValue = dvmComputeUtf8Hash(desc->method->name);
361                methodFound =
362                    dvmHashTableLookup(gDvmJit.methodTable, hashValue,
363                                   (char *) desc->method->name,
364                                   (HashCompareFunc) strcmp, false) !=
365                    NULL;
366
367                /*
368                 * Debug by call-graph is enabled. Check if the debug list
369                 * covers any methods on the VM stack.
370                 */
371                if (methodFound == false && gDvmJit.checkCallGraph == true) {
372                    methodFound =
373                        filterMethodByCallGraph(info->requestingThread,
374                                                desc->method->name);
375                }
376            }
377        }
378
379        /*
380         * Under the following conditions, the trace will be *conservatively*
381         * compiled by only containing single-step instructions to and from the
382         * interpreter.
383         * 1) If includeSelectedMethod == false, the method matches the full or
384         *    partial signature stored in the hash table.
385         *
386         * 2) If includeSelectedMethod == true, the method does not match the
387         *    full and partial signature stored in the hash table.
388         */
389        if (gDvmJit.includeSelectedMethod != methodFound) {
390            cUnit.allSingleStep = true;
391        } else {
392            /* Compile the trace as normal */
393
394            /* Print the method we cherry picked */
395            if (gDvmJit.includeSelectedMethod == true) {
396                cUnit.printMe = true;
397            }
398        }
399    }
400
401    /* Allocate the entry block */
402    lastBB = startBB = curBB = dvmCompilerNewBB(kEntryBlock);
403    curBB->startOffset = curOffset;
404    curBB->id = numBlocks++;
405
406    curBB = dvmCompilerNewBB(kDalvikByteCode);
407    curBB->startOffset = curOffset;
408    curBB->id = numBlocks++;
409
410    /* Make the first real dalvik block the fallthrough of the entry block */
411    startBB->fallThrough = curBB;
412    lastBB->next = curBB;
413    lastBB = curBB;
414
415    if (cUnit.printMe) {
416        LOGD("--------\nCompiler: Building trace for %s, offset 0x%x\n",
417             desc->method->name, curOffset);
418    }
419
420    /*
421     * Analyze the trace descriptor and include up to the maximal number
422     * of Dalvik instructions into the IR.
423     */
424    while (1) {
425        MIR *insn;
426        int width;
427        insn = dvmCompilerNew(sizeof(MIR), true);
428        insn->offset = curOffset;
429        width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe);
430
431        /* The trace should never incude instruction data */
432        assert(width);
433        insn->width = width;
434        traceSize += width;
435        dvmCompilerAppendMIR(curBB, insn);
436        cUnit.numInsts++;
437        /* Instruction limit reached - terminate the trace here */
438        if (cUnit.numInsts >= numMaxInsts) {
439            break;
440        }
441        if (--numInsts == 0) {
442            if (currRun->frag.runEnd) {
443                break;
444            } else {
445                curBB = dvmCompilerNewBB(kDalvikByteCode);
446                lastBB->next = curBB;
447                lastBB = curBB;
448                curBB->id = numBlocks++;
449                currRun++;
450                curOffset = currRun->frag.startOffset;
451                numInsts = currRun->frag.numInsts;
452                curBB->startOffset = curOffset;
453                codePtr = dexCode->insns + curOffset;
454            }
455        } else {
456            curOffset += width;
457            codePtr += width;
458        }
459    }
460
461#if defined(WITH_JIT_TUNING)
462    /* Convert # of half-word to bytes */
463    methodStats->compiledDalvikSize += traceSize * 2;
464#endif
465
466    /*
467     * Now scan basic blocks containing real code to connect the
468     * taken/fallthrough links. Also create chaining cells for code not included
469     * in the trace.
470     */
471    for (curBB = startBB; curBB; curBB = curBB->next) {
472        MIR *lastInsn = curBB->lastMIRInsn;
473        /* Skip empty blocks */
474        if (lastInsn == NULL) {
475            continue;
476        }
477        curOffset = lastInsn->offset;
478        unsigned int targetOffset = curOffset;
479        unsigned int fallThroughOffset = curOffset + lastInsn->width;
480        bool isInvoke = false;
481        const Method *callee = NULL;
482
483        findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset,
484                          &targetOffset, &isInvoke, &callee);
485
486        /* Link the taken and fallthrough blocks */
487        BasicBlock *searchBB;
488
489        /* No backward branch in the trace - start searching the next BB */
490        for (searchBB = curBB->next; searchBB; searchBB = searchBB->next) {
491            if (targetOffset == searchBB->startOffset) {
492                curBB->taken = searchBB;
493            }
494            if (fallThroughOffset == searchBB->startOffset) {
495                curBB->fallThrough = searchBB;
496            }
497        }
498
499        int flags = dexGetInstrFlags(gDvm.instrFlags,
500                                     lastInsn->dalvikInsn.opCode);
501
502        /*
503         * Some blocks are ended by non-control-flow-change instructions,
504         * currently only due to trace length constraint. In this case we need
505         * to generate an explicit branch at the end of the block to jump to
506         * the chaining cell.
507         *
508         * NOTE: INVOKE_DIRECT_EMPTY is actually not an invoke but a nop
509         */
510        curBB->needFallThroughBranch =
511            ((flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
512                       kInstrInvoke)) == 0) ||
513            (lastInsn->dalvikInsn.opCode == OP_INVOKE_DIRECT_EMPTY);
514
515        if (curBB->taken == NULL &&
516            curBB->fallThrough == NULL &&
517            flags == (kInstrCanBranch | kInstrCanContinue) &&
518            fallThroughOffset == startBB->startOffset) {
519            BasicBlock *loopBranch = curBB;
520            BasicBlock *exitBB;
521            BasicBlock *exitChainingCell;
522
523            if (cUnit.printMe) {
524                LOGD("Natural loop detected!");
525            }
526            exitBB = dvmCompilerNewBB(kExitBlock);
527            lastBB->next = exitBB;
528            lastBB = exitBB;
529
530            exitBB->startOffset = targetOffset;
531            exitBB->id = numBlocks++;
532            exitBB->needFallThroughBranch = true;
533
534            loopBranch->taken = exitBB;
535#if defined(WITH_SELF_VERIFICATION)
536            BasicBlock *backwardCell =
537                dvmCompilerNewBB(kChainingCellBackwardBranch);
538            lastBB->next = backwardCell;
539            lastBB = backwardCell;
540
541            backwardCell->startOffset = startBB->startOffset;
542            backwardCell->id = numBlocks++;
543            loopBranch->fallThrough = backwardCell;
544#elif defined(WITH_JIT_TUNING)
545            if (gDvmJit.profile) {
546                BasicBlock *backwardCell =
547                    dvmCompilerNewBB(kChainingCellBackwardBranch);
548                lastBB->next = backwardCell;
549                lastBB = backwardCell;
550
551                backwardCell->startOffset = startBB->startOffset;
552                backwardCell->id = numBlocks++;
553                loopBranch->fallThrough = backwardCell;
554            } else {
555                loopBranch->fallThrough = startBB->next;
556            }
557#else
558            loopBranch->fallThrough = startBB->next;
559#endif
560
561            /* Create the chaining cell as the fallthrough of the exit block */
562            exitChainingCell = dvmCompilerNewBB(kChainingCellNormal);
563            lastBB->next = exitChainingCell;
564            lastBB = exitChainingCell;
565
566            exitChainingCell->startOffset = targetOffset;
567            exitChainingCell->id = numBlocks++;
568
569            exitBB->fallThrough = exitChainingCell;
570
571            cUnit.hasLoop = true;
572        }
573
574        if (lastInsn->dalvikInsn.opCode == OP_PACKED_SWITCH ||
575            lastInsn->dalvikInsn.opCode == OP_SPARSE_SWITCH) {
576            int i;
577            const u2 *switchData = desc->method->insns + lastInsn->offset +
578                             lastInsn->dalvikInsn.vB;
579            int size = switchData[1];
580            int maxChains = MIN(size, MAX_CHAINED_SWITCH_CASES);
581
582            /*
583             * Generate the landing pad for cases whose ranks are higher than
584             * MAX_CHAINED_SWITCH_CASES. The code will re-enter the interpreter
585             * through the NoChain point.
586             */
587            if (maxChains != size) {
588                cUnit.switchOverflowPad =
589                    desc->method->insns + lastInsn->offset;
590            }
591
592            s4 *targets = (s4 *) (switchData + 2 +
593                    (lastInsn->dalvikInsn.opCode == OP_PACKED_SWITCH ?
594                     2 : size * 2));
595
596            /* One chaining cell for the first MAX_CHAINED_SWITCH_CASES cases */
597            for (i = 0; i < maxChains; i++) {
598                BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
599                lastBB->next = caseChain;
600                lastBB = caseChain;
601
602                caseChain->startOffset = lastInsn->offset + targets[i];
603                caseChain->id = numBlocks++;
604            }
605
606            /* One more chaining cell for the default case */
607            BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
608            lastBB->next = caseChain;
609            lastBB = caseChain;
610
611            caseChain->startOffset = lastInsn->offset + lastInsn->width;
612            caseChain->id = numBlocks++;
613        /* Fallthrough block not included in the trace */
614        } else if (!isUnconditionalBranch(lastInsn) &&
615                   curBB->fallThrough == NULL) {
616            /*
617             * If the chaining cell is after an invoke or
618             * instruction that cannot change the control flow, request a hot
619             * chaining cell.
620             */
621            if (isInvoke || curBB->needFallThroughBranch) {
622                lastBB->next = dvmCompilerNewBB(kChainingCellHot);
623            } else {
624                lastBB->next = dvmCompilerNewBB(kChainingCellNormal);
625            }
626            lastBB = lastBB->next;
627            lastBB->id = numBlocks++;
628            lastBB->startOffset = fallThroughOffset;
629            curBB->fallThrough = lastBB;
630        }
631        /* Target block not included in the trace */
632        if (curBB->taken == NULL &&
633            (isGoto(lastInsn) || isInvoke ||
634            (targetOffset != UNKNOWN_TARGET && targetOffset != curOffset))) {
635            BasicBlock *newBB;
636            if (isInvoke) {
637                /* Monomorphic callee */
638                if (callee) {
639                    newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton);
640                    newBB->startOffset = 0;
641                    newBB->containingMethod = callee;
642                /* Will resolve at runtime */
643                } else {
644                    newBB = dvmCompilerNewBB(kChainingCellInvokePredicted);
645                    newBB->startOffset = 0;
646                }
647            /* For unconditional branches, request a hot chaining cell */
648            } else {
649#if !defined(WITH_SELF_VERIFICATION)
650                newBB = dvmCompilerNewBB(flags & kInstrUnconditional ?
651                                                  kChainingCellHot :
652                                                  kChainingCellNormal);
653                newBB->startOffset = targetOffset;
654#else
655                /* Handle branches that branch back into the block */
656                if (targetOffset >= curBB->firstMIRInsn->offset &&
657                    targetOffset <= curBB->lastMIRInsn->offset) {
658                    newBB = dvmCompilerNewBB(kChainingCellBackwardBranch);
659                } else {
660                    newBB = dvmCompilerNewBB(flags & kInstrUnconditional ?
661                                                      kChainingCellHot :
662                                                      kChainingCellNormal);
663                }
664                newBB->startOffset = targetOffset;
665#endif
666            }
667            newBB->id = numBlocks++;
668            curBB->taken = newBB;
669            lastBB->next = newBB;
670            lastBB = newBB;
671        }
672    }
673
674    /* Now create a special block to host PC reconstruction code */
675    lastBB->next = dvmCompilerNewBB(kPCReconstruction);
676    lastBB = lastBB->next;
677    lastBB->id = numBlocks++;
678
679    /* And one final block that publishes the PC and raise the exception */
680    lastBB->next = dvmCompilerNewBB(kExceptionHandling);
681    lastBB = lastBB->next;
682    lastBB->id = numBlocks++;
683
684    if (cUnit.printMe) {
685        LOGD("TRACEINFO (%d): 0x%08x %s%s 0x%x %d of %d, %d blocks",
686            compilationId,
687            (intptr_t) desc->method->insns,
688            desc->method->clazz->descriptor,
689            desc->method->name,
690            desc->trace[0].frag.startOffset,
691            traceSize,
692            dexCode->insnsSize,
693            numBlocks);
694    }
695
696    BasicBlock **blockList;
697
698    cUnit.method = desc->method;
699    cUnit.traceDesc = desc;
700    cUnit.numBlocks = numBlocks;
701    dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
702    blockList = cUnit.blockList =
703        dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
704
705    int i;
706
707    for (i = 0, curBB = startBB; i < numBlocks; i++) {
708        blockList[i] = curBB;
709        curBB = curBB->next;
710    }
711    /* Make sure all blocks are added to the cUnit */
712    assert(curBB == NULL);
713
714    /* Preparation for SSA conversion */
715    dvmInitializeSSAConversion(&cUnit);
716
717
718    if (cUnit.hasLoop) {
719        dvmCompilerLoopOpt(&cUnit);
720    }
721    else {
722        dvmCompilerNonLoopAnalysis(&cUnit);
723    }
724
725    dvmCompilerInitializeRegAlloc(&cUnit);  // Needs to happen after SSA naming
726
727    if (cUnit.printMe) {
728        dvmCompilerDumpCompilationUnit(&cUnit);
729    }
730
731    /* Set the instruction set to use (NOTE: later components may change it) */
732    cUnit.instructionSet = dvmCompilerInstructionSet();
733
734    /* Allocate Registers */
735    dvmCompilerRegAlloc(&cUnit);
736
737    /* Convert MIR to LIR, etc. */
738    dvmCompilerMIR2LIR(&cUnit);
739
740    /* Convert LIR into machine code. */
741    dvmCompilerAssembleLIR(&cUnit, info);
742
743    if (cUnit.printMe) {
744        if (cUnit.halveInstCount) {
745            LOGD("Assembler aborted");
746        } else {
747            dvmCompilerCodegenDump(&cUnit);
748        }
749        LOGD("End %s%s, %d Dalvik instructions",
750             desc->method->clazz->descriptor, desc->method->name,
751             cUnit.numInsts);
752    }
753
754    /* Reset the compiler resource pool */
755    dvmCompilerArenaReset();
756
757    /* Success */
758    if (!cUnit.halveInstCount) {
759#if defined(WITH_JIT_TUNING)
760        methodStats->nativeSize += cUnit.totalSize;
761#endif
762        return info->codeAddress != NULL;
763
764    /* Halve the instruction count and retry again */
765    } else {
766        return dvmCompileTrace(desc, cUnit.numInsts / 2, info, bailPtr);
767    }
768}
769
770/*
771 * Similar to dvmCompileTrace, but the entity processed here is the whole
772 * method.
773 *
774 * TODO: implementation will be revisited when the trace builder can provide
775 * whole-method traces.
776 */
777bool dvmCompileMethod(const Method *method, JitTranslationInfo *info)
778{
779    const DexCode *dexCode = dvmGetMethodCode(method);
780    const u2 *codePtr = dexCode->insns;
781    const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
782    int blockID = 0;
783    unsigned int curOffset = 0;
784
785    BasicBlock *firstBlock = dvmCompilerNewBB(kDalvikByteCode);
786    firstBlock->id = blockID++;
787
788    /* Allocate the bit-vector to track the beginning of basic blocks */
789    BitVector *bbStartAddr = dvmCompilerAllocBitVector(dexCode->insnsSize+1,
790                                                       false);
791    dvmCompilerSetBit(bbStartAddr, 0);
792
793    /*
794     * Sequentially go through every instruction first and put them in a single
795     * basic block. Identify block boundaries at the mean time.
796     */
797    while (codePtr < codeEnd) {
798        MIR *insn = dvmCompilerNew(sizeof(MIR), true);
799        insn->offset = curOffset;
800        int width = parseInsn(codePtr, &insn->dalvikInsn, false);
801        bool isInvoke = false;
802        const Method *callee;
803        insn->width = width;
804
805        /* Terminate when the data section is seen */
806        if (width == 0)
807            break;
808        dvmCompilerAppendMIR(firstBlock, insn);
809        /*
810         * Check whether this is a block ending instruction and whether it
811         * suggests the start of a new block
812         */
813        unsigned int target = curOffset;
814
815        /*
816         * If findBlockBoundary returns true, it means the current instruction
817         * is terminating the current block. If it is a branch, the target
818         * address will be recorded in target.
819         */
820        if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke,
821                              &callee)) {
822            dvmCompilerSetBit(bbStartAddr, curOffset + width);
823            if (target != curOffset) {
824                dvmCompilerSetBit(bbStartAddr, target);
825            }
826        }
827
828        codePtr += width;
829        /* each bit represents 16-bit quantity */
830        curOffset += width;
831    }
832
833    /*
834     * The number of blocks will be equal to the number of bits set to 1 in the
835     * bit vector minus 1, because the bit representing the location after the
836     * last instruction is set to one.
837     */
838    int numBlocks = dvmCountSetBits(bbStartAddr);
839    if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) {
840        numBlocks--;
841    }
842
843    CompilationUnit cUnit;
844    BasicBlock **blockList;
845
846    memset(&cUnit, 0, sizeof(CompilationUnit));
847    cUnit.method = method;
848    blockList = cUnit.blockList =
849        dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
850
851    /*
852     * Register the first block onto the list and start split it into block
853     * boundaries from there.
854     */
855    blockList[0] = firstBlock;
856    cUnit.numBlocks = 1;
857
858    int i;
859    for (i = 0; i < numBlocks; i++) {
860        MIR *insn;
861        BasicBlock *curBB = blockList[i];
862        curOffset = curBB->lastMIRInsn->offset;
863
864        for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) {
865            /* Found the beginning of a new block, see if it is created yet */
866            if (dvmIsBitSet(bbStartAddr, insn->offset)) {
867                int j;
868                for (j = 0; j < cUnit.numBlocks; j++) {
869                    if (blockList[j]->firstMIRInsn->offset == insn->offset)
870                        break;
871                }
872
873                /* Block not split yet - do it now */
874                if (j == cUnit.numBlocks) {
875                    BasicBlock *newBB = dvmCompilerNewBB(kDalvikByteCode);
876                    newBB->id = blockID++;
877                    newBB->firstMIRInsn = insn;
878                    newBB->startOffset = insn->offset;
879                    newBB->lastMIRInsn = curBB->lastMIRInsn;
880                    curBB->lastMIRInsn = insn->prev;
881                    insn->prev->next = NULL;
882                    insn->prev = NULL;
883
884                    /*
885                     * If the insn is not an unconditional branch, set up the
886                     * fallthrough link.
887                     */
888                    if (!isUnconditionalBranch(curBB->lastMIRInsn)) {
889                        curBB->fallThrough = newBB;
890                    }
891
892                    /* enqueue the new block */
893                    blockList[cUnit.numBlocks++] = newBB;
894                    break;
895                }
896            }
897        }
898    }
899
900    if (numBlocks != cUnit.numBlocks) {
901        LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit.numBlocks);
902        dvmCompilerAbort(&cUnit);
903    }
904
905    /* Connect the basic blocks through the taken links */
906    for (i = 0; i < numBlocks; i++) {
907        BasicBlock *curBB = blockList[i];
908        MIR *insn = curBB->lastMIRInsn;
909        unsigned int target = insn->offset;
910        bool isInvoke;
911        const Method *callee;
912
913        findBlockBoundary(method, insn, target, &target, &isInvoke, &callee);
914
915        /* Found a block ended on a branch */
916        if (target != insn->offset) {
917            int j;
918            /* Forward branch */
919            if (target > insn->offset) {
920                j = i + 1;
921            } else {
922                /* Backward branch */
923                j = 0;
924            }
925            for (; j < numBlocks; j++) {
926                if (blockList[j]->firstMIRInsn->offset == target) {
927                    curBB->taken = blockList[j];
928                    break;
929                }
930            }
931
932            /* Don't create dummy block for the callee yet */
933            if (j == numBlocks && !isInvoke) {
934                LOGE("Target not found for insn %x: expect target %x\n",
935                     curBB->lastMIRInsn->offset, target);
936                dvmCompilerAbort(&cUnit);
937            }
938        }
939    }
940
941    /* Set the instruction set to use (NOTE: later components may change it) */
942    cUnit.instructionSet = dvmCompilerInstructionSet();
943
944    dvmCompilerMIR2LIR(&cUnit);
945
946    dvmCompilerAssembleLIR(&cUnit, info);
947
948    dvmCompilerDumpCompilationUnit(&cUnit);
949
950    dvmCompilerArenaReset();
951
952    return info->codeAddress != NULL;
953}
954