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 { 541 MIR *insn = origBlock->firstMIRInsn; 542 while (insn) { 543 if (insn->offset == codeOffset) break; 544 insn = insn->next; 545 } 546 if (insn == NULL) { 547 LOGE("Break split failed"); 548 dvmAbort(); 549 } 550 BasicBlock *bottomBlock = dvmCompilerNewBB(kDalvikByteCode, 551 cUnit->numBlocks++); 552 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bottomBlock); 553 554 bottomBlock->startOffset = codeOffset; 555 bottomBlock->firstMIRInsn = insn; 556 bottomBlock->lastMIRInsn = origBlock->lastMIRInsn; 557 558 /* Handle the taken path */ 559 bottomBlock->taken = origBlock->taken; 560 if (bottomBlock->taken) { 561 origBlock->taken = NULL; 562 dvmCompilerClearBit(bottomBlock->taken->predecessors, origBlock->id); 563 dvmCompilerSetBit(bottomBlock->taken->predecessors, bottomBlock->id); 564 } 565 566 /* Handle the fallthrough path */ 567 bottomBlock->needFallThroughBranch = origBlock->needFallThroughBranch; 568 bottomBlock->fallThrough = origBlock->fallThrough; 569 origBlock->fallThrough = bottomBlock; 570 origBlock->needFallThroughBranch = true; 571 dvmCompilerSetBit(bottomBlock->predecessors, origBlock->id); 572 if (bottomBlock->fallThrough) { 573 dvmCompilerClearBit(bottomBlock->fallThrough->predecessors, 574 origBlock->id); 575 dvmCompilerSetBit(bottomBlock->fallThrough->predecessors, 576 bottomBlock->id); 577 } 578 579 /* Handle the successor list */ 580 if (origBlock->successorBlockList.blockListType != kNotUsed) { 581 bottomBlock->successorBlockList = origBlock->successorBlockList; 582 origBlock->successorBlockList.blockListType = kNotUsed; 583 GrowableListIterator iterator; 584 585 dvmGrowableListIteratorInit(&bottomBlock->successorBlockList.blocks, 586 &iterator); 587 while (true) { 588 SuccessorBlockInfo *successorBlockInfo = 589 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); 590 if (successorBlockInfo == NULL) break; 591 BasicBlock *bb = successorBlockInfo->block; 592 dvmCompilerClearBit(bb->predecessors, origBlock->id); 593 dvmCompilerSetBit(bb->predecessors, bottomBlock->id); 594 } 595 } 596 597 origBlock->lastMIRInsn = insn->prev; 598 599 insn->prev->next = NULL; 600 insn->prev = NULL; 601 return bottomBlock; 602 } 603 604 /* 605 * Given a code offset, find out the block that starts with it. If the offset 606 * is in the middle of an existing block, split it into two. 607 */ 608 static BasicBlock *findBlock(CompilationUnit *cUnit, 609 unsigned int codeOffset, 610 bool split, bool create) 611 { 612 GrowableList *blockList = &cUnit->blockList; 613 BasicBlock *bb; 614 unsigned int i; 615 616 for (i = 0; i < blockList->numUsed; i++) { 617 bb = (BasicBlock *) blockList->elemList[i]; 618 if (bb->blockType != kDalvikByteCode) continue; 619 if (bb->startOffset == codeOffset) return bb; 620 /* Check if a branch jumps into the middle of an existing block */ 621 if ((split == true) && (codeOffset > bb->startOffset) && 622 (bb->lastMIRInsn != NULL) && 623 (codeOffset <= bb->lastMIRInsn->offset)) { 624 BasicBlock *newBB = splitBlock(cUnit, codeOffset, bb); 625 return newBB; 626 } 627 } 628 if (create) { 629 bb = dvmCompilerNewBB(kDalvikByteCode, cUnit->numBlocks++); 630 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bb); 631 bb->startOffset = codeOffset; 632 return bb; 633 } 634 return NULL; 635 } 636 637 /* Dump the CFG into a DOT graph */ 638 void dvmDumpCFG(CompilationUnit *cUnit, const char *dirPrefix) 639 { 640 const Method *method = cUnit->method; 641 FILE *file; 642 char *signature = dexProtoCopyMethodDescriptor(&method->prototype); 643 char startOffset[80]; 644 sprintf(startOffset, "_%x", cUnit->entryBlock->fallThrough->startOffset); 645 char *fileName = (char *) dvmCompilerNew( 646 strlen(dirPrefix) + 647 strlen(method->clazz->descriptor) + 648 strlen(method->name) + 649 strlen(signature) + 650 strlen(startOffset) + 651 strlen(".dot") + 1, true); 652 sprintf(fileName, "%s%s%s%s%s.dot", dirPrefix, 653 method->clazz->descriptor, method->name, signature, startOffset); 654 free(signature); 655 656 /* 657 * Convert the special characters into a filesystem- and shell-friendly 658 * format. 659 */ 660 int i; 661 for (i = strlen(dirPrefix); fileName[i]; i++) { 662 if (fileName[i] == '/') { 663 fileName[i] = '_'; 664 } else if (fileName[i] == ';') { 665 fileName[i] = '#'; 666 } else if (fileName[i] == '$') { 667 fileName[i] = '+'; 668 } else if (fileName[i] == '(' || fileName[i] == ')') { 669 fileName[i] = '@'; 670 } else if (fileName[i] == '<' || fileName[i] == '>') { 671 fileName[i] = '='; 672 } 673 } 674 file = fopen(fileName, "w"); 675 if (file == NULL) { 676 return; 677 } 678 fprintf(file, "digraph G {\n"); 679 680 fprintf(file, " rankdir=TB\n"); 681 682 int numReachableBlocks = cUnit->numReachableBlocks; 683 int idx; 684 const GrowableList *blockList = &cUnit->blockList; 685 686 for (idx = 0; idx < numReachableBlocks; idx++) { 687 int blockIdx = cUnit->dfsOrder.elemList[idx]; 688 BasicBlock *bb = (BasicBlock *) dvmGrowableListGetElement(blockList, 689 blockIdx); 690 if (bb == NULL) break; 691 if (bb->blockType == kEntryBlock) { 692 fprintf(file, " entry [shape=Mdiamond];\n"); 693 } else if (bb->blockType == kExitBlock) { 694 fprintf(file, " exit [shape=Mdiamond];\n"); 695 } else if (bb->blockType == kDalvikByteCode) { 696 fprintf(file, " block%04x [shape=record,label = \"{ \\\n", 697 bb->startOffset); 698 const MIR *mir; 699 fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 700 bb->firstMIRInsn ? " | " : " "); 701 for (mir = bb->firstMIRInsn; mir; mir = mir->next) { 702 fprintf(file, " {%04x %s\\l}%s\\\n", mir->offset, 703 mir->ssaRep ? 704 dvmCompilerFullDisassembler(cUnit, mir) : 705 dexGetOpcodeName(mir->dalvikInsn.opcode), 706 mir->next ? " | " : " "); 707 } 708 fprintf(file, " }\"];\n\n"); 709 } else if (bb->blockType == kExceptionHandling) { 710 char blockName[BLOCK_NAME_LEN]; 711 712 dvmGetBlockName(bb, blockName); 713 fprintf(file, " %s [shape=invhouse];\n", blockName); 714 } 715 716 char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN]; 717 718 if (bb->taken) { 719 dvmGetBlockName(bb, blockName1); 720 dvmGetBlockName(bb->taken, blockName2); 721 fprintf(file, " %s:s -> %s:n [style=dotted]\n", 722 blockName1, blockName2); 723 } 724 if (bb->fallThrough) { 725 dvmGetBlockName(bb, blockName1); 726 dvmGetBlockName(bb->fallThrough, blockName2); 727 fprintf(file, " %s:s -> %s:n\n", blockName1, blockName2); 728 } 729 730 if (bb->successorBlockList.blockListType != kNotUsed) { 731 fprintf(file, " succ%04x [shape=%s,label = \"{ \\\n", 732 bb->startOffset, 733 (bb->successorBlockList.blockListType == kCatch) ? 734 "Mrecord" : "record"); 735 GrowableListIterator iterator; 736 dvmGrowableListIteratorInit(&bb->successorBlockList.blocks, 737 &iterator); 738 SuccessorBlockInfo *successorBlockInfo = 739 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); 740 741 int succId = 0; 742 while (true) { 743 if (successorBlockInfo == NULL) break; 744 745 BasicBlock *destBlock = successorBlockInfo->block; 746 SuccessorBlockInfo *nextSuccessorBlockInfo = 747 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); 748 749 fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 750 succId++, 751 successorBlockInfo->key, 752 destBlock->startOffset, 753 (nextSuccessorBlockInfo != NULL) ? " | " : " "); 754 755 successorBlockInfo = nextSuccessorBlockInfo; 756 } 757 fprintf(file, " }\"];\n\n"); 758 759 dvmGetBlockName(bb, blockName1); 760 fprintf(file, " %s:s -> succ%04x:n [style=dashed]\n", 761 blockName1, bb->startOffset); 762 763 if (bb->successorBlockList.blockListType == kPackedSwitch || 764 bb->successorBlockList.blockListType == kSparseSwitch) { 765 766 dvmGrowableListIteratorInit(&bb->successorBlockList.blocks, 767 &iterator); 768 769 succId = 0; 770 while (true) { 771 SuccessorBlockInfo *successorBlockInfo = 772 (SuccessorBlockInfo *) 773 dvmGrowableListIteratorNext(&iterator); 774 if (successorBlockInfo == NULL) break; 775 776 BasicBlock *destBlock = successorBlockInfo->block; 777 778 dvmGetBlockName(destBlock, blockName2); 779 fprintf(file, " succ%04x:f%d:e -> %s:n\n", 780 bb->startOffset, succId++, 781 blockName2); 782 } 783 } 784 } 785 fprintf(file, "\n"); 786 787 /* 788 * If we need to debug the dominator tree, uncomment the following code 789 */ 790 #if 1 791 dvmGetBlockName(bb, blockName1); 792 fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 793 blockName1, blockName1); 794 if (bb->iDom) { 795 dvmGetBlockName(bb->iDom, blockName2); 796 fprintf(file, " cfg%s:s -> cfg%s:n\n\n", 797 blockName2, blockName1); 798 } 799 #endif 800 } 801 fprintf(file, "}\n"); 802 fclose(file); 803 } 804 805 /* Verify if all the successor is connected with all the claimed predecessors */ 806 static bool verifyPredInfo(CompilationUnit *cUnit, BasicBlock *bb) 807 { 808 BitVectorIterator bvIterator; 809 810 dvmBitVectorIteratorInit(bb->predecessors, &bvIterator); 811 while (true) { 812 int blockIdx = dvmBitVectorIteratorNext(&bvIterator); 813 if (blockIdx == -1) break; 814 BasicBlock *predBB = (BasicBlock *) 815 dvmGrowableListGetElement(&cUnit->blockList, blockIdx); 816 bool found = false; 817 if (predBB->taken == bb) { 818 found = true; 819 } else if (predBB->fallThrough == bb) { 820 found = true; 821 } else if (predBB->successorBlockList.blockListType != kNotUsed) { 822 GrowableListIterator iterator; 823 dvmGrowableListIteratorInit(&predBB->successorBlockList.blocks, 824 &iterator); 825 while (true) { 826 SuccessorBlockInfo *successorBlockInfo = 827 (SuccessorBlockInfo *) 828 dvmGrowableListIteratorNext(&iterator); 829 if (successorBlockInfo == NULL) break; 830 BasicBlock *succBB = successorBlockInfo->block; 831 if (succBB == bb) { 832 found = true; 833 break; 834 } 835 } 836 } 837 if (found == false) { 838 char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN]; 839 dvmGetBlockName(bb, blockName1); 840 dvmGetBlockName(predBB, blockName2); 841 dvmDumpCFG(cUnit, "/sdcard/cfg/"); 842 LOGE("Successor %s not found from %s", 843 blockName1, blockName2); 844 dvmAbort(); 845 } 846 } 847 return true; 848 } 849 850 /* Identify code range in try blocks and set up the empty catch blocks */ 851 static void processTryCatchBlocks(CompilationUnit *cUnit) 852 { 853 const Method *meth = cUnit->method; 854 const DexCode *pCode = dvmGetMethodCode(meth); 855 int triesSize = pCode->triesSize; 856 int i; 857 int offset; 858 859 if (triesSize == 0) { 860 return; 861 } 862 863 const DexTry *pTries = dexGetTries(pCode); 864 BitVector *tryBlockAddr = cUnit->tryBlockAddr; 865 866 /* Mark all the insn offsets in Try blocks */ 867 for (i = 0; i < triesSize; i++) { 868 const DexTry* pTry = &pTries[i]; 869 /* all in 16-bit units */ 870 int startOffset = pTry->startAddr; 871 int endOffset = startOffset + pTry->insnCount; 872 873 for (offset = startOffset; offset < endOffset; offset++) { 874 dvmCompilerSetBit(tryBlockAddr, offset); 875 } 876 } 877 878 /* Iterate over each of the handlers to enqueue the empty Catch blocks */ 879 offset = dexGetFirstHandlerOffset(pCode); 880 int handlersSize = dexGetHandlersSize(pCode); 881 882 for (i = 0; i < handlersSize; i++) { 883 DexCatchIterator iterator; 884 dexCatchIteratorInit(&iterator, pCode, offset); 885 886 for (;;) { 887 DexCatchHandler* handler = dexCatchIteratorNext(&iterator); 888 889 if (handler == NULL) { 890 break; 891 } 892 893 /* 894 * Create dummy catch blocks first. Since these are created before 895 * other blocks are processed, "split" is specified as false. 896 */ 897 findBlock(cUnit, handler->address, 898 /* split */ 899 false, 900 /* create */ 901 true); 902 } 903 904 offset = dexCatchIteratorGetEndOffset(&iterator, pCode); 905 } 906 } 907 908 /* Process instructions with the kInstrCanBranch flag */ 909 static void processCanBranch(CompilationUnit *cUnit, BasicBlock *curBlock, 910 MIR *insn, int curOffset, int width, int flags, 911 const u2* codePtr, const u2* codeEnd) 912 { 913 int target = curOffset; 914 switch (insn->dalvikInsn.opcode) { 915 case OP_GOTO: 916 case OP_GOTO_16: 917 case OP_GOTO_32: 918 target += (int) insn->dalvikInsn.vA; 919 break; 920 case OP_IF_EQ: 921 case OP_IF_NE: 922 case OP_IF_LT: 923 case OP_IF_GE: 924 case OP_IF_GT: 925 case OP_IF_LE: 926 target += (int) insn->dalvikInsn.vC; 927 break; 928 case OP_IF_EQZ: 929 case OP_IF_NEZ: 930 case OP_IF_LTZ: 931 case OP_IF_GEZ: 932 case OP_IF_GTZ: 933 case OP_IF_LEZ: 934 target += (int) insn->dalvikInsn.vB; 935 break; 936 default: 937 LOGE("Unexpected opcode(%d) with kInstrCanBranch set", 938 insn->dalvikInsn.opcode); 939 dvmAbort(); 940 } 941 BasicBlock *takenBlock = findBlock(cUnit, target, 942 /* split */ 943 true, 944 /* create */ 945 true); 946 curBlock->taken = takenBlock; 947 dvmCompilerSetBit(takenBlock->predecessors, curBlock->id); 948 949 /* Always terminate the current block for conditional branches */ 950 if (flags & kInstrCanContinue) { 951 BasicBlock *fallthroughBlock = findBlock(cUnit, 952 curOffset + width, 953 /* 954 * If the method is processed 955 * in sequential order from the 956 * beginning, we don't need to 957 * specify split for continue 958 * blocks. However, this 959 * routine can be called by 960 * compileLoop, which starts 961 * parsing the method from an 962 * arbitrary address in the 963 * method body. 964 */ 965 true, 966 /* create */ 967 true); 968 curBlock->fallThrough = fallthroughBlock; 969 dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id); 970 } else if (codePtr < codeEnd) { 971 /* Create a fallthrough block for real instructions (incl. OP_NOP) */ 972 if (contentIsInsn(codePtr)) { 973 findBlock(cUnit, curOffset + width, 974 /* split */ 975 false, 976 /* create */ 977 true); 978 } 979 } 980 } 981 982 /* Process instructions with the kInstrCanSwitch flag */ 983 static void processCanSwitch(CompilationUnit *cUnit, BasicBlock *curBlock, 984 MIR *insn, int curOffset, int width, int flags) 985 { 986 u2 *switchData= (u2 *) (cUnit->method->insns + curOffset + 987 insn->dalvikInsn.vB); 988 int size; 989 int *keyTable; 990 int *targetTable; 991 int i; 992 int firstKey; 993 994 /* 995 * Packed switch data format: 996 * ushort ident = 0x0100 magic value 997 * ushort size number of entries in the table 998 * int first_key first (and lowest) switch case value 999 * int targets[size] branch targets, relative to switch opcode 1000 * 1001 * Total size is (4+size*2) 16-bit code units. 1002 */ 1003 if (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) { 1004 assert(switchData[0] == kPackedSwitchSignature); 1005 size = switchData[1]; 1006 firstKey = switchData[2] | (switchData[3] << 16); 1007 targetTable = (int *) &switchData[4]; 1008 keyTable = NULL; // Make the compiler happy 1009 /* 1010 * Sparse switch data format: 1011 * ushort ident = 0x0200 magic value 1012 * ushort size number of entries in the table; > 0 1013 * int keys[size] keys, sorted low-to-high; 32-bit aligned 1014 * int targets[size] branch targets, relative to switch opcode 1015 * 1016 * Total size is (2+size*4) 16-bit code units. 1017 */ 1018 } else { 1019 assert(switchData[0] == kSparseSwitchSignature); 1020 size = switchData[1]; 1021 keyTable = (int *) &switchData[2]; 1022 targetTable = (int *) &switchData[2 + size*2]; 1023 firstKey = 0; // To make the compiler happy 1024 } 1025 1026 if (curBlock->successorBlockList.blockListType != kNotUsed) { 1027 LOGE("Successor block list already in use: %d", 1028 curBlock->successorBlockList.blockListType); 1029 dvmAbort(); 1030 } 1031 curBlock->successorBlockList.blockListType = 1032 (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) ? 1033 kPackedSwitch : kSparseSwitch; 1034 dvmInitGrowableList(&curBlock->successorBlockList.blocks, size); 1035 1036 for (i = 0; i < size; i++) { 1037 BasicBlock *caseBlock = findBlock(cUnit, curOffset + targetTable[i], 1038 /* split */ 1039 true, 1040 /* create */ 1041 true); 1042 SuccessorBlockInfo *successorBlockInfo = 1043 (SuccessorBlockInfo *) dvmCompilerNew(sizeof(SuccessorBlockInfo), 1044 false); 1045 successorBlockInfo->block = caseBlock; 1046 successorBlockInfo->key = (insn->dalvikInsn.opcode == OP_PACKED_SWITCH)? 1047 firstKey + i : keyTable[i]; 1048 dvmInsertGrowableList(&curBlock->successorBlockList.blocks, 1049 (intptr_t) successorBlockInfo); 1050 dvmCompilerSetBit(caseBlock->predecessors, curBlock->id); 1051 } 1052 1053 /* Fall-through case */ 1054 BasicBlock *fallthroughBlock = findBlock(cUnit, 1055 curOffset + width, 1056 /* split */ 1057 false, 1058 /* create */ 1059 true); 1060 curBlock->fallThrough = fallthroughBlock; 1061 dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id); 1062 } 1063 1064 /* Process instructions with the kInstrCanThrow flag */ 1065 static void processCanThrow(CompilationUnit *cUnit, BasicBlock *curBlock, 1066 MIR *insn, int curOffset, int width, int flags, 1067 BitVector *tryBlockAddr, const u2 *codePtr, 1068 const u2* codeEnd) 1069 { 1070 const Method *method = cUnit->method; 1071 const DexCode *dexCode = dvmGetMethodCode(method); 1072 1073 /* In try block */ 1074 if (dvmIsBitSet(tryBlockAddr, curOffset)) { 1075 DexCatchIterator iterator; 1076 1077 if (!dexFindCatchHandler(&iterator, dexCode, curOffset)) { 1078 LOGE("Catch block not found in dexfile for insn %x in %s", 1079 curOffset, method->name); 1080 dvmAbort(); 1081 1082 } 1083 if (curBlock->successorBlockList.blockListType != kNotUsed) { 1084 LOGE("Successor block list already in use: %d", 1085 curBlock->successorBlockList.blockListType); 1086 dvmAbort(); 1087 } 1088 curBlock->successorBlockList.blockListType = kCatch; 1089 dvmInitGrowableList(&curBlock->successorBlockList.blocks, 2); 1090 1091 for (;;) { 1092 DexCatchHandler* handler = dexCatchIteratorNext(&iterator); 1093 1094 if (handler == NULL) { 1095 break; 1096 } 1097 1098 BasicBlock *catchBlock = findBlock(cUnit, handler->address, 1099 /* split */ 1100 false, 1101 /* create */ 1102 false); 1103 1104 SuccessorBlockInfo *successorBlockInfo = 1105 (SuccessorBlockInfo *) dvmCompilerNew(sizeof(SuccessorBlockInfo), 1106 false); 1107 successorBlockInfo->block = catchBlock; 1108 successorBlockInfo->key = handler->typeIdx; 1109 dvmInsertGrowableList(&curBlock->successorBlockList.blocks, 1110 (intptr_t) successorBlockInfo); 1111 dvmCompilerSetBit(catchBlock->predecessors, curBlock->id); 1112 } 1113 } else { 1114 BasicBlock *ehBlock = dvmCompilerNewBB(kExceptionHandling, 1115 cUnit->numBlocks++); 1116 curBlock->taken = ehBlock; 1117 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) ehBlock); 1118 ehBlock->startOffset = curOffset; 1119 dvmCompilerSetBit(ehBlock->predecessors, curBlock->id); 1120 } 1121 1122 /* 1123 * Force the current block to terminate. 1124 * 1125 * Data may be present before codeEnd, so we need to parse it to know 1126 * whether it is code or data. 1127 */ 1128 if (codePtr < codeEnd) { 1129 /* Create a fallthrough block for real instructions (incl. OP_NOP) */ 1130 if (contentIsInsn(codePtr)) { 1131 BasicBlock *fallthroughBlock = findBlock(cUnit, 1132 curOffset + width, 1133 /* split */ 1134 false, 1135 /* create */ 1136 true); 1137 /* 1138 * OP_THROW and OP_THROW_VERIFICATION_ERROR are unconditional 1139 * branches. 1140 */ 1141 if (insn->dalvikInsn.opcode != OP_THROW_VERIFICATION_ERROR && 1142 insn->dalvikInsn.opcode != OP_THROW) { 1143 curBlock->fallThrough = fallthroughBlock; 1144 dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id); 1145 } 1146 } 1147 } 1148 } 1149 1150 /* 1151 * Similar to dvmCompileTrace, but the entity processed here is the whole 1152 * method. 1153 * 1154 * TODO: implementation will be revisited when the trace builder can provide 1155 * whole-method traces. 1156 */ 1157 bool dvmCompileMethod(const Method *method, JitTranslationInfo *info) 1158 { 1159 CompilationUnit cUnit; 1160 const DexCode *dexCode = dvmGetMethodCode(method); 1161 const u2 *codePtr = dexCode->insns; 1162 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize; 1163 int numBlocks = 0; 1164 unsigned int curOffset = 0; 1165 1166 /* Method already compiled */ 1167 if (dvmJitGetMethodAddr(codePtr)) { 1168 info->codeAddress = NULL; 1169 return false; 1170 } 1171 1172 memset(&cUnit, 0, sizeof(cUnit)); 1173 cUnit.method = method; 1174 1175 cUnit.jitMode = kJitMethod; 1176 1177 /* Initialize the block list */ 1178 dvmInitGrowableList(&cUnit.blockList, 4); 1179 1180 /* 1181 * FIXME - PC reconstruction list won't be needed after the codegen routines 1182 * are enhanced to true method mode. 1183 */ 1184 /* Initialize the PC reconstruction list */ 1185 dvmInitGrowableList(&cUnit.pcReconstructionList, 8); 1186 1187 /* Allocate the bit-vector to track the beginning of basic blocks */ 1188 BitVector *tryBlockAddr = dvmCompilerAllocBitVector(dexCode->insnsSize, 1189 true /* expandable */); 1190 cUnit.tryBlockAddr = tryBlockAddr; 1191 1192 /* Create the default entry and exit blocks and enter them to the list */ 1193 BasicBlock *entryBlock = dvmCompilerNewBB(kEntryBlock, numBlocks++); 1194 BasicBlock *exitBlock = dvmCompilerNewBB(kExitBlock, numBlocks++); 1195 1196 cUnit.entryBlock = entryBlock; 1197 cUnit.exitBlock = exitBlock; 1198 1199 dvmInsertGrowableList(&cUnit.blockList, (intptr_t) entryBlock); 1200 dvmInsertGrowableList(&cUnit.blockList, (intptr_t) exitBlock); 1201 1202 /* Current block to record parsed instructions */ 1203 BasicBlock *curBlock = dvmCompilerNewBB(kDalvikByteCode, numBlocks++); 1204 curBlock->startOffset = 0; 1205 dvmInsertGrowableList(&cUnit.blockList, (intptr_t) curBlock); 1206 entryBlock->fallThrough = curBlock; 1207 dvmCompilerSetBit(curBlock->predecessors, entryBlock->id); 1208 1209 /* 1210 * Store back the number of blocks since new blocks may be created of 1211 * accessing cUnit. 1212 */ 1213 cUnit.numBlocks = numBlocks; 1214 1215 /* Identify code range in try blocks and set up the empty catch blocks */ 1216 processTryCatchBlocks(&cUnit); 1217 1218 /* Parse all instructions and put them into containing basic blocks */ 1219 while (codePtr < codeEnd) { 1220 MIR *insn = (MIR *) dvmCompilerNew(sizeof(MIR), true); 1221 insn->offset = curOffset; 1222 int width = parseInsn(codePtr, &insn->dalvikInsn, false); 1223 insn->width = width; 1224 1225 /* Terminate when the data section is seen */ 1226 if (width == 0) 1227 break; 1228 1229 dvmCompilerAppendMIR(curBlock, insn); 1230 1231 codePtr += width; 1232 int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode); 1233 1234 if (flags & kInstrCanBranch) { 1235 processCanBranch(&cUnit, curBlock, insn, curOffset, width, flags, 1236 codePtr, codeEnd); 1237 } else if (flags & kInstrCanReturn) { 1238 curBlock->fallThrough = exitBlock; 1239 dvmCompilerSetBit(exitBlock->predecessors, curBlock->id); 1240 /* 1241 * Terminate the current block if there are instructions 1242 * afterwards. 1243 */ 1244 if (codePtr < codeEnd) { 1245 /* 1246 * Create a fallthrough block for real instructions 1247 * (incl. OP_NOP). 1248 */ 1249 if (contentIsInsn(codePtr)) { 1250 findBlock(&cUnit, curOffset + width, 1251 /* split */ 1252 false, 1253 /* create */ 1254 true); 1255 } 1256 } 1257 } else if (flags & kInstrCanThrow) { 1258 processCanThrow(&cUnit, curBlock, insn, curOffset, width, flags, 1259 tryBlockAddr, codePtr, codeEnd); 1260 } else if (flags & kInstrCanSwitch) { 1261 processCanSwitch(&cUnit, curBlock, insn, curOffset, width, flags); 1262 } 1263 curOffset += width; 1264 BasicBlock *nextBlock = findBlock(&cUnit, curOffset, 1265 /* split */ 1266 false, 1267 /* create */ 1268 false); 1269 if (nextBlock) { 1270 /* 1271 * The next instruction could be the target of a previously parsed 1272 * forward branch so a block is already created. If the current 1273 * instruction is not an unconditional branch, connect them through 1274 * the fall-through link. 1275 */ 1276 assert(curBlock->fallThrough == NULL || 1277 curBlock->fallThrough == nextBlock || 1278 curBlock->fallThrough == exitBlock); 1279 1280 if ((curBlock->fallThrough == NULL) && 1281 (flags & kInstrCanContinue)) { 1282 curBlock->fallThrough = nextBlock; 1283 dvmCompilerSetBit(nextBlock->predecessors, curBlock->id); 1284 } 1285 curBlock = nextBlock; 1286 } 1287 } 1288 1289 if (cUnit.printMe) { 1290 dvmCompilerDumpCompilationUnit(&cUnit); 1291 } 1292 1293 /* Adjust this value accordingly once inlining is performed */ 1294 cUnit.numDalvikRegisters = cUnit.method->registersSize; 1295 1296 /* Verify if all blocks are connected as claimed */ 1297 /* FIXME - to be disabled in the future */ 1298 dvmCompilerDataFlowAnalysisDispatcher(&cUnit, verifyPredInfo, 1299 kAllNodes, 1300 false /* isIterative */); 1301 1302 1303 /* Perform SSA transformation for the whole method */ 1304 dvmCompilerMethodSSATransformation(&cUnit); 1305 1306 dvmCompilerInitializeRegAlloc(&cUnit); // Needs to happen after SSA naming 1307 1308 /* Allocate Registers using simple local allocation scheme */ 1309 dvmCompilerLocalRegAlloc(&cUnit); 1310 1311 /* Convert MIR to LIR, etc. */ 1312 dvmCompilerMethodMIR2LIR(&cUnit); 1313 1314 // Debugging only 1315 //dvmDumpCFG(&cUnit, "/sdcard/cfg/"); 1316 1317 /* Method is not empty */ 1318 if (cUnit.firstLIRInsn) { 1319 /* Convert LIR into machine code. Loop for recoverable retries */ 1320 do { 1321 dvmCompilerAssembleLIR(&cUnit, info); 1322 cUnit.assemblerRetries++; 1323 if (cUnit.printMe && cUnit.assemblerStatus != kSuccess) 1324 LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries, 1325 cUnit.assemblerStatus); 1326 } while (cUnit.assemblerStatus == kRetryAll); 1327 1328 if (cUnit.printMe) { 1329 dvmCompilerCodegenDump(&cUnit); 1330 } 1331 1332 if (info->codeAddress) { 1333 dvmJitSetCodeAddr(dexCode->insns, info->codeAddress, 1334 info->instructionSet, true, 0); 1335 /* 1336 * Clear the codeAddress for the enclosing trace to reuse the info 1337 */ 1338 info->codeAddress = NULL; 1339 } 1340 } 1341 1342 return false; 1343 } 1344 1345 /* Extending the trace by crawling the code from curBlock */ 1346 static bool exhaustTrace(CompilationUnit *cUnit, BasicBlock *curBlock) 1347 { 1348 unsigned int curOffset = curBlock->startOffset; 1349 const u2 *codePtr = cUnit->method->insns + curOffset; 1350 1351 if (curBlock->visited == true) return false; 1352 1353 curBlock->visited = true; 1354 1355 if (curBlock->blockType == kEntryBlock || 1356 curBlock->blockType == kExitBlock) { 1357 return false; 1358 } 1359 1360 /* 1361 * Block has been parsed - check the taken/fallThrough in case it is a split 1362 * block. 1363 */ 1364 if (curBlock->firstMIRInsn != NULL) { 1365 bool changed = false; 1366 if (curBlock->taken) 1367 changed |= exhaustTrace(cUnit, curBlock->taken); 1368 if (curBlock->fallThrough) 1369 changed |= exhaustTrace(cUnit, curBlock->fallThrough); 1370 return changed; 1371 } 1372 while (true) { 1373 MIR *insn = (MIR *) dvmCompilerNew(sizeof(MIR), true); 1374 insn->offset = curOffset; 1375 int width = parseInsn(codePtr, &insn->dalvikInsn, false); 1376 insn->width = width; 1377 1378 /* Terminate when the data section is seen */ 1379 if (width == 0) 1380 break; 1381 1382 dvmCompilerAppendMIR(curBlock, insn); 1383 1384 codePtr += width; 1385 int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode); 1386 1387 /* Stop extending the trace after seeing these instructions */ 1388 if (flags & (kInstrCanReturn | kInstrCanSwitch | kInstrInvoke)) { 1389 curBlock->fallThrough = cUnit->exitBlock; 1390 dvmCompilerSetBit(cUnit->exitBlock->predecessors, curBlock->id); 1391 break; 1392 } else if (flags & kInstrCanBranch) { 1393 processCanBranch(cUnit, curBlock, insn, curOffset, width, flags, 1394 codePtr, NULL); 1395 if (curBlock->taken) { 1396 exhaustTrace(cUnit, curBlock->taken); 1397 } 1398 if (curBlock->fallThrough) { 1399 exhaustTrace(cUnit, curBlock->fallThrough); 1400 } 1401 break; 1402 } 1403 curOffset += width; 1404 BasicBlock *nextBlock = findBlock(cUnit, curOffset, 1405 /* split */ 1406 false, 1407 /* create */ 1408 false); 1409 if (nextBlock) { 1410 /* 1411 * The next instruction could be the target of a previously parsed 1412 * forward branch so a block is already created. If the current 1413 * instruction is not an unconditional branch, connect them through 1414 * the fall-through link. 1415 */ 1416 assert(curBlock->fallThrough == NULL || 1417 curBlock->fallThrough == nextBlock || 1418 curBlock->fallThrough == cUnit->exitBlock); 1419 1420 if ((curBlock->fallThrough == NULL) && 1421 (flags & kInstrCanContinue)) { 1422 curBlock->needFallThroughBranch = true; 1423 curBlock->fallThrough = nextBlock; 1424 dvmCompilerSetBit(nextBlock->predecessors, curBlock->id); 1425 } 1426 /* Block has been visited - no more parsing needed */ 1427 if (nextBlock->visited == true) { 1428 return true; 1429 } 1430 curBlock = nextBlock; 1431 } 1432 } 1433 return true; 1434 } 1435 1436 /* Compile a loop */ 1437 static bool compileLoop(CompilationUnit *cUnit, unsigned int startOffset, 1438 JitTraceDescription *desc, int numMaxInsts, 1439 JitTranslationInfo *info, jmp_buf *bailPtr, 1440 int optHints) 1441 { 1442 int numBlocks = 0; 1443 unsigned int curOffset = startOffset; 1444 bool changed; 1445 BasicBlock *bb; 1446 #if defined(WITH_JIT_TUNING) 1447 CompilerMethodStats *methodStats; 1448 #endif 1449 1450 cUnit->jitMode = kJitLoop; 1451 1452 /* Initialize the block list */ 1453 dvmInitGrowableList(&cUnit->blockList, 4); 1454 1455 /* Initialize the PC reconstruction list */ 1456 dvmInitGrowableList(&cUnit->pcReconstructionList, 8); 1457 1458 /* Create the default entry and exit blocks and enter them to the list */ 1459 BasicBlock *entryBlock = dvmCompilerNewBB(kEntryBlock, numBlocks++); 1460 entryBlock->startOffset = curOffset; 1461 BasicBlock *exitBlock = dvmCompilerNewBB(kExitBlock, numBlocks++); 1462 1463 cUnit->entryBlock = entryBlock; 1464 cUnit->exitBlock = exitBlock; 1465 1466 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) entryBlock); 1467 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) exitBlock); 1468 1469 /* Current block to record parsed instructions */ 1470 BasicBlock *curBlock = dvmCompilerNewBB(kDalvikByteCode, numBlocks++); 1471 curBlock->startOffset = curOffset; 1472 1473 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) curBlock); 1474 entryBlock->fallThrough = curBlock; 1475 dvmCompilerSetBit(curBlock->predecessors, entryBlock->id); 1476 1477 /* 1478 * Store back the number of blocks since new blocks may be created of 1479 * accessing cUnit. 1480 */ 1481 cUnit->numBlocks = numBlocks; 1482 1483 do { 1484 dvmCompilerDataFlowAnalysisDispatcher(cUnit, 1485 dvmCompilerClearVisitedFlag, 1486 kAllNodes, 1487 false /* isIterative */); 1488 changed = exhaustTrace(cUnit, curBlock); 1489 } while (changed); 1490 1491 /* Backward chaining block */ 1492 bb = dvmCompilerNewBB(kChainingCellBackwardBranch, cUnit->numBlocks++); 1493 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bb); 1494 cUnit->backChainBlock = bb; 1495 1496 /* A special block to host PC reconstruction code */ 1497 bb = dvmCompilerNewBB(kPCReconstruction, cUnit->numBlocks++); 1498 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bb); 1499 1500 /* And one final block that publishes the PC and raises the exception */ 1501 bb = dvmCompilerNewBB(kExceptionHandling, cUnit->numBlocks++); 1502 dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bb); 1503 cUnit->puntBlock = bb; 1504 1505 cUnit->numDalvikRegisters = cUnit->method->registersSize; 1506 1507 /* Verify if all blocks are connected as claimed */ 1508 /* FIXME - to be disabled in the future */ 1509 dvmCompilerDataFlowAnalysisDispatcher(cUnit, verifyPredInfo, 1510 kAllNodes, 1511 false /* isIterative */); 1512 1513 1514 /* Try to identify a loop */ 1515 if (!dvmCompilerBuildLoop(cUnit)) 1516 goto bail; 1517 1518 dvmCompilerLoopOpt(cUnit); 1519 1520 /* 1521 * Change the backward branch to the backward chaining cell after dataflow 1522 * analsys/optimizations are done. 1523 */ 1524 dvmCompilerInsertBackwardChaining(cUnit); 1525 1526 dvmCompilerInitializeRegAlloc(cUnit); 1527 1528 /* Allocate Registers using simple local allocation scheme */ 1529 dvmCompilerLocalRegAlloc(cUnit); 1530 1531 /* Convert MIR to LIR, etc. */ 1532 dvmCompilerMIR2LIR(cUnit); 1533 1534 /* Loop contains never executed blocks / heavy instructions */ 1535 if (cUnit->quitLoopMode) { 1536 if (cUnit->printMe || gDvmJit.receivedSIGUSR2) { 1537 LOGD("Loop trace @ offset %04x aborted due to unresolved code info", 1538 cUnit->entryBlock->startOffset); 1539 } 1540 goto bail; 1541 } 1542 1543 /* Convert LIR into machine code. Loop for recoverable retries */ 1544 do { 1545 dvmCompilerAssembleLIR(cUnit, info); 1546 cUnit->assemblerRetries++; 1547 if (cUnit->printMe && cUnit->assemblerStatus != kSuccess) 1548 LOGD("Assembler abort #%d on %d", cUnit->assemblerRetries, 1549 cUnit->assemblerStatus); 1550 } while (cUnit->assemblerStatus == kRetryAll); 1551 1552 /* Loop is too big - bail out */ 1553 if (cUnit->assemblerStatus == kRetryHalve) { 1554 goto bail; 1555 } 1556 1557 if (cUnit->printMe || gDvmJit.receivedSIGUSR2) { 1558 LOGD("Loop trace @ offset %04x", cUnit->entryBlock->startOffset); 1559 dvmCompilerCodegenDump(cUnit); 1560 } 1561 1562 /* 1563 * If this trace uses class objects as constants, 1564 * dvmJitInstallClassObjectPointers will switch the thread state 1565 * to running and look up the class pointers using the descriptor/loader 1566 * tuple stored in the callsite info structure. We need to make this window 1567 * as short as possible since it is blocking GC. 1568 */ 1569 if (cUnit->hasClassLiterals && info->codeAddress) { 1570 dvmJitInstallClassObjectPointers(cUnit, (char *) info->codeAddress); 1571 } 1572 1573 /* 1574 * Since callsiteinfo is allocated from the arena, delay the reset until 1575 * class pointers are resolved. 1576 */ 1577 dvmCompilerArenaReset(); 1578 1579 assert(cUnit->assemblerStatus == kSuccess); 1580 #if defined(WITH_JIT_TUNING) 1581 /* Locate the entry to store compilation statistics for this method */ 1582 methodStats = dvmCompilerAnalyzeMethodBody(desc->method, false); 1583 methodStats->nativeSize += cUnit->totalSize; 1584 #endif 1585 return info->codeAddress != NULL; 1586 1587 bail: 1588 /* Retry the original trace with JIT_OPT_NO_LOOP disabled */ 1589 dvmCompilerArenaReset(); 1590 return dvmCompileTrace(desc, numMaxInsts, info, bailPtr, 1591 optHints | JIT_OPT_NO_LOOP); 1592 } 1593 1594 /* 1595 * Main entry point to start trace compilation. Basic blocks are constructed 1596 * first and they will be passed to the codegen routines to convert Dalvik 1597 * bytecode into machine code. 1598 */ 1599 bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, 1600 JitTranslationInfo *info, jmp_buf *bailPtr, 1601 int optHints) 1602 { 1603 const DexCode *dexCode = dvmGetMethodCode(desc->method); 1604 const JitTraceRun* currRun = &desc->trace[0]; 1605 unsigned int curOffset = currRun->info.frag.startOffset; 1606 unsigned int startOffset = curOffset; 1607 unsigned int numInsts = currRun->info.frag.numInsts; 1608 const u2 *codePtr = dexCode->insns + curOffset; 1609 int traceSize = 0; // # of half-words 1610 const u2 *startCodePtr = codePtr; 1611 BasicBlock *curBB, *entryCodeBB; 1612 int numBlocks = 0; 1613 static int compilationId; 1614 CompilationUnit cUnit; 1615 GrowableList *blockList; 1616 #if defined(WITH_JIT_TUNING) 1617 CompilerMethodStats *methodStats; 1618 #endif 1619 1620 /* If we've already compiled this trace, just return success */ 1621 if (dvmJitGetTraceAddr(startCodePtr) && !info->discardResult) { 1622 /* 1623 * Make sure the codeAddress is NULL so that it won't clobber the 1624 * existing entry. 1625 */ 1626 info->codeAddress = NULL; 1627 return true; 1628 } 1629 1630 /* If the work order is stale, discard it */ 1631 if (info->cacheVersion != gDvmJit.cacheVersion) { 1632 return false; 1633 } 1634 1635 compilationId++; 1636 memset(&cUnit, 0, sizeof(CompilationUnit)); 1637 1638 #if defined(WITH_JIT_TUNING) 1639 /* Locate the entry to store compilation statistics for this method */ 1640 methodStats = dvmCompilerAnalyzeMethodBody(desc->method, false); 1641 #endif 1642 1643 /* Set the recover buffer pointer */ 1644 cUnit.bailPtr = bailPtr; 1645 1646 /* Initialize the printMe flag */ 1647 cUnit.printMe = gDvmJit.printMe; 1648 1649 /* Setup the method */ 1650 cUnit.method = desc->method; 1651 1652 /* Store the trace descriptor and set the initial mode */ 1653 cUnit.traceDesc = desc; 1654 cUnit.jitMode = kJitTrace; 1655 1656 /* Initialize the PC reconstruction list */ 1657 dvmInitGrowableList(&cUnit.pcReconstructionList, 8); 1658 1659 /* Initialize the basic block list */ 1660 blockList = &cUnit.blockList; 1661 dvmInitGrowableList(blockList, 8); 1662 1663 /* Identify traces that we don't want to compile */ 1664 if (gDvmJit.methodTable) { 1665 int len = strlen(desc->method->clazz->descriptor) + 1666 strlen(desc->method->name) + 1; 1667 char *fullSignature = (char *)dvmCompilerNew(len, true); 1668 strcpy(fullSignature, desc->method->clazz->descriptor); 1669 strcat(fullSignature, desc->method->name); 1670 1671 int hashValue = dvmComputeUtf8Hash(fullSignature); 1672 1673 /* 1674 * Doing three levels of screening to see whether we want to skip 1675 * compiling this method 1676 */ 1677 1678 /* First, check the full "class;method" signature */ 1679 bool methodFound = 1680 dvmHashTableLookup(gDvmJit.methodTable, hashValue, 1681 fullSignature, (HashCompareFunc) strcmp, 1682 false) != 1683 NULL; 1684 1685 /* Full signature not found - check the enclosing class */ 1686 if (methodFound == false) { 1687 int hashValue = dvmComputeUtf8Hash(desc->method->clazz->descriptor); 1688 methodFound = 1689 dvmHashTableLookup(gDvmJit.methodTable, hashValue, 1690 (char *) desc->method->clazz->descriptor, 1691 (HashCompareFunc) strcmp, false) != 1692 NULL; 1693 /* Enclosing class not found - check the method name */ 1694 if (methodFound == false) { 1695 int hashValue = dvmComputeUtf8Hash(desc->method->name); 1696 methodFound = 1697 dvmHashTableLookup(gDvmJit.methodTable, hashValue, 1698 (char *) desc->method->name, 1699 (HashCompareFunc) strcmp, false) != 1700 NULL; 1701 1702 /* 1703 * Debug by call-graph is enabled. Check if the debug list 1704 * covers any methods on the VM stack. 1705 */ 1706 if (methodFound == false && gDvmJit.checkCallGraph == true) { 1707 methodFound = 1708 filterMethodByCallGraph(info->requestingThread, 1709 desc->method->name); 1710 } 1711 } 1712 } 1713 1714 /* 1715 * Under the following conditions, the trace will be *conservatively* 1716 * compiled by only containing single-step instructions to and from the 1717 * interpreter. 1718 * 1) If includeSelectedMethod == false, the method matches the full or 1719 * partial signature stored in the hash table. 1720 * 1721 * 2) If includeSelectedMethod == true, the method does not match the 1722 * full and partial signature stored in the hash table. 1723 */ 1724 if (gDvmJit.includeSelectedMethod != methodFound) { 1725 cUnit.allSingleStep = true; 1726 } else { 1727 /* Compile the trace as normal */ 1728 1729 /* Print the method we cherry picked */ 1730 if (gDvmJit.includeSelectedMethod == true) { 1731 cUnit.printMe = true; 1732 } 1733 } 1734 } 1735 1736 /* Allocate the entry block */ 1737 curBB = dvmCompilerNewBB(kEntryBlock, numBlocks++); 1738 dvmInsertGrowableList(blockList, (intptr_t) curBB); 1739 curBB->startOffset = curOffset; 1740 1741 entryCodeBB = dvmCompilerNewBB(kDalvikByteCode, numBlocks++); 1742 dvmInsertGrowableList(blockList, (intptr_t) entryCodeBB); 1743 entryCodeBB->startOffset = curOffset; 1744 curBB->fallThrough = entryCodeBB; 1745 curBB = entryCodeBB; 1746 1747 if (cUnit.printMe) { 1748 LOGD("--------\nCompiler: Building trace for %s, offset %#x", 1749 desc->method->name, curOffset); 1750 } 1751 1752 /* 1753 * Analyze the trace descriptor and include up to the maximal number 1754 * of Dalvik instructions into the IR. 1755 */ 1756 while (1) { 1757 MIR *insn; 1758 int width; 1759 insn = (MIR *)dvmCompilerNew(sizeof(MIR), true); 1760 insn->offset = curOffset; 1761 width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe); 1762 1763 /* The trace should never incude instruction data */ 1764 assert(width); 1765 insn->width = width; 1766 traceSize += width; 1767 dvmCompilerAppendMIR(curBB, insn); 1768 cUnit.numInsts++; 1769 1770 int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode); 1771 1772 if (flags & kInstrInvoke) { 1773 const Method *calleeMethod = (const Method *) 1774 currRun[JIT_TRACE_CUR_METHOD].info.meta; 1775 assert(numInsts == 1); 1776 CallsiteInfo *callsiteInfo = 1777 (CallsiteInfo *)dvmCompilerNew(sizeof(CallsiteInfo), true); 1778 callsiteInfo->classDescriptor = (const char *) 1779 currRun[JIT_TRACE_CLASS_DESC].info.meta; 1780 callsiteInfo->classLoader = (Object *) 1781 currRun[JIT_TRACE_CLASS_LOADER].info.meta; 1782 callsiteInfo->method = calleeMethod; 1783 insn->meta.callsiteInfo = callsiteInfo; 1784 } 1785 1786 /* Instruction limit reached - terminate the trace here */ 1787 if (cUnit.numInsts >= numMaxInsts) { 1788 break; 1789 } 1790 if (--numInsts == 0) { 1791 if (currRun->info.frag.runEnd) { 1792 break; 1793 } else { 1794 /* Advance to the next trace description (ie non-meta info) */ 1795 do { 1796 currRun++; 1797 } while (!currRun->isCode); 1798 1799 /* Dummy end-of-run marker seen */ 1800 if (currRun->info.frag.numInsts == 0) { 1801 break; 1802 } 1803 1804 curBB = dvmCompilerNewBB(kDalvikByteCode, numBlocks++); 1805 dvmInsertGrowableList(blockList, (intptr_t) curBB); 1806 curOffset = currRun->info.frag.startOffset; 1807 numInsts = currRun->info.frag.numInsts; 1808 curBB->startOffset = curOffset; 1809 codePtr = dexCode->insns + curOffset; 1810 } 1811 } else { 1812 curOffset += width; 1813 codePtr += width; 1814 } 1815 } 1816 1817 #if defined(WITH_JIT_TUNING) 1818 /* Convert # of half-word to bytes */ 1819 methodStats->compiledDalvikSize += traceSize * 2; 1820 #endif 1821 1822 /* 1823 * Now scan basic blocks containing real code to connect the 1824 * taken/fallthrough links. Also create chaining cells for code not included 1825 * in the trace. 1826 */ 1827 size_t blockId; 1828 for (blockId = 0; blockId < blockList->numUsed; blockId++) { 1829 curBB = (BasicBlock *) dvmGrowableListGetElement(blockList, blockId); 1830 MIR *lastInsn = curBB->lastMIRInsn; 1831 /* Skip empty blocks */ 1832 if (lastInsn == NULL) { 1833 continue; 1834 } 1835 curOffset = lastInsn->offset; 1836 unsigned int targetOffset = curOffset; 1837 unsigned int fallThroughOffset = curOffset + lastInsn->width; 1838 bool isInvoke = false; 1839 const Method *callee = NULL; 1840 1841 findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset, 1842 &targetOffset, &isInvoke, &callee); 1843 1844 /* Link the taken and fallthrough blocks */ 1845 BasicBlock *searchBB; 1846 1847 int flags = dexGetFlagsFromOpcode(lastInsn->dalvikInsn.opcode); 1848 1849 if (flags & kInstrInvoke) { 1850 cUnit.hasInvoke = true; 1851 } 1852 1853 /* Backward branch seen */ 1854 if (isInvoke == false && 1855 (flags & kInstrCanBranch) != 0 && 1856 targetOffset < curOffset && 1857 (optHints & JIT_OPT_NO_LOOP) == 0) { 1858 dvmCompilerArenaReset(); 1859 return compileLoop(&cUnit, startOffset, desc, numMaxInsts, 1860 info, bailPtr, optHints); 1861 } 1862 1863 /* No backward branch in the trace - start searching the next BB */ 1864 size_t searchBlockId; 1865 for (searchBlockId = blockId+1; searchBlockId < blockList->numUsed; 1866 searchBlockId++) { 1867 searchBB = (BasicBlock *) dvmGrowableListGetElement(blockList, 1868 searchBlockId); 1869 if (targetOffset == searchBB->startOffset) { 1870 curBB->taken = searchBB; 1871 dvmCompilerSetBit(searchBB->predecessors, curBB->id); 1872 } 1873 if (fallThroughOffset == searchBB->startOffset) { 1874 curBB->fallThrough = searchBB; 1875 dvmCompilerSetBit(searchBB->predecessors, curBB->id); 1876 1877 /* 1878 * Fallthrough block of an invoke instruction needs to be 1879 * aligned to 4-byte boundary (alignment instruction to be 1880 * inserted later. 1881 */ 1882 if (flags & kInstrInvoke) { 1883 searchBB->isFallThroughFromInvoke = true; 1884 } 1885 } 1886 } 1887 1888 /* 1889 * Some blocks are ended by non-control-flow-change instructions, 1890 * currently only due to trace length constraint. In this case we need 1891 * to generate an explicit branch at the end of the block to jump to 1892 * the chaining cell. 1893 */ 1894 curBB->needFallThroughBranch = 1895 ((flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn | 1896 kInstrInvoke)) == 0); 1897 if (lastInsn->dalvikInsn.opcode == OP_PACKED_SWITCH || 1898 lastInsn->dalvikInsn.opcode == OP_SPARSE_SWITCH) { 1899 int i; 1900 const u2 *switchData = desc->method->insns + lastInsn->offset + 1901 lastInsn->dalvikInsn.vB; 1902 int size = switchData[1]; 1903 int maxChains = MIN(size, MAX_CHAINED_SWITCH_CASES); 1904 1905 /* 1906 * Generate the landing pad for cases whose ranks are higher than 1907 * MAX_CHAINED_SWITCH_CASES. The code will re-enter the interpreter 1908 * through the NoChain point. 1909 */ 1910 if (maxChains != size) { 1911 cUnit.switchOverflowPad = 1912 desc->method->insns + lastInsn->offset; 1913 } 1914 1915 s4 *targets = (s4 *) (switchData + 2 + 1916 (lastInsn->dalvikInsn.opcode == OP_PACKED_SWITCH ? 1917 2 : size * 2)); 1918 1919 /* One chaining cell for the first MAX_CHAINED_SWITCH_CASES cases */ 1920 for (i = 0; i < maxChains; i++) { 1921 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal, 1922 numBlocks++); 1923 dvmInsertGrowableList(blockList, (intptr_t) caseChain); 1924 caseChain->startOffset = lastInsn->offset + targets[i]; 1925 } 1926 1927 /* One more chaining cell for the default case */ 1928 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal, 1929 numBlocks++); 1930 dvmInsertGrowableList(blockList, (intptr_t) caseChain); 1931 caseChain->startOffset = lastInsn->offset + lastInsn->width; 1932 /* Fallthrough block not included in the trace */ 1933 } else if (!isUnconditionalBranch(lastInsn) && 1934 curBB->fallThrough == NULL) { 1935 BasicBlock *fallThroughBB; 1936 /* 1937 * If the chaining cell is after an invoke or 1938 * instruction that cannot change the control flow, request a hot 1939 * chaining cell. 1940 */ 1941 if (isInvoke || curBB->needFallThroughBranch) { 1942 fallThroughBB = dvmCompilerNewBB(kChainingCellHot, numBlocks++); 1943 } else { 1944 fallThroughBB = dvmCompilerNewBB(kChainingCellNormal, 1945 numBlocks++); 1946 } 1947 dvmInsertGrowableList(blockList, (intptr_t) fallThroughBB); 1948 fallThroughBB->startOffset = fallThroughOffset; 1949 curBB->fallThrough = fallThroughBB; 1950 dvmCompilerSetBit(fallThroughBB->predecessors, curBB->id); 1951 } 1952 /* Target block not included in the trace */ 1953 if (curBB->taken == NULL && 1954 (isGoto(lastInsn) || isInvoke || 1955 (targetOffset != UNKNOWN_TARGET && targetOffset != curOffset))) { 1956 BasicBlock *newBB = NULL; 1957 if (isInvoke) { 1958 /* Monomorphic callee */ 1959 if (callee) { 1960 /* JNI call doesn't need a chaining cell */ 1961 if (!dvmIsNativeMethod(callee)) { 1962 newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton, 1963 numBlocks++); 1964 newBB->startOffset = 0; 1965 newBB->containingMethod = callee; 1966 } 1967 /* Will resolve at runtime */ 1968 } else { 1969 newBB = dvmCompilerNewBB(kChainingCellInvokePredicted, 1970 numBlocks++); 1971 newBB->startOffset = 0; 1972 } 1973 /* For unconditional branches, request a hot chaining cell */ 1974 } else { 1975 #if !defined(WITH_SELF_VERIFICATION) 1976 newBB = dvmCompilerNewBB(dexIsGoto(flags) ? 1977 kChainingCellHot : 1978 kChainingCellNormal, 1979 numBlocks++); 1980 newBB->startOffset = targetOffset; 1981 #else 1982 /* Handle branches that branch back into the block */ 1983 if (targetOffset >= curBB->firstMIRInsn->offset && 1984 targetOffset <= curBB->lastMIRInsn->offset) { 1985 newBB = dvmCompilerNewBB(kChainingCellBackwardBranch, 1986 numBlocks++); 1987 } else { 1988 newBB = dvmCompilerNewBB(dexIsGoto(flags) ? 1989 kChainingCellHot : 1990 kChainingCellNormal, 1991 numBlocks++); 1992 } 1993 newBB->startOffset = targetOffset; 1994 #endif 1995 } 1996 if (newBB) { 1997 curBB->taken = newBB; 1998 dvmCompilerSetBit(newBB->predecessors, curBB->id); 1999 dvmInsertGrowableList(blockList, (intptr_t) newBB); 2000 } 2001 } 2002 } 2003 2004 /* Now create a special block to host PC reconstruction code */ 2005 curBB = dvmCompilerNewBB(kPCReconstruction, numBlocks++); 2006 dvmInsertGrowableList(blockList, (intptr_t) curBB); 2007 2008 /* And one final block that publishes the PC and raise the exception */ 2009 curBB = dvmCompilerNewBB(kExceptionHandling, numBlocks++); 2010 dvmInsertGrowableList(blockList, (intptr_t) curBB); 2011 cUnit.puntBlock = curBB; 2012 2013 if (cUnit.printMe) { 2014 char* signature = 2015 dexProtoCopyMethodDescriptor(&desc->method->prototype); 2016 LOGD("TRACEINFO (%d): 0x%08x %s%s.%s %#x %d of %d, %d blocks", 2017 compilationId, 2018 (intptr_t) desc->method->insns, 2019 desc->method->clazz->descriptor, 2020 desc->method->name, 2021 signature, 2022 desc->trace[0].info.frag.startOffset, 2023 traceSize, 2024 dexCode->insnsSize, 2025 numBlocks); 2026 free(signature); 2027 } 2028 2029 cUnit.numBlocks = numBlocks; 2030 2031 /* Set the instruction set to use (NOTE: later components may change it) */ 2032 cUnit.instructionSet = dvmCompilerInstructionSet(); 2033 2034 /* Inline transformation @ the MIR level */ 2035 if (cUnit.hasInvoke && !(gDvmJit.disableOpt & (1 << kMethodInlining))) { 2036 dvmCompilerInlineMIR(&cUnit, info); 2037 } 2038 2039 cUnit.numDalvikRegisters = cUnit.method->registersSize; 2040 2041 /* Preparation for SSA conversion */ 2042 dvmInitializeSSAConversion(&cUnit); 2043 2044 dvmCompilerNonLoopAnalysis(&cUnit); 2045 2046 dvmCompilerInitializeRegAlloc(&cUnit); // Needs to happen after SSA naming 2047 2048 if (cUnit.printMe) { 2049 dvmCompilerDumpCompilationUnit(&cUnit); 2050 } 2051 2052 /* Allocate Registers using simple local allocation scheme */ 2053 dvmCompilerLocalRegAlloc(&cUnit); 2054 2055 /* Convert MIR to LIR, etc. */ 2056 dvmCompilerMIR2LIR(&cUnit); 2057 2058 /* Convert LIR into machine code. Loop for recoverable retries */ 2059 do { 2060 dvmCompilerAssembleLIR(&cUnit, info); 2061 cUnit.assemblerRetries++; 2062 if (cUnit.printMe && cUnit.assemblerStatus != kSuccess) 2063 LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries, 2064 cUnit.assemblerStatus); 2065 } while (cUnit.assemblerStatus == kRetryAll); 2066 2067 if (cUnit.printMe) { 2068 LOGD("Trace Dalvik PC: %p", startCodePtr); 2069 dvmCompilerCodegenDump(&cUnit); 2070 LOGD("End %s%s, %d Dalvik instructions", 2071 desc->method->clazz->descriptor, desc->method->name, 2072 cUnit.numInsts); 2073 } 2074 2075 if (cUnit.assemblerStatus == kRetryHalve) { 2076 /* Reset the compiler resource pool before retry */ 2077 dvmCompilerArenaReset(); 2078 2079 /* Halve the instruction count and start from the top */ 2080 return dvmCompileTrace(desc, cUnit.numInsts / 2, info, bailPtr, 2081 optHints); 2082 } 2083 2084 /* 2085 * If this trace uses class objects as constants, 2086 * dvmJitInstallClassObjectPointers will switch the thread state 2087 * to running and look up the class pointers using the descriptor/loader 2088 * tuple stored in the callsite info structure. We need to make this window 2089 * as short as possible since it is blocking GC. 2090 */ 2091 if (cUnit.hasClassLiterals && info->codeAddress) { 2092 dvmJitInstallClassObjectPointers(&cUnit, (char *) info->codeAddress); 2093 } 2094 2095 /* 2096 * Since callsiteinfo is allocated from the arena, delay the reset until 2097 * class pointers are resolved. 2098 */ 2099 dvmCompilerArenaReset(); 2100 2101 assert(cUnit.assemblerStatus == kSuccess); 2102 #if defined(WITH_JIT_TUNING) 2103 methodStats->nativeSize += cUnit.totalSize; 2104 #endif 2105 2106 return info->codeAddress != NULL; 2107 } 2108
