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