vm/compiler/Frontend.c

   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/DexOpcodes.h"
  19 #include "libdex/DexCatch.h"
  20 #include "interp/Jit.h"
  21 #include "CompilerInternals.h"
  22 #include "Dataflow.h"
  23
  24 static inline bool contentIsInsn(const u2 *codePtr) {
  25     u2 instr = *codePtr;
  26     Opcode opcode = instr & 0xff;
  27
  28     /*
  29      * Since the low 8-bit in metadata may look like OP_NOP, we need to check
  30      * both the low and whole sub-word to determine whether it is code or data.
  31      */
  32     return (opcode != OP_NOP || instr == 0);
  33 }
  34
  35 /*
  36  * Parse an instruction, return the length of the instruction
  37  */
  38 static inline int parseInsn(const u2 *codePtr, DecodedInstruction *decInsn,
  39                             bool printMe)
  40 {
  41     // Don't parse instruction data
  42     if (!contentIsInsn(codePtr)) {
  43         return 0;
  44     }
  45
  46     u2 instr = *codePtr;
  47     Opcode opcode = dexOpcodeFromCodeUnit(instr);
  48
  49     dexDecodeInstruction(codePtr, decInsn);
  50     if (printMe) {
  51         char *decodedString = dvmCompilerGetDalvikDisassembly(decInsn, NULL);
  52         LOGD("%p: %#06x %s\n", codePtr, opcode, decodedString);
  53     }
  54     return dexGetWidthFromOpcode(opcode);
  55 }
  56
  57 #define UNKNOWN_TARGET 0xffffffff
  58
  59 /*
  60  * Identify block-ending instructions and collect supplemental information
  61  * regarding the following instructions.
  62  */
  63 static inline bool findBlockBoundary(const Method *caller, MIR *insn,
  64                                      unsigned int curOffset,
  65                                      unsigned int *target, bool *isInvoke,
  66                                      const Method **callee)
  67 {
  68     switch (insn->dalvikInsn.opcode) {
  69         /* Target is not compile-time constant */
  70         case OP_RETURN_VOID:
  71         case OP_RETURN:
  72         case OP_RETURN_WIDE:
  73         case OP_RETURN_OBJECT:
  74         case OP_THROW:
  75           *target = UNKNOWN_TARGET;
  76           break;
  77         case OP_INVOKE_VIRTUAL:
  78         case OP_INVOKE_VIRTUAL_RANGE:
  79         case OP_INVOKE_INTERFACE:
  80         case OP_INVOKE_INTERFACE_RANGE:
  81         case OP_INVOKE_VIRTUAL_QUICK:
  82         case OP_INVOKE_VIRTUAL_QUICK_RANGE:
  83             *isInvoke = true;
  84             break;
  85         case OP_INVOKE_SUPER:
  86         case OP_INVOKE_SUPER_RANGE: {
  87             int mIndex = caller->clazz->pDvmDex->
  88                 pResMethods[insn->dalvikInsn.vB]->methodIndex;
  89             const Method *calleeMethod =
  90                 caller->clazz->super->vtable[mIndex];
  91
  92             if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
  93                 *target = (unsigned int) calleeMethod->insns;
  94             }
  95             *isInvoke = true;
  96             *callee = calleeMethod;
  97             break;
  98         }
  99         case OP_INVOKE_STATIC:
 100         case OP_INVOKE_STATIC_RANGE: {
 101             const Method *calleeMethod =
 102                 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
 103
 104             if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
 105                 *target = (unsigned int) calleeMethod->insns;
 106             }
 107             *isInvoke = true;
 108             *callee = calleeMethod;
 109             break;
 110         }
 111         case OP_INVOKE_SUPER_QUICK:
 112         case OP_INVOKE_SUPER_QUICK_RANGE: {
 113             const Method *calleeMethod =
 114                 caller->clazz->super->vtable[insn->dalvikInsn.vB];
 115
 116             if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
 117                 *target = (unsigned int) calleeMethod->insns;
 118             }
 119             *isInvoke = true;
 120             *callee = calleeMethod;
 121             break;
 122         }
 123         case OP_INVOKE_DIRECT:
 124         case OP_INVOKE_DIRECT_RANGE: {
 125             const Method *calleeMethod =
 126                 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
 127             if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
 128                 *target = (unsigned int) calleeMethod->insns;
 129             }
 130             *isInvoke = true;
 131             *callee = calleeMethod;
 132             break;
 133         }
 134         case OP_GOTO:
 135         case OP_GOTO_16:
 136         case OP_GOTO_32:
 137             *target = curOffset + (int) insn->dalvikInsn.vA;
 138             break;
 139
 140         case OP_IF_EQ:
 141         case OP_IF_NE:
 142         case OP_IF_LT:
 143         case OP_IF_GE:
 144         case OP_IF_GT:
 145         case OP_IF_LE:
 146             *target = curOffset + (int) insn->dalvikInsn.vC;
 147             break;
 148
 149         case OP_IF_EQZ:
 150         case OP_IF_NEZ:
 151         case OP_IF_LTZ:
 152         case OP_IF_GEZ:
 153         case OP_IF_GTZ:
 154         case OP_IF_LEZ:
 155             *target = curOffset + (int) insn->dalvikInsn.vB;
 156             break;
 157
 158         default:
 159             return false;
 160     }
 161     return true;
 162 }
 163
 164 static inline bool isGoto(MIR *insn)
 165 {
 166     switch (insn->dalvikInsn.opcode) {
 167         case OP_GOTO:
 168         case OP_GOTO_16:
 169         case OP_GOTO_32:
 170             return true;
 171         default:
 172             return false;
 173     }
 174 }
 175
 176 /*
 177  * Identify unconditional branch instructions
 178  */
 179 static inline bool isUnconditionalBranch(MIR *insn)
 180 {
 181     switch (insn->dalvikInsn.opcode) {
 182         case OP_RETURN_VOID:
 183         case OP_RETURN:
 184         case OP_RETURN_WIDE:
 185         case OP_RETURN_OBJECT:
 186             return true;
 187         default:
 188             return isGoto(insn);
 189     }
 190 }
 191
 192 /*
 193  * dvmHashTableLookup() callback
 194  */
 195 static int compareMethod(const CompilerMethodStats *m1,
 196                          const CompilerMethodStats *m2)
 197 {
 198     return (int) m1->method - (int) m2->method;
 199 }
 200
 201 /*
 202  * Analyze the body of the method to collect high-level information regarding
 203  * inlining:
 204  * - is empty method?
 205  * - is getter/setter?
 206  * - can throw exception?
 207  *
 208  * Currently the inliner only handles getters and setters. When its capability
 209  * becomes more sophisticated more information will be retrieved here.
 210  */
 211 static int analyzeInlineTarget(DecodedInstruction *dalvikInsn, int attributes,
 212                                int offset)
 213 {
 214     int flags = dexGetFlagsFromOpcode(dalvikInsn->opcode);
 215     int dalvikOpcode = dalvikInsn->opcode;
 216
 217     if (flags & kInstrInvoke) {
 218         attributes &= ~METHOD_IS_LEAF;
 219     }
 220
 221     if (!(flags & kInstrCanReturn)) {
 222         if (!(dvmCompilerDataFlowAttributes[dalvikOpcode] &
 223               DF_IS_GETTER)) {
 224             attributes &= ~METHOD_IS_GETTER;
 225         }
 226         if (!(dvmCompilerDataFlowAttributes[dalvikOpcode] &
 227               DF_IS_SETTER)) {
 228             attributes &= ~METHOD_IS_SETTER;
 229         }
 230     }
 231
 232     /*
 233      * The expected instruction sequence is setter will never return value and
 234      * getter will also do. Clear the bits if the behavior is discovered
 235      * otherwise.
 236      */
 237     if (flags & kInstrCanReturn) {
 238         if (dalvikOpcode == OP_RETURN_VOID) {
 239             attributes &= ~METHOD_IS_GETTER;
 240         }
 241         else {
 242             attributes &= ~METHOD_IS_SETTER;
 243         }
 244     }
 245
 246     if (flags & kInstrCanThrow) {
 247         attributes &= ~METHOD_IS_THROW_FREE;
 248     }
 249
 250     if (offset == 0 && dalvikOpcode == OP_RETURN_VOID) {
 251         attributes |= METHOD_IS_EMPTY;
 252     }
 253
 254     /*
 255      * Check if this opcode is selected for single stepping.
 256      * If so, don't inline the callee as there is no stack frame for the
 257      * interpreter to single-step through the instruction.
 258      */
 259     if (SINGLE_STEP_OP(dalvikOpcode)) {
 260         attributes &= ~(METHOD_IS_GETTER | METHOD_IS_SETTER);
 261     }
 262
 263     return attributes;
 264 }
 265
 266 /*
 267  * Analyze each method whose traces are ever compiled. Collect a variety of
 268  * statistics like the ratio of exercised vs overall code and code bloat
 269  * ratios. If isCallee is true, also analyze each instruction in more details
 270  * to see if it is suitable for inlining.
 271  */
 272 CompilerMethodStats *dvmCompilerAnalyzeMethodBody(const Method *method,
 273                                                   bool isCallee)
 274 {
 275     const DexCode *dexCode = dvmGetMethodCode(method);
 276     const u2 *codePtr = dexCode->insns;
 277     const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
 278     int insnSize = 0;
 279     int hashValue = dvmComputeUtf8Hash(method->name);
 280
 281     CompilerMethodStats dummyMethodEntry; // For hash table lookup
 282     CompilerMethodStats *realMethodEntry; // For hash table storage
 283
 284     /* For lookup only */
 285     dummyMethodEntry.method = method;
 286     realMethodEntry =
 287         (CompilerMethodStats *) dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
 288                                                    &dummyMethodEntry,
 289                                                    (HashCompareFunc) compareMethod,
 290                                                    false);
 291
 292     /* This method has never been analyzed before - create an entry */
 293     if (realMethodEntry == NULL) {
 294         realMethodEntry =
 295             (CompilerMethodStats *) calloc(1, sizeof(CompilerMethodStats));
 296         realMethodEntry->method = method;
 297
 298         dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
 299                            realMethodEntry,
 300                            (HashCompareFunc) compareMethod,
 301                            true);
 302     }
 303
 304     /* This method is invoked as a callee and has been analyzed - just return */
 305     if ((isCallee == true) && (realMethodEntry->attributes & METHOD_IS_CALLEE))
 306         return realMethodEntry;
 307
 308     /*
 309      * Similarly, return if this method has been compiled before as a hot
 310      * method already.
 311      */
 312     if ((isCallee == false) &&
 313         (realMethodEntry->attributes & METHOD_IS_HOT))
 314         return realMethodEntry;
 315
 316     int attributes;
 317
 318     /* Method hasn't been analyzed for the desired purpose yet */
 319     if (isCallee) {
 320         /* Aggressively set the attributes until proven otherwise */
 321         attributes = METHOD_IS_LEAF | METHOD_IS_THROW_FREE | METHOD_IS_CALLEE |
 322                      METHOD_IS_GETTER | METHOD_IS_SETTER;
 323     } else {
 324         attributes = METHOD_IS_HOT;
 325     }
 326
 327     /* Count the number of instructions */
 328     while (codePtr < codeEnd) {
 329         DecodedInstruction dalvikInsn;
 330         int width = parseInsn(codePtr, &dalvikInsn, false);
 331
 332         /* Terminate when the data section is seen */
 333         if (width == 0)
 334             break;
 335
 336         if (isCallee) {
 337             attributes = analyzeInlineTarget(&dalvikInsn, attributes, insnSize);
 338         }
 339
 340         insnSize += width;
 341         codePtr += width;
 342     }
 343
 344     /*
 345      * Only handle simple getters/setters with one instruction followed by
 346      * return
 347      */
 348     if ((attributes & (METHOD_IS_GETTER | METHOD_IS_SETTER)) &&
 349         (insnSize != 3)) {
 350         attributes &= ~(METHOD_IS_GETTER | METHOD_IS_SETTER);
 351     }
 352
 353     realMethodEntry->dalvikSize = insnSize * 2;
 354     realMethodEntry->attributes |= attributes;
 355
 356 #if 0
 357     /* Uncomment the following to explore various callee patterns */
 358     if (attributes & METHOD_IS_THROW_FREE) {
 359         LOGE("%s%s is inlinable%s", method->clazz->descriptor, method->name,
 360              (attributes & METHOD_IS_EMPTY) ? " empty" : "");
 361     }
 362
 363     if (attributes & METHOD_IS_LEAF) {
 364         LOGE("%s%s is leaf %d%s", method->clazz->descriptor, method->name,
 365              insnSize, insnSize < 5 ? " (small)" : "");
 366     }
 367
 368     if (attributes & (METHOD_IS_GETTER | METHOD_IS_SETTER)) {
 369         LOGE("%s%s is %s", method->clazz->descriptor, method->name,
 370              attributes & METHOD_IS_GETTER ? "getter": "setter");
 371     }
 372     if (attributes ==
 373         (METHOD_IS_LEAF | METHOD_IS_THROW_FREE | METHOD_IS_CALLEE)) {
 374         LOGE("%s%s is inlinable non setter/getter", method->clazz->descriptor,
 375              method->name);
 376     }
 377 #endif
 378
 379     return realMethodEntry;
 380 }
 381
 382 /*
 383  * Crawl the stack of the thread that requesed compilation to see if any of the
 384  * ancestors are on the blacklist.
 385  */
 386 static bool filterMethodByCallGraph(Thread *thread, const char *curMethodName)
 387 {
 388     /* Crawl the Dalvik stack frames and compare the method name*/
 389     StackSaveArea *ssaPtr = ((StackSaveArea *) thread->curFrame) - 1;
 390     while (ssaPtr != ((StackSaveArea *) NULL) - 1) {
 391         const Method *method = ssaPtr->method;
 392         if (method) {
 393             int hashValue = dvmComputeUtf8Hash(method->name);
 394             bool found =
 395                 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
 396                                (char *) method->name,
 397                                (HashCompareFunc) strcmp, false) !=
 398                 NULL;
 399             if (found) {
 400                 LOGD("Method %s (--> %s) found on the JIT %s list",
 401                      method->name, curMethodName,
 402                      gDvmJit.includeSelectedMethod ? "white" : "black");
 403                 return true;
 404             }
 405
 406         }
 407         ssaPtr = ((StackSaveArea *) ssaPtr->prevFrame) - 1;
 408     };
 409     return false;
 410 }
 411
 412 /*
 413  * Main entry point to start trace compilation. Basic blocks are constructed
 414  * first and they will be passed to the codegen routines to convert Dalvik
 415  * bytecode into machine code.
 416  */
 417 bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts,
 418                      JitTranslationInfo *info, jmp_buf *bailPtr,
 419                      int optHints)
 420 {
 421     const DexCode *dexCode = dvmGetMethodCode(desc->method);
 422     const JitTraceRun* currRun = &desc->trace[0];
 423     unsigned int curOffset = currRun->frag.startOffset;
 424     unsigned int numInsts = currRun->frag.numInsts;
 425     const u2 *codePtr = dexCode->insns + curOffset;
 426     int traceSize = 0;  // # of half-words
 427     const u2 *startCodePtr = codePtr;
 428     BasicBlock *curBB, *entryCodeBB;
 429     int numBlocks = 0;
 430     static int compilationId;
 431     CompilationUnit cUnit;
 432     GrowableList *blockList;
 433 #if defined(WITH_JIT_TUNING)
 434     CompilerMethodStats *methodStats;
 435 #endif
 436
 437     /* If we've already compiled this trace, just return success */
 438     if (dvmJitGetCodeAddr(startCodePtr) && !info->discardResult) {
 439         /*
 440          * Make sure the codeAddress is NULL so that it won't clobber the
 441          * existing entry.
 442          */
 443         info->codeAddress = NULL;
 444         return true;
 445     }
 446
 447     compilationId++;
 448     memset(&cUnit, 0, sizeof(CompilationUnit));
 449
 450 #if defined(WITH_JIT_TUNING)
 451     /* Locate the entry to store compilation statistics for this method */
 452     methodStats = dvmCompilerAnalyzeMethodBody(desc->method, false);
 453 #endif
 454
 455     /* Set the recover buffer pointer */
 456     cUnit.bailPtr = bailPtr;
 457
 458     /* Initialize the printMe flag */
 459     cUnit.printMe = gDvmJit.printMe;
 460
 461     /* Initialize the profile flag */
 462     cUnit.executionCount = gDvmJit.profile;
 463
 464     /* Setup the method */
 465     cUnit.method = desc->method;
 466
 467     /* Initialize the PC reconstruction list */
 468     dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
 469
 470     /* Initialize the basic block list */
 471     blockList = &cUnit.blockList;
 472     dvmInitGrowableList(blockList, 8);
 473
 474     /* Identify traces that we don't want to compile */
 475     if (gDvmJit.methodTable) {
 476         int len = strlen(desc->method->clazz->descriptor) +
 477                   strlen(desc->method->name) + 1;
 478         char *fullSignature = (char *)dvmCompilerNew(len, true);
 479         strcpy(fullSignature, desc->method->clazz->descriptor);
 480         strcat(fullSignature, desc->method->name);
 481
 482         int hashValue = dvmComputeUtf8Hash(fullSignature);
 483
 484         /*
 485          * Doing three levels of screening to see whether we want to skip
 486          * compiling this method
 487          */
 488
 489         /* First, check the full "class;method" signature */
 490         bool methodFound =
 491             dvmHashTableLookup(gDvmJit.methodTable, hashValue,
 492                                fullSignature, (HashCompareFunc) strcmp,
 493                                false) !=
 494             NULL;
 495
 496         /* Full signature not found - check the enclosing class */
 497         if (methodFound == false) {
 498             int hashValue = dvmComputeUtf8Hash(desc->method->clazz->descriptor);
 499             methodFound =
 500                 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
 501                                (char *) desc->method->clazz->descriptor,
 502                                (HashCompareFunc) strcmp, false) !=
 503                 NULL;
 504             /* Enclosing class not found - check the method name */
 505             if (methodFound == false) {
 506                 int hashValue = dvmComputeUtf8Hash(desc->method->name);
 507                 methodFound =
 508                     dvmHashTableLookup(gDvmJit.methodTable, hashValue,
 509                                    (char *) desc->method->name,
 510                                    (HashCompareFunc) strcmp, false) !=
 511                     NULL;
 512
 513                 /*
 514                  * Debug by call-graph is enabled. Check if the debug list
 515                  * covers any methods on the VM stack.
 516                  */
 517                 if (methodFound == false && gDvmJit.checkCallGraph == true) {
 518                     methodFound =
 519                         filterMethodByCallGraph(info->requestingThread,
 520                                                 desc->method->name);
 521                 }
 522             }
 523         }
 524
 525         /*
 526          * Under the following conditions, the trace will be *conservatively*
 527          * compiled by only containing single-step instructions to and from the
 528          * interpreter.
 529          * 1) If includeSelectedMethod == false, the method matches the full or
 530          *    partial signature stored in the hash table.
 531          *
 532          * 2) If includeSelectedMethod == true, the method does not match the
 533          *    full and partial signature stored in the hash table.
 534          */
 535         if (gDvmJit.includeSelectedMethod != methodFound) {
 536             cUnit.allSingleStep = true;
 537         } else {
 538             /* Compile the trace as normal */
 539
 540             /* Print the method we cherry picked */
 541             if (gDvmJit.includeSelectedMethod == true) {
 542                 cUnit.printMe = true;
 543             }
 544         }
 545     }
 546
 547     /* Allocate the entry block */
 548     curBB = dvmCompilerNewBB(kTraceEntryBlock, numBlocks++);
 549     dvmInsertGrowableList(blockList, (intptr_t) curBB);
 550     curBB->startOffset = curOffset;
 551
 552     entryCodeBB = dvmCompilerNewBB(kDalvikByteCode, numBlocks++);
 553     dvmInsertGrowableList(blockList, (intptr_t) entryCodeBB);
 554     entryCodeBB->startOffset = curOffset;
 555     curBB->fallThrough = entryCodeBB;
 556     curBB = entryCodeBB;
 557
 558     if (cUnit.printMe) {
 559         LOGD("--------\nCompiler: Building trace for %s, offset 0x%x\n",
 560              desc->method->name, curOffset);
 561     }
 562
 563     /*
 564      * Analyze the trace descriptor and include up to the maximal number
 565      * of Dalvik instructions into the IR.
 566      */
 567     while (1) {
 568         MIR *insn;
 569         int width;
 570         insn = (MIR *)dvmCompilerNew(sizeof(MIR), true);
 571         insn->offset = curOffset;
 572         width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe);
 573
 574         /* The trace should never incude instruction data */
 575         assert(width);
 576         insn->width = width;
 577         traceSize += width;
 578         dvmCompilerAppendMIR(curBB, insn);
 579         cUnit.numInsts++;
 580
 581         int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode);
 582
 583         if (flags & kInstrInvoke) {
 584             assert(numInsts == 1);
 585             CallsiteInfo *callsiteInfo =
 586                 (CallsiteInfo *)dvmCompilerNew(sizeof(CallsiteInfo), true);
 587             callsiteInfo->clazz = (ClassObject *)currRun[1].meta;
 588             callsiteInfo->method = (Method *)currRun[2].meta;
 589             insn->meta.callsiteInfo = callsiteInfo;
 590         }
 591
 592         /* Instruction limit reached - terminate the trace here */
 593         if (cUnit.numInsts >= numMaxInsts) {
 594             break;
 595         }
 596         if (--numInsts == 0) {
 597             if (currRun->frag.runEnd) {
 598                 break;
 599             } else {
 600                 /* Advance to the next trace description (ie non-meta info) */
 601                 do {
 602                     currRun++;
 603                 } while (!currRun->frag.isCode);
 604
 605                 /* Dummy end-of-run marker seen */
 606                 if (currRun->frag.numInsts == 0) {
 607                     break;
 608                 }
 609
 610                 curBB = dvmCompilerNewBB(kDalvikByteCode, numBlocks++);
 611                 dvmInsertGrowableList(blockList, (intptr_t) curBB);
 612                 curOffset = currRun->frag.startOffset;
 613                 numInsts = currRun->frag.numInsts;
 614                 curBB->startOffset = curOffset;
 615                 codePtr = dexCode->insns + curOffset;
 616             }
 617         } else {
 618             curOffset += width;
 619             codePtr += width;
 620         }
 621     }
 622
 623 #if defined(WITH_JIT_TUNING)
 624     /* Convert # of half-word to bytes */
 625     methodStats->compiledDalvikSize += traceSize * 2;
 626 #endif
 627
 628     /*
 629      * Now scan basic blocks containing real code to connect the
 630      * taken/fallthrough links. Also create chaining cells for code not included
 631      * in the trace.
 632      */
 633     size_t blockId;
 634     for (blockId = 0; blockId < blockList->numUsed; blockId++) {
 635         curBB = (BasicBlock *) dvmGrowableListGetElement(blockList, blockId);
 636         MIR *lastInsn = curBB->lastMIRInsn;
 637         /* Skip empty blocks */
 638         if (lastInsn == NULL) {
 639             continue;
 640         }
 641         curOffset = lastInsn->offset;
 642         unsigned int targetOffset = curOffset;
 643         unsigned int fallThroughOffset = curOffset + lastInsn->width;
 644         bool isInvoke = false;
 645         const Method *callee = NULL;
 646
 647         findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset,
 648                           &targetOffset, &isInvoke, &callee);
 649
 650         /* Link the taken and fallthrough blocks */
 651         BasicBlock *searchBB;
 652
 653         int flags = dexGetFlagsFromOpcode(lastInsn->dalvikInsn.opcode);
 654
 655         if (flags & kInstrInvoke) {
 656             cUnit.hasInvoke = true;
 657         }
 658
 659         /* No backward branch in the trace - start searching the next BB */
 660         size_t searchBlockId;
 661         for (searchBlockId = blockId+1; searchBlockId < blockList->numUsed;
 662              searchBlockId++) {
 663             searchBB = (BasicBlock *) dvmGrowableListGetElement(blockList,
 664                                                                 searchBlockId);
 665             if (targetOffset == searchBB->startOffset) {
 666                 curBB->taken = searchBB;
 667             }
 668             if (fallThroughOffset == searchBB->startOffset) {
 669                 curBB->fallThrough = searchBB;
 670
 671                 /*
 672                  * Fallthrough block of an invoke instruction needs to be
 673                  * aligned to 4-byte boundary (alignment instruction to be
 674                  * inserted later.
 675                  */
 676                 if (flags & kInstrInvoke) {
 677                     searchBB->isFallThroughFromInvoke = true;
 678                 }
 679             }
 680         }
 681
 682         /*
 683          * Some blocks are ended by non-control-flow-change instructions,
 684          * currently only due to trace length constraint. In this case we need
 685          * to generate an explicit branch at the end of the block to jump to
 686          * the chaining cell.
 687          */
 688         curBB->needFallThroughBranch =
 689             ((flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
 690                        kInstrInvoke)) == 0);
 691
 692         /* Only form a loop if JIT_OPT_NO_LOOP is not set */
 693         if (curBB->taken == NULL &&
 694             curBB->fallThrough == NULL &&
 695             flags == (kInstrCanBranch | kInstrCanContinue) &&
 696             fallThroughOffset == entryCodeBB->startOffset &&
 697             JIT_OPT_NO_LOOP != (optHints & JIT_OPT_NO_LOOP)) {
 698             BasicBlock *loopBranch = curBB;
 699             BasicBlock *exitBB;
 700             BasicBlock *exitChainingCell;
 701
 702             if (cUnit.printMe) {
 703                 LOGD("Natural loop detected!");
 704             }
 705             exitBB = dvmCompilerNewBB(kTraceExitBlock, numBlocks++);
 706             dvmInsertGrowableList(blockList, (intptr_t) exitBB);
 707             exitBB->startOffset = targetOffset;
 708             exitBB->needFallThroughBranch = true;
 709
 710             loopBranch->taken = exitBB;
 711 #if defined(WITH_SELF_VERIFICATION)
 712             BasicBlock *backwardCell =
 713                 dvmCompilerNewBB(kChainingCellBackwardBranch, numBlocks++);
 714             dvmInsertGrowableList(blockList, (intptr_t) backwardCell);
 715             backwardCell->startOffset = entryCodeBB->startOffset;
 716             loopBranch->fallThrough = backwardCell;
 717 #elif defined(WITH_JIT_TUNING)
 718             if (gDvmJit.profile) {
 719                 BasicBlock *backwardCell =
 720                     dvmCompilerNewBB(kChainingCellBackwardBranch, numBlocks++);
 721                 dvmInsertGrowableList(blockList, (intptr_t) backwardCell);
 722                 backwardCell->startOffset = entryCodeBB->startOffset;
 723                 loopBranch->fallThrough = backwardCell;
 724             } else {
 725                 loopBranch->fallThrough = entryCodeBB;
 726             }
 727 #else
 728             loopBranch->fallThrough = entryCodeBB;
 729 #endif
 730
 731             /* Create the chaining cell as the fallthrough of the exit block */
 732             exitChainingCell = dvmCompilerNewBB(kChainingCellNormal,
 733                                                 numBlocks++);
 734             dvmInsertGrowableList(blockList, (intptr_t) exitChainingCell);
 735             exitChainingCell->startOffset = targetOffset;
 736
 737             exitBB->fallThrough = exitChainingCell;
 738
 739             cUnit.hasLoop = true;
 740         }
 741
 742         if (lastInsn->dalvikInsn.opcode == OP_PACKED_SWITCH ||
 743             lastInsn->dalvikInsn.opcode == OP_SPARSE_SWITCH) {
 744             int i;
 745             const u2 *switchData = desc->method->insns + lastInsn->offset +
 746                              lastInsn->dalvikInsn.vB;
 747             int size = switchData[1];
 748             int maxChains = MIN(size, MAX_CHAINED_SWITCH_CASES);
 749
 750             /*
 751              * Generate the landing pad for cases whose ranks are higher than
 752              * MAX_CHAINED_SWITCH_CASES. The code will re-enter the interpreter
 753              * through the NoChain point.
 754              */
 755             if (maxChains != size) {
 756                 cUnit.switchOverflowPad =
 757                     desc->method->insns + lastInsn->offset;
 758             }
 759
 760             s4 *targets = (s4 *) (switchData + 2 +
 761                     (lastInsn->dalvikInsn.opcode == OP_PACKED_SWITCH ?
 762                      2 : size * 2));
 763
 764             /* One chaining cell for the first MAX_CHAINED_SWITCH_CASES cases */
 765             for (i = 0; i < maxChains; i++) {
 766                 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal,
 767                                                          numBlocks++);
 768                 dvmInsertGrowableList(blockList, (intptr_t) caseChain);
 769                 caseChain->startOffset = lastInsn->offset + targets[i];
 770             }
 771
 772             /* One more chaining cell for the default case */
 773             BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal,
 774                                                      numBlocks++);
 775             dvmInsertGrowableList(blockList, (intptr_t) caseChain);
 776             caseChain->startOffset = lastInsn->offset + lastInsn->width;
 777         /* Fallthrough block not included in the trace */
 778         } else if (!isUnconditionalBranch(lastInsn) &&
 779                    curBB->fallThrough == NULL) {
 780             BasicBlock *fallThroughBB;
 781             /*
 782              * If the chaining cell is after an invoke or
 783              * instruction that cannot change the control flow, request a hot
 784              * chaining cell.
 785              */
 786             if (isInvoke || curBB->needFallThroughBranch) {
 787                 fallThroughBB = dvmCompilerNewBB(kChainingCellHot, numBlocks++);
 788             } else {
 789                 fallThroughBB = dvmCompilerNewBB(kChainingCellNormal,
 790                                                  numBlocks++);
 791             }
 792             dvmInsertGrowableList(blockList, (intptr_t) fallThroughBB);
 793             fallThroughBB->startOffset = fallThroughOffset;
 794             curBB->fallThrough = fallThroughBB;
 795         }
 796         /* Target block not included in the trace */
 797         if (curBB->taken == NULL &&
 798             (isGoto(lastInsn) || isInvoke ||
 799             (targetOffset != UNKNOWN_TARGET && targetOffset != curOffset))) {
 800             BasicBlock *newBB;
 801             if (isInvoke) {
 802                 /* Monomorphic callee */
 803                 if (callee) {
 804                     newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton,
 805                                              numBlocks++);
 806                     newBB->startOffset = 0;
 807                     newBB->containingMethod = callee;
 808                 /* Will resolve at runtime */
 809                 } else {
 810                     newBB = dvmCompilerNewBB(kChainingCellInvokePredicted,
 811                                              numBlocks++);
 812                     newBB->startOffset = 0;
 813                 }
 814             /* For unconditional branches, request a hot chaining cell */
 815             } else {
 816 #if !defined(WITH_SELF_VERIFICATION)
 817                 newBB = dvmCompilerNewBB(dexIsGoto(flags) ?
 818                                                   kChainingCellHot :
 819                                                   kChainingCellNormal,
 820                                          numBlocks++);
 821                 newBB->startOffset = targetOffset;
 822 #else
 823                 /* Handle branches that branch back into the block */
 824                 if (targetOffset >= curBB->firstMIRInsn->offset &&
 825                     targetOffset <= curBB->lastMIRInsn->offset) {
 826                     newBB = dvmCompilerNewBB(kChainingCellBackwardBranch,
 827                                              numBlocks++);
 828                 } else {
 829                     newBB = dvmCompilerNewBB(dexIsGoto(flags) ?
 830                                                       kChainingCellHot :
 831                                                       kChainingCellNormal,
 832                                              numBlocks++);
 833                 }
 834                 newBB->startOffset = targetOffset;
 835 #endif
 836             }
 837             curBB->taken = newBB;
 838             dvmInsertGrowableList(blockList, (intptr_t) newBB);
 839         }
 840     }
 841
 842     /* Now create a special block to host PC reconstruction code */
 843     curBB = dvmCompilerNewBB(kPCReconstruction, numBlocks++);
 844     dvmInsertGrowableList(blockList, (intptr_t) curBB);
 845
 846     /* And one final block that publishes the PC and raise the exception */
 847     curBB = dvmCompilerNewBB(kExceptionHandling, numBlocks++);
 848     dvmInsertGrowableList(blockList, (intptr_t) curBB);
 849
 850     if (cUnit.printMe) {
 851         char* signature =
 852             dexProtoCopyMethodDescriptor(&desc->method->prototype);
 853         LOGD("TRACEINFO (%d): 0x%08x %s%s.%s 0x%x %d of %d, %d blocks",
 854             compilationId,
 855             (intptr_t) desc->method->insns,
 856             desc->method->clazz->descriptor,
 857             desc->method->name,
 858             signature,
 859             desc->trace[0].frag.startOffset,
 860             traceSize,
 861             dexCode->insnsSize,
 862             numBlocks);
 863         free(signature);
 864     }
 865
 866     cUnit.traceDesc = desc;
 867     cUnit.numBlocks = numBlocks;
 868
 869     /* Set the instruction set to use (NOTE: later components may change it) */
 870     cUnit.instructionSet = dvmCompilerInstructionSet();
 871
 872     /* Inline transformation @ the MIR level */
 873     if (cUnit.hasInvoke && !(gDvmJit.disableOpt & (1 << kMethodInlining))) {
 874         dvmCompilerInlineMIR(&cUnit);
 875     }
 876
 877     cUnit.numDalvikRegisters = cUnit.method->registersSize;
 878
 879     /* Preparation for SSA conversion */
 880     dvmInitializeSSAConversion(&cUnit);
 881
 882     if (cUnit.hasLoop) {
 883         /*
 884          * Loop is not optimizable (for example lack of a single induction
 885          * variable), punt and recompile the trace with loop optimization
 886          * disabled.
 887          */
 888         bool loopOpt = dvmCompilerLoopOpt(&cUnit);
 889         if (loopOpt == false) {
 890             if (cUnit.printMe) {
 891                 LOGD("Loop is not optimizable - retry codegen");
 892             }
 893             /* Reset the compiler resource pool */
 894             dvmCompilerArenaReset();
 895             return dvmCompileTrace(desc, cUnit.numInsts, info, bailPtr,
 896                                    optHints | JIT_OPT_NO_LOOP);
 897         }
 898     }
 899     else {
 900         dvmCompilerNonLoopAnalysis(&cUnit);
 901     }
 902
 903     dvmCompilerInitializeRegAlloc(&cUnit);  // Needs to happen after SSA naming
 904
 905     if (cUnit.printMe) {
 906         dvmCompilerDumpCompilationUnit(&cUnit);
 907     }
 908
 909     /* Allocate Registers */
 910     dvmCompilerRegAlloc(&cUnit);
 911
 912     /* Convert MIR to LIR, etc. */
 913     dvmCompilerMIR2LIR(&cUnit);
 914
 915     /* Convert LIR into machine code. Loop for recoverable retries */
 916     do {
 917         dvmCompilerAssembleLIR(&cUnit, info);
 918         cUnit.assemblerRetries++;
 919         if (cUnit.printMe && cUnit.assemblerStatus != kSuccess)
 920             LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries,
 921                   cUnit.assemblerStatus);
 922     } while (cUnit.assemblerStatus == kRetryAll);
 923
 924     if (cUnit.printMe) {
 925         dvmCompilerCodegenDump(&cUnit);
 926         LOGD("End %s%s, %d Dalvik instructions",
 927              desc->method->clazz->descriptor, desc->method->name,
 928              cUnit.numInsts);
 929     }
 930
 931     /* Reset the compiler resource pool */
 932     dvmCompilerArenaReset();
 933
 934     if (cUnit.assemblerStatus == kRetryHalve) {
 935         /* Halve the instruction count and start from the top */
 936         return dvmCompileTrace(desc, cUnit.numInsts / 2, info, bailPtr,
 937                                optHints);
 938     }
 939
 940     assert(cUnit.assemblerStatus == kSuccess);
 941 #if defined(WITH_JIT_TUNING)
 942     methodStats->nativeSize += cUnit.totalSize;
 943 #endif
 944
 945     /* FIXME - to exercise the method parser, uncomment the following code */
 946 #if 0
 947     bool dvmCompileMethod(const Method *method);
 948     if (desc->trace[0].frag.startOffset == 0) {
 949         dvmCompileMethod(desc->method);
 950     }
 951 #endif
 952
 953     return info->codeAddress != NULL;
 954 }
 955
 956 /*
 957  * Since we are including instructions from possibly a cold method into the
 958  * current trace, we need to make sure that all the associated information
 959  * with the callee is properly initialized. If not, we punt on this inline
 960  * target.
 961  *
 962  * TODO: volatile instructions will be handled later.
 963  */
 964 bool dvmCompilerCanIncludeThisInstruction(const Method *method,
 965                                           const DecodedInstruction *insn)
 966 {
 967     switch (insn->opcode) {
 968         case OP_NEW_INSTANCE:
 969         case OP_CHECK_CAST: {
 970             ClassObject *classPtr = (ClassObject *)(void*)
 971               (method->clazz->pDvmDex->pResClasses[insn->vB]);
 972
 973             /* Class hasn't been initialized yet */
 974             if (classPtr == NULL) {
 975                 return false;
 976             }
 977             return true;
 978         }
 979         case OP_SGET_OBJECT:
 980         case OP_SGET_BOOLEAN:
 981         case OP_SGET_CHAR:
 982         case OP_SGET_BYTE:
 983         case OP_SGET_SHORT:
 984         case OP_SGET:
 985         case OP_SGET_WIDE:
 986         case OP_SPUT_OBJECT:
 987         case OP_SPUT_BOOLEAN:
 988         case OP_SPUT_CHAR:
 989         case OP_SPUT_BYTE:
 990         case OP_SPUT_SHORT:
 991         case OP_SPUT:
 992         case OP_SPUT_WIDE: {
 993             void *fieldPtr = (void*)
 994               (method->clazz->pDvmDex->pResFields[insn->vB]);
 995
 996             if (fieldPtr == NULL) {
 997                 return false;
 998             }
 999             return true;
1000         }
1001         case OP_INVOKE_SUPER:
1002         case OP_INVOKE_SUPER_RANGE: {
1003             int mIndex = method->clazz->pDvmDex->
1004                 pResMethods[insn->vB]->methodIndex;
1005             const Method *calleeMethod = method->clazz->super->vtable[mIndex];
1006             if (calleeMethod == NULL) {
1007                 return false;
1008             }
1009             return true;
1010         }
1011         case OP_INVOKE_SUPER_QUICK:
1012         case OP_INVOKE_SUPER_QUICK_RANGE: {
1013             const Method *calleeMethod = method->clazz->super->vtable[insn->vB];
1014             if (calleeMethod == NULL) {
1015                 return false;
1016             }
1017             return true;
1018         }
1019         case OP_INVOKE_STATIC:
1020         case OP_INVOKE_STATIC_RANGE:
1021         case OP_INVOKE_DIRECT:
1022         case OP_INVOKE_DIRECT_RANGE: {
1023             const Method *calleeMethod =
1024                 method->clazz->pDvmDex->pResMethods[insn->vB];
1025             if (calleeMethod == NULL) {
1026                 return false;
1027             }
1028             return true;
1029         }
1030         case OP_CONST_CLASS: {
1031             void *classPtr = (void*)
1032                 (method->clazz->pDvmDex->pResClasses[insn->vB]);
1033
1034             if (classPtr == NULL) {
1035                 return false;
1036             }
1037             return true;
1038         }
1039         case OP_CONST_STRING_JUMBO:
1040         case OP_CONST_STRING: {
1041             void *strPtr = (void*)
1042                 (method->clazz->pDvmDex->pResStrings[insn->vB]);
1043
1044             if (strPtr == NULL) {
1045                 return false;
1046             }
1047             return true;
1048         }
1049         default:
1050             return true;
1051     }
1052 }
1053
1054 /* Split an existing block from the specified code offset into two */
1055 static BasicBlock *splitBlock(CompilationUnit *cUnit,
1056                               unsigned int codeOffset,
1057                               BasicBlock *origBlock)
1058 {
1059     MIR *insn = origBlock->firstMIRInsn;
1060     while (insn) {
1061         if (insn->offset == codeOffset) break;
1062         insn = insn->next;
1063     }
1064     if (insn == NULL) {
1065         LOGE("Break split failed");
1066         dvmAbort();
1067     }
1068     BasicBlock *bottomBlock = dvmCompilerNewBB(kDalvikByteCode,
1069                                                cUnit->numBlocks++);
1070     dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bottomBlock);
1071
1072     bottomBlock->startOffset = codeOffset;
1073     bottomBlock->firstMIRInsn = insn;
1074     bottomBlock->lastMIRInsn = origBlock->lastMIRInsn;
1075
1076     /* Only the top half of split blocks is tagged as BA_CATCH_BLOCK */
1077     bottomBlock->blockAttributes = origBlock->blockAttributes & ~BA_CATCH_BLOCK;
1078
1079     /* Handle the taken path */
1080     bottomBlock->taken = origBlock->taken;
1081     if (bottomBlock->taken) {
1082         origBlock->taken = NULL;
1083         dvmCompilerClearBit(bottomBlock->taken->predecessors, origBlock->id);
1084         dvmCompilerSetBit(bottomBlock->taken->predecessors, bottomBlock->id);
1085     }
1086
1087     /* Handle the fallthrough path */
1088     bottomBlock->fallThrough = origBlock->fallThrough;
1089     origBlock->fallThrough = bottomBlock;
1090     dvmCompilerSetBit(bottomBlock->predecessors, origBlock->id);
1091     if (bottomBlock->fallThrough) {
1092         dvmCompilerClearBit(bottomBlock->fallThrough->predecessors,
1093                             origBlock->id);
1094         dvmCompilerSetBit(bottomBlock->fallThrough->predecessors,
1095                           bottomBlock->id);
1096     }
1097
1098     /* Handle the successor list */
1099     if (origBlock->successorBlockList.blockListType != kNotUsed) {
1100         bottomBlock->successorBlockList = origBlock->successorBlockList;
1101         origBlock->successorBlockList.blockListType = kNotUsed;
1102         GrowableListIterator iterator;
1103
1104         dvmGrowableListIteratorInit(&bottomBlock->successorBlockList.blocks,
1105                                     &iterator);
1106         while (true) {
1107             BasicBlock *bb =
1108                 (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
1109             if (bb == NULL) break;
1110             dvmCompilerClearBit(bb->predecessors, origBlock->id);
1111             dvmCompilerSetBit(bb->predecessors, bottomBlock->id);
1112         }
1113     }
1114
1115     origBlock->lastMIRInsn = insn->prev;
1116     /* Only the bottom half of split blocks is tagged as BA_ENDS_WITH_THROW */
1117     origBlock->blockAttributes &= ~BA_ENDS_WITH_THROW;
1118
1119     insn->prev->next = NULL;
1120     insn->prev = NULL;
1121     return bottomBlock;
1122 }
1123
1124 /*
1125  * Given a code offset, find out the block that starts with it. If the offset
1126  * is in the middle of an existing block, split it into two.
1127  */
1128 static BasicBlock *findBlock(CompilationUnit *cUnit,
1129                              unsigned int codeOffset,
1130                              bool split, bool create)
1131 {
1132     GrowableList *blockList = &cUnit->blockList;
1133     BasicBlock *bb;
1134     unsigned int i;
1135
1136     for (i = 0; i < blockList->numUsed; i++) {
1137         bb = (BasicBlock *) blockList->elemList[i];
1138         if (bb->blockType != kDalvikByteCode) continue;
1139         if (bb->startOffset == codeOffset) return bb;
1140         /* Check if a branch jumps into the middle of an existing block */
1141         if ((split == true) && (codeOffset > bb->startOffset) &&
1142             (bb->lastMIRInsn != NULL) &&
1143             (codeOffset <= bb->lastMIRInsn->offset)) {
1144             BasicBlock *newBB = splitBlock(cUnit, codeOffset, bb);
1145             return newBB;
1146         }
1147     }
1148     if (create) {
1149           bb = dvmCompilerNewBB(kDalvikByteCode, cUnit->numBlocks++);
1150           dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bb);
1151           bb->startOffset = codeOffset;
1152           return bb;
1153     }
1154     return NULL;
1155 }
1156
1157 /* Dump the CFG into a DOT graph */
1158 void dumpCFG(CompilationUnit *cUnit, const char *dirPrefix)
1159 {
1160     const Method *method = cUnit->method;
1161     FILE *file;
1162     char* signature = dexProtoCopyMethodDescriptor(&method->prototype);
1163     char *fileName = (char *) dvmCompilerNew(
1164                                   strlen(dirPrefix) +
1165                                   strlen(method->clazz->descriptor) +
1166                                   strlen(method->name) +
1167                                   strlen(signature) +
1168                                   strlen(".dot") + 1, true);
1169     sprintf(fileName, "%s%s%s%s.dot", dirPrefix,
1170             method->clazz->descriptor, method->name, signature);
1171     free(signature);
1172
1173     /*
1174      * Convert the special characters into a filesystem- and shell-friendly
1175      * format.
1176      */
1177     int i;
1178     for (i = strlen(dirPrefix); fileName[i]; i++) {
1179         if (fileName[i] == '/') {
1180             fileName[i] = '_';
1181         } else if (fileName[i] == ';') {
1182             fileName[i] = '#';
1183         } else if (fileName[i] == '$') {
1184             fileName[i] = '+';
1185         } else if (fileName[i] == '(' || fileName[i] == ')') {
1186             fileName[i] = '@';
1187         } else if (fileName[i] == '<' || fileName[i] == '>') {
1188             fileName[i] = '=';
1189         }
1190     }
1191     file = fopen(fileName, "w");
1192     if (file == NULL) {
1193         return;
1194     }
1195     fprintf(file, "digraph G {\n");
1196
1197     fprintf(file, "  rankdir=TB\n");
1198
1199     int numReachableBlocks = cUnit->numReachableBlocks;
1200     int idx;
1201     const GrowableList *blockList = &cUnit->blockList;
1202
1203     for (idx = 0; idx < numReachableBlocks; idx++) {
1204         int blockIdx = cUnit->dfsOrder.elemList[idx];
1205         BasicBlock *bb = (BasicBlock *) dvmGrowableListGetElement(blockList,
1206                                                                   blockIdx);
1207         if (bb == NULL) break;
1208         if (bb->blockType == kMethodEntryBlock) {
1209             fprintf(file, "  entry [shape=Mdiamond];\n");
1210         } else if (bb->blockType == kMethodExitBlock) {
1211             fprintf(file, "  exit [shape=Mdiamond];\n");
1212         } else if (bb->blockType == kDalvikByteCode) {
1213             fprintf(file, "  block%04x [shape=%s,label = \"{ \\\n",
1214                     bb->startOffset,
1215                     bb->blockAttributes & BA_CATCH_BLOCK ?
1216                       "Mrecord" : "record");
1217             if (bb->blockAttributes & BA_CATCH_BLOCK) {
1218                 if (bb->exceptionTypeIdx == kDexNoIndex) {
1219                     fprintf(file, "    {any\\l} |\\\n");
1220                 } else {
1221                     fprintf(file, "    {throwable type:%x\\l} |\\\n",
1222                             bb->exceptionTypeIdx);
1223                 }
1224             }
1225             const MIR *mir;
1226             for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1227                 fprintf(file, "    {%04x %s\\l}%s\\\n", mir->offset,
1228                         dvmCompilerFullDisassembler(cUnit, mir),
1229                         mir->next ? " | " : " ");
1230             }
1231             fprintf(file, "  }\"];\n\n");
1232         } else if (bb->blockType == kExceptionHandling) {
1233             char blockName[BLOCK_NAME_LEN];
1234
1235             dvmGetBlockName(bb, blockName);
1236             fprintf(file, "  %s [shape=invhouse];\n", blockName);
1237         }
1238
1239         char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
1240
1241         if (bb->taken) {
1242             dvmGetBlockName(bb, blockName1);
1243             dvmGetBlockName(bb->taken, blockName2);
1244             fprintf(file, "  %s:s -> %s:n [style=dotted]\n",
1245                     blockName1, blockName2);
1246         }
1247         if (bb->fallThrough) {
1248             dvmGetBlockName(bb, blockName1);
1249             dvmGetBlockName(bb->fallThrough, blockName2);
1250             fprintf(file, "  %s:s -> %s:n\n", blockName1, blockName2);
1251         }
1252
1253         if (bb->successorBlockList.blockListType != kNotUsed) {
1254             fprintf(file, "  succ%04x [shape=%s,label = \"{ \\\n",
1255                     bb->startOffset,
1256                     (bb->successorBlockList.blockListType == kCatch) ?
1257                         "Mrecord" : "record");
1258             GrowableListIterator iterator;
1259             dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
1260                                         &iterator);
1261
1262             BasicBlock *destBlock =
1263                 (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
1264
1265             int succId = 0;
1266             while (true) {
1267                 if (destBlock == NULL) break;
1268                 BasicBlock *nextBlock =
1269                     (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
1270                 fprintf(file, "    {<f%d> %04x\\l}%s\\\n",
1271                         succId++,
1272                         destBlock->startOffset,
1273                         (nextBlock != NULL) ? " | " : " ");
1274                 destBlock = nextBlock;
1275             }
1276             fprintf(file, "  }\"];\n\n");
1277
1278             dvmGetBlockName(bb, blockName1);
1279             fprintf(file, "  %s:s -> succ%04x:n [style=dashed]\n",
1280                     blockName1, bb->startOffset);
1281
1282             if (bb->successorBlockList.blockListType == kPackedSwitch ||
1283                 bb->successorBlockList.blockListType == kSparseSwitch) {
1284
1285                 dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
1286                                             &iterator);
1287
1288                 succId = 0;
1289                 while (true) {
1290                     BasicBlock *destBlock =
1291                         (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
1292                     if (destBlock == NULL) break;
1293
1294                     dvmGetBlockName(destBlock, blockName2);
1295                     fprintf(file, "  succ%04x:f%d:e -> %s:n\n",
1296                             bb->startOffset, succId++,
1297                             blockName2);
1298                 }
1299             }
1300         }
1301         fprintf(file, "\n");
1302
1303         /*
1304          * If we need to debug the dominator tree, uncomment the following code
1305          */
1306 #if 0
1307         dvmGetBlockName(bb, blockName1);
1308         fprintf(file, "  cfg%s [label=\"%s\", shape=none];\n",
1309                 blockName1, blockName1);
1310         if (bb->iDom) {
1311             dvmGetBlockName(bb->iDom, blockName2);
1312             fprintf(file, "  cfg%s:s -> cfg%s:n\n\n",
1313                     blockName2, blockName1);
1314         }
1315 #endif
1316     }
1317     fprintf(file, "}\n");
1318     fclose(file);
1319 }
1320
1321 /* Verify if all the successor is connected with all the claimed predecessors */
1322 static bool verifyPredInfo(CompilationUnit *cUnit, BasicBlock *bb)
1323 {
1324     BitVectorIterator bvIterator;
1325
1326     dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
1327     while (true) {
1328         int blockIdx = dvmBitVectorIteratorNext(&bvIterator);
1329         if (blockIdx == -1) break;
1330         BasicBlock *predBB = (BasicBlock *)
1331             dvmGrowableListGetElement(&cUnit->blockList, blockIdx);
1332         bool found = false;
1333         if (predBB->taken == bb) {
1334             found = true;
1335         } else if (predBB->fallThrough == bb) {
1336             found = true;
1337         } else if (predBB->successorBlockList.blockListType != kNotUsed) {
1338             GrowableListIterator iterator;
1339             dvmGrowableListIteratorInit(&predBB->successorBlockList.blocks,
1340                                         &iterator);
1341             while (true) {
1342                 BasicBlock *succBB =
1343                     (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
1344                 if (succBB == NULL) break;
1345                 if (succBB == bb) {
1346                     found = true;
1347                     break;
1348                 }
1349             }
1350         }
1351         if (found == false) {
1352             char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
1353             dvmGetBlockName(bb, blockName1);
1354             dvmGetBlockName(predBB, blockName2);
1355             dumpCFG(cUnit, "/data/tombstones/");
1356             LOGE("Successor %s not found from %s",
1357                  blockName1, blockName2);
1358             dvmAbort();
1359         }
1360     }
1361     return true;
1362 }
1363
1364 /* Identify code range in try blocks and set up the empty catch blocks */
1365 static void processTryCatchBlocks(CompilationUnit *cUnit)
1366 {
1367     const Method *meth = cUnit->method;
1368     const DexCode *pCode = dvmGetMethodCode(meth);
1369     int triesSize = pCode->triesSize;
1370     int i;
1371     int offset;
1372
1373     if (triesSize == 0) {
1374         return;
1375     }
1376
1377     const DexTry *pTries = dexGetTries(pCode);
1378     BitVector *tryBlockAddr = cUnit->tryBlockAddr;
1379
1380     /* Mark all the insn offsets in Try blocks */
1381     for (i = 0; i < triesSize; i++) {
1382         const DexTry* pTry = &pTries[i];
1383         /* all in 16-bit units */
1384         int startOffset = pTry->startAddr;
1385         int endOffset = startOffset + pTry->insnCount;
1386
1387         for (offset = startOffset; offset < endOffset; offset++) {
1388             dvmCompilerSetBit(tryBlockAddr, offset);
1389         }
1390     }
1391
1392     /* Iterate over each of the handlers to enqueue the empty Catch blocks */
1393     offset = dexGetFirstHandlerOffset(pCode);
1394     int handlersSize = dexGetHandlersSize(pCode);
1395
1396     for (i = 0; i < handlersSize; i++) {
1397         DexCatchIterator iterator;
1398         dexCatchIteratorInit(&iterator, pCode, offset);
1399
1400         for (;;) {
1401             DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
1402
1403             if (handler == NULL) {
1404                 break;
1405             }
1406
1407             BasicBlock *catchBlock = findBlock(cUnit, handler->address,
1408                                                /* split */
1409                                                false,
1410                                                /* create */
1411                                                true);
1412             catchBlock->blockAttributes |= BA_CATCH_BLOCK;
1413             catchBlock->exceptionTypeIdx = handler->typeIdx;
1414         }
1415
1416         offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
1417     }
1418 }
1419
1420 /* Process instructions with the kInstrCanBranch flag */
1421 static void processCanBranch(CompilationUnit *cUnit, BasicBlock *curBlock,
1422                              MIR *insn, int curOffset, int width, int flags,
1423                              const u2* codePtr, const u2* codeEnd)
1424 {
1425     int target = curOffset;
1426     switch (insn->dalvikInsn.opcode) {
1427         case OP_GOTO:
1428         case OP_GOTO_16:
1429         case OP_GOTO_32:
1430             target += (int) insn->dalvikInsn.vA;
1431             break;
1432         case OP_IF_EQ:
1433         case OP_IF_NE:
1434         case OP_IF_LT:
1435         case OP_IF_GE:
1436         case OP_IF_GT:
1437         case OP_IF_LE:
1438             target += (int) insn->dalvikInsn.vC;
1439             break;
1440         case OP_IF_EQZ:
1441         case OP_IF_NEZ:
1442         case OP_IF_LTZ:
1443         case OP_IF_GEZ:
1444         case OP_IF_GTZ:
1445         case OP_IF_LEZ:
1446             target += (int) insn->dalvikInsn.vB;
1447             break;
1448         default:
1449             LOGE("Unexpected opcode(%d) with kInstrCanBranch set",
1450                  insn->dalvikInsn.opcode);
1451             dvmAbort();
1452     }
1453     BasicBlock *takenBlock = findBlock(cUnit, target,
1454                                        /* split */
1455                                        true,
1456                                        /* create */
1457                                        true);
1458     curBlock->taken = takenBlock;
1459     dvmCompilerSetBit(takenBlock->predecessors, curBlock->id);
1460
1461     /* Always terminate the current block for conditional branches */
1462     if (flags & kInstrCanContinue) {
1463         BasicBlock *fallthroughBlock = findBlock(cUnit,
1464                                                  curOffset +  width,
1465                                                  /* split */
1466                                                  false,
1467                                                  /* create */
1468                                                  true);
1469         curBlock->fallThrough = fallthroughBlock;
1470         dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
1471     } else if (codePtr < codeEnd) {
1472         /* Create a fallthrough block for real instructions (incl. OP_NOP) */
1473         if (contentIsInsn(codePtr)) {
1474             findBlock(cUnit, curOffset + width,
1475                       /* split */
1476                       false,
1477                       /* create */
1478                       true);
1479         }
1480     }
1481 }
1482
1483 /* Process instructions with the kInstrCanSwitch flag */
1484 static void processCanSwitch(CompilationUnit *cUnit, BasicBlock *curBlock,
1485                              MIR *insn, int curOffset, int width, int flags)
1486 {
1487     u2 *switchData= (u2 *) (cUnit->method->insns + curOffset +
1488                             insn->dalvikInsn.vB);
1489     int size;
1490     int *targetTable;
1491     int i;
1492
1493     /*
1494      * Packed switch data format:
1495      *  ushort ident = 0x0100   magic value
1496      *  ushort size             number of entries in the table
1497      *  int first_key           first (and lowest) switch case value
1498      *  int targets[size]       branch targets, relative to switch opcode
1499      *
1500      * Total size is (4+size*2) 16-bit code units.
1501      */
1502     if (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) {
1503         assert(switchData[0] == kPackedSwitchSignature);
1504         size = switchData[1];
1505         targetTable = (int *) &switchData[4];
1506     /*
1507      * Sparse switch data format:
1508      *  ushort ident = 0x0200   magic value
1509      *  ushort size             number of entries in the table; > 0
1510      *  int keys[size]          keys, sorted low-to-high; 32-bit aligned
1511      *  int targets[size]       branch targets, relative to switch opcode
1512      *
1513      * Total size is (2+size*4) 16-bit code units.
1514      */
1515     } else {
1516         assert(switchData[0] == kSparseSwitchSignature);
1517         size = switchData[1];
1518         targetTable = (int *) &switchData[2 + size*2];
1519     }
1520
1521     if (curBlock->successorBlockList.blockListType != kNotUsed) {
1522         LOGE("Successor block list already in use: %d",
1523              curBlock->successorBlockList.blockListType);
1524         dvmAbort();
1525     }
1526     curBlock->successorBlockList.blockListType =
1527         (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) ?
1528         kPackedSwitch : kSparseSwitch;
1529     dvmInitGrowableList(&curBlock->successorBlockList.blocks, size);
1530
1531     for (i = 0; i < size; i++) {
1532         BasicBlock *caseBlock = findBlock(cUnit, curOffset + targetTable[i],
1533                                           /* split */
1534                                           true,
1535                                           /* create */
1536                                           true);
1537         dvmInsertGrowableList(&curBlock->successorBlockList.blocks,
1538                               (intptr_t) caseBlock);
1539         dvmCompilerSetBit(caseBlock->predecessors, curBlock->id);
1540     }
1541
1542     /* Fall-through case */
1543     BasicBlock *fallthroughBlock = findBlock(cUnit,
1544                                              curOffset +  width,
1545                                              /* split */
1546                                              false,
1547                                              /* create */
1548                                              true);
1549     curBlock->fallThrough = fallthroughBlock;
1550     dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
1551 }
1552
1553 /* Process instructions with the kInstrCanThrow flag */
1554 static void processCanThrow(CompilationUnit *cUnit, BasicBlock *curBlock,
1555                             MIR *insn, int curOffset, int width, int flags,
1556                             BitVector *tryBlockAddr, const u2 *codePtr,
1557                             const u2* codeEnd)
1558 {
1559     const Method *method = cUnit->method;
1560     const DexCode *dexCode = dvmGetMethodCode(method);
1561
1562     curBlock->blockAttributes |= BA_ENDS_WITH_THROW;
1563     /* In try block */
1564     if (dvmIsBitSet(tryBlockAddr, curOffset)) {
1565         DexCatchIterator iterator;
1566
1567         if (!dexFindCatchHandler(&iterator, dexCode, curOffset)) {
1568             LOGE("Catch block not found in dexfile for insn %x in %s",
1569                  curOffset, method->name);
1570             dvmAbort();
1571
1572         }
1573         if (curBlock->successorBlockList.blockListType != kNotUsed) {
1574             LOGE("Successor block list already in use: %d",
1575                  curBlock->successorBlockList.blockListType);
1576             dvmAbort();
1577         }
1578         curBlock->successorBlockList.blockListType = kCatch;
1579         dvmInitGrowableList(&curBlock->successorBlockList.blocks, 2);
1580
1581         for (;;) {
1582             DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
1583
1584             if (handler == NULL) {
1585                 break;
1586             }
1587
1588             BasicBlock *catchBlock = findBlock(cUnit, handler->address,
1589                                                /* split */
1590                                                false,
1591                                                /* create */
1592                                                false);
1593
1594             assert(catchBlock->blockAttributes & BA_CATCH_BLOCK);
1595             dvmInsertGrowableList(&curBlock->successorBlockList.blocks,
1596                                   (intptr_t) catchBlock);
1597             dvmCompilerSetBit(catchBlock->predecessors, curBlock->id);
1598         }
1599     } else {
1600         BasicBlock *ehBlock = dvmCompilerNewBB(kExceptionHandling,
1601                                                cUnit->numBlocks++);
1602         curBlock->taken = ehBlock;
1603         dvmInsertGrowableList(&cUnit->blockList, (intptr_t) ehBlock);
1604         ehBlock->startOffset = curOffset;
1605         dvmCompilerSetBit(ehBlock->predecessors, curBlock->id);
1606     }
1607
1608     /*
1609      * Force the current block to terminate.
1610      *
1611      * Data may be present before codeEnd, so we need to parse it to know
1612      * whether it is code or data.
1613      */
1614     if (codePtr < codeEnd) {
1615         /* Create a fallthrough block for real instructions (incl. OP_NOP) */
1616         if (contentIsInsn(codePtr)) {
1617             BasicBlock *fallthroughBlock = findBlock(cUnit,
1618                                                      curOffset + width,
1619                                                      /* split */
1620                                                      false,
1621                                                      /* create */
1622                                                      true);
1623             /*
1624              * OP_THROW and OP_THROW_VERIFICATION_ERROR are unconditional
1625              * branches.
1626              */
1627             if (insn->dalvikInsn.opcode != OP_THROW_VERIFICATION_ERROR &&
1628                 insn->dalvikInsn.opcode != OP_THROW) {
1629                 curBlock->fallThrough = fallthroughBlock;
1630                 dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
1631             }
1632         }
1633     }
1634 }
1635
1636 /*
1637  * Similar to dvmCompileTrace, but the entity processed here is the whole
1638  * method.
1639  *
1640  * TODO: implementation will be revisited when the trace builder can provide
1641  * whole-method traces.
1642  */
1643 bool dvmCompileMethod(const Method *method)
1644 {
1645     CompilationUnit cUnit;
1646     const DexCode *dexCode = dvmGetMethodCode(method);
1647     const u2 *codePtr = dexCode->insns;
1648     const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
1649     int numBlocks = 0;
1650     unsigned int curOffset = 0;
1651
1652     memset(&cUnit, 0, sizeof(cUnit));
1653     cUnit.method = method;
1654
1655     /* Initialize the block list */
1656     dvmInitGrowableList(&cUnit.blockList, 4);
1657
1658     /* Allocate the bit-vector to track the beginning of basic blocks */
1659     BitVector *tryBlockAddr = dvmCompilerAllocBitVector(dexCode->insnsSize,
1660                                                         true /* expandable */);
1661     cUnit.tryBlockAddr = tryBlockAddr;
1662
1663     /* Create the default entry and exit blocks and enter them to the list */
1664     BasicBlock *entryBlock = dvmCompilerNewBB(kMethodEntryBlock, numBlocks++);
1665     BasicBlock *exitBlock = dvmCompilerNewBB(kMethodExitBlock, numBlocks++);
1666
1667     cUnit.entryBlock = entryBlock;
1668     cUnit.exitBlock = exitBlock;
1669
1670     dvmInsertGrowableList(&cUnit.blockList, (intptr_t) entryBlock);
1671     dvmInsertGrowableList(&cUnit.blockList, (intptr_t) exitBlock);
1672
1673     /* Current block to record parsed instructions */
1674     BasicBlock *curBlock = dvmCompilerNewBB(kDalvikByteCode, numBlocks++);
1675     curBlock->startOffset = 0;
1676     dvmInsertGrowableList(&cUnit.blockList, (intptr_t) curBlock);
1677     entryBlock->fallThrough = curBlock;
1678     dvmCompilerSetBit(curBlock->predecessors, entryBlock->id);
1679
1680     /*
1681      * Store back the number of blocks since new blocks may be created of
1682      * accessing cUnit.
1683      */
1684     cUnit.numBlocks = numBlocks;
1685
1686     /* Identify code range in try blocks and set up the empty catch blocks */
1687     processTryCatchBlocks(&cUnit);
1688
1689     /* Parse all instructions and put them into containing basic blocks */
1690     while (codePtr < codeEnd) {
1691         MIR *insn = (MIR *) dvmCompilerNew(sizeof(MIR), true);
1692         insn->offset = curOffset;
1693         int width = parseInsn(codePtr, &insn->dalvikInsn, false);
1694         insn->width = width;
1695
1696         /* Terminate when the data section is seen */
1697         if (width == 0)
1698             break;
1699
1700         dvmCompilerAppendMIR(curBlock, insn);
1701
1702         codePtr += width;
1703         int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode);
1704
1705         if (flags & kInstrCanBranch) {
1706             processCanBranch(&cUnit, curBlock, insn, curOffset, width, flags,
1707                              codePtr, codeEnd);
1708         } else if (flags & kInstrCanReturn) {
1709             curBlock->fallThrough = exitBlock;
1710             dvmCompilerSetBit(exitBlock->predecessors, curBlock->id);
1711             /*
1712              * Terminate the current block if there are instructions
1713              * afterwards.
1714              */
1715             if (codePtr < codeEnd) {
1716                 /*
1717                  * Create a fallthrough block for real instructions
1718                  * (incl. OP_NOP).
1719                  */
1720                 if (contentIsInsn(codePtr)) {
1721                     findBlock(&cUnit, curOffset + width,
1722                               /* split */
1723                               false,
1724                               /* create */
1725                               true);
1726                 }
1727             }
1728         } else if (flags & kInstrCanThrow) {
1729             processCanThrow(&cUnit, curBlock, insn, curOffset, width, flags,
1730                             tryBlockAddr, codePtr, codeEnd);
1731         } else if (flags & kInstrCanSwitch) {
1732             processCanSwitch(&cUnit, curBlock, insn, curOffset, width, flags);
1733         }
1734         curOffset += width;
1735         BasicBlock *nextBlock = findBlock(&cUnit, curOffset,
1736                                           /* split */
1737                                           false,
1738                                           /* create */
1739                                           false);
1740         if (nextBlock) {
1741             /*
1742              * The next instruction could be the target of a previously parsed
1743              * forward branch so a block is already created. If the current
1744              * instruction is not an unconditional branch, connect them through
1745              * the fall-through link.
1746              */
1747             assert(curBlock->fallThrough == NULL ||
1748                    curBlock->fallThrough == nextBlock ||
1749                    curBlock->fallThrough == exitBlock);
1750
1751             if ((curBlock->fallThrough == NULL) &&
1752                 !dexIsGoto(flags) &&
1753                 !(flags & kInstrCanReturn)) {
1754                 curBlock->fallThrough = nextBlock;
1755                 dvmCompilerSetBit(nextBlock->predecessors, curBlock->id);
1756             }
1757             curBlock = nextBlock;
1758         }
1759     }
1760
1761     /* Adjust this value accordingly once inlining is performed */
1762     cUnit.numDalvikRegisters = cUnit.method->registersSize;
1763
1764     /* Verify if all blocks are connected as claimed */
1765     /* FIXME - to be disabled in the future */
1766     dvmCompilerDataFlowAnalysisDispatcher(&cUnit, verifyPredInfo,
1767                                           kAllNodes,
1768                                           false /* isIterative */);
1769
1770
1771     /* Perform SSA transformation for the whole method */
1772     dvmCompilerMethodSSATransformation(&cUnit);
1773
1774     if (cUnit.printMe) dumpCFG(&cUnit, "/data/tombstones/");
1775
1776     /* Reset the compiler resource pool */
1777     dvmCompilerArenaReset();
1778
1779     return false;
1780 }