1 /*
2 * Copyright (C) 2009 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "Dalvik.h"
18 #include "libdex/OpCode.h"
19 #include "interp/Jit.h"
20 #include "CompilerInternals.h"
21 #include "Dataflow.h"
22
23 /*
24 * Parse an instruction, return the length of the instruction
25 */
parseInsn(const u2 * codePtr,DecodedInstruction * decInsn,bool printMe)26 static inline int parseInsn(const u2 *codePtr, DecodedInstruction *decInsn,
27 bool printMe)
28 {
29 u2 instr = *codePtr;
30 OpCode opcode = instr & 0xff;
31 int insnWidth;
32
33 // Don't parse instruction data
34 if (opcode == OP_NOP && instr != 0) {
35 return 0;
36 } else {
37 insnWidth = gDvm.instrWidth[opcode];
38 if (insnWidth < 0) {
39 insnWidth = -insnWidth;
40 }
41 }
42
43 dexDecodeInstruction(gDvm.instrFormat, codePtr, decInsn);
44 if (printMe) {
45 char *decodedString = dvmCompilerGetDalvikDisassembly(decInsn, NULL);
46 LOGD("%p: %#06x %s\n", codePtr, opcode, decodedString);
47 }
48 return insnWidth;
49 }
50
51 #define UNKNOWN_TARGET 0xffffffff
52
53 /*
54 * Identify block-ending instructions and collect supplemental information
55 * regarding the following instructions.
56 */
findBlockBoundary(const Method * caller,MIR * insn,unsigned int curOffset,unsigned int * target,bool * isInvoke,const Method ** callee)57 static inline bool findBlockBoundary(const Method *caller, MIR *insn,
58 unsigned int curOffset,
59 unsigned int *target, bool *isInvoke,
60 const Method **callee)
61 {
62 switch (insn->dalvikInsn.opCode) {
63 /* Target is not compile-time constant */
64 case OP_RETURN_VOID:
65 case OP_RETURN:
66 case OP_RETURN_WIDE:
67 case OP_RETURN_OBJECT:
68 case OP_THROW:
69 *target = UNKNOWN_TARGET;
70 break;
71 case OP_INVOKE_VIRTUAL:
72 case OP_INVOKE_VIRTUAL_RANGE:
73 case OP_INVOKE_INTERFACE:
74 case OP_INVOKE_INTERFACE_RANGE:
75 case OP_INVOKE_VIRTUAL_QUICK:
76 case OP_INVOKE_VIRTUAL_QUICK_RANGE:
77 *isInvoke = true;
78 break;
79 case OP_INVOKE_SUPER:
80 case OP_INVOKE_SUPER_RANGE: {
81 int mIndex = caller->clazz->pDvmDex->
82 pResMethods[insn->dalvikInsn.vB]->methodIndex;
83 const Method *calleeMethod =
84 caller->clazz->super->vtable[mIndex];
85
86 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
87 *target = (unsigned int) calleeMethod->insns;
88 }
89 *isInvoke = true;
90 *callee = calleeMethod;
91 break;
92 }
93 case OP_INVOKE_STATIC:
94 case OP_INVOKE_STATIC_RANGE: {
95 const Method *calleeMethod =
96 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
97
98 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
99 *target = (unsigned int) calleeMethod->insns;
100 }
101 *isInvoke = true;
102 *callee = calleeMethod;
103 break;
104 }
105 case OP_INVOKE_SUPER_QUICK:
106 case OP_INVOKE_SUPER_QUICK_RANGE: {
107 const Method *calleeMethod =
108 caller->clazz->super->vtable[insn->dalvikInsn.vB];
109
110 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
111 *target = (unsigned int) calleeMethod->insns;
112 }
113 *isInvoke = true;
114 *callee = calleeMethod;
115 break;
116 }
117 case OP_INVOKE_DIRECT:
118 case OP_INVOKE_DIRECT_RANGE: {
119 const Method *calleeMethod =
120 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
121 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
122 *target = (unsigned int) calleeMethod->insns;
123 }
124 *isInvoke = true;
125 *callee = calleeMethod;
126 break;
127 }
128 case OP_GOTO:
129 case OP_GOTO_16:
130 case OP_GOTO_32:
131 *target = curOffset + (int) insn->dalvikInsn.vA;
132 break;
133
134 case OP_IF_EQ:
135 case OP_IF_NE:
136 case OP_IF_LT:
137 case OP_IF_GE:
138 case OP_IF_GT:
139 case OP_IF_LE:
140 *target = curOffset + (int) insn->dalvikInsn.vC;
141 break;
142
143 case OP_IF_EQZ:
144 case OP_IF_NEZ:
145 case OP_IF_LTZ:
146 case OP_IF_GEZ:
147 case OP_IF_GTZ:
148 case OP_IF_LEZ:
149 *target = curOffset + (int) insn->dalvikInsn.vB;
150 break;
151
152 default:
153 return false;
154 }
155 return true;
156 }
157
isGoto(MIR * insn)158 static inline bool isGoto(MIR *insn)
159 {
160 switch (insn->dalvikInsn.opCode) {
161 case OP_GOTO:
162 case OP_GOTO_16:
163 case OP_GOTO_32:
164 return true;
165 default:
166 return false;
167 }
168 }
169
170 /*
171 * Identify unconditional branch instructions
172 */
isUnconditionalBranch(MIR * insn)173 static inline bool isUnconditionalBranch(MIR *insn)
174 {
175 switch (insn->dalvikInsn.opCode) {
176 case OP_RETURN_VOID:
177 case OP_RETURN:
178 case OP_RETURN_WIDE:
179 case OP_RETURN_OBJECT:
180 return true;
181 default:
182 return isGoto(insn);
183 }
184 }
185
186 /*
187 * dvmHashTableLookup() callback
188 */
compareMethod(const CompilerMethodStats * m1,const CompilerMethodStats * m2)189 static int compareMethod(const CompilerMethodStats *m1,
190 const CompilerMethodStats *m2)
191 {
192 return (int) m1->method - (int) m2->method;
193 }
194
195 /*
196 * Analyze the body of the method to collect high-level information regarding
197 * inlining:
198 * - is empty method?
199 * - is getter/setter?
200 * - can throw exception?
201 *
202 * Currently the inliner only handles getters and setters. When its capability
203 * becomes more sophisticated more information will be retrieved here.
204 */
analyzeInlineTarget(DecodedInstruction * dalvikInsn,int attributes,int offset)205 static int analyzeInlineTarget(DecodedInstruction *dalvikInsn, int attributes,
206 int offset)
207 {
208 int flags = dexGetInstrFlags(gDvm.instrFlags, dalvikInsn->opCode);
209 int dalvikOpCode = dalvikInsn->opCode;
210
211 if ((flags & kInstrInvoke) &&
212 (dalvikOpCode != OP_INVOKE_DIRECT_EMPTY)) {
213 attributes &= ~METHOD_IS_LEAF;
214 }
215
216 if (!(flags & kInstrCanReturn)) {
217 if (!(dvmCompilerDataFlowAttributes[dalvikOpCode] &
218 DF_IS_GETTER)) {
219 attributes &= ~METHOD_IS_GETTER;
220 }
221 if (!(dvmCompilerDataFlowAttributes[dalvikOpCode] &
222 DF_IS_SETTER)) {
223 attributes &= ~METHOD_IS_SETTER;
224 }
225 }
226
227 /*
228 * The expected instruction sequence is setter will never return value and
229 * getter will also do. Clear the bits if the behavior is discovered
230 * otherwise.
231 */
232 if (flags & kInstrCanReturn) {
233 if (dalvikOpCode == OP_RETURN_VOID) {
234 attributes &= ~METHOD_IS_GETTER;
235 }
236 else {
237 attributes &= ~METHOD_IS_SETTER;
238 }
239 }
240
241 if (flags & kInstrCanThrow) {
242 attributes &= ~METHOD_IS_THROW_FREE;
243 }
244
245 if (offset == 0 && dalvikOpCode == OP_RETURN_VOID) {
246 attributes |= METHOD_IS_EMPTY;
247 }
248
249 /*
250 * Check if this opcode is selected for single stepping.
251 * If so, don't inline the callee as there is no stack frame for the
252 * interpreter to single-step through the instruction.
253 */
254 if (SINGLE_STEP_OP(dalvikOpCode)) {
255 attributes &= ~(METHOD_IS_GETTER | METHOD_IS_SETTER);
256 }
257
258 return attributes;
259 }
260
261 /*
262 * Analyze each method whose traces are ever compiled. Collect a variety of
263 * statistics like the ratio of exercised vs overall code and code bloat
264 * ratios. If isCallee is true, also analyze each instruction in more details
265 * to see if it is suitable for inlining.
266 */
dvmCompilerAnalyzeMethodBody(const Method * method,bool isCallee)267 CompilerMethodStats *dvmCompilerAnalyzeMethodBody(const Method *method,
268 bool isCallee)
269 {
270 const DexCode *dexCode = dvmGetMethodCode(method);
271 const u2 *codePtr = dexCode->insns;
272 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
273 int insnSize = 0;
274 int hashValue = dvmComputeUtf8Hash(method->name);
275
276 CompilerMethodStats dummyMethodEntry; // For hash table lookup
277 CompilerMethodStats *realMethodEntry; // For hash table storage
278
279 /* For lookup only */
280 dummyMethodEntry.method = method;
281 realMethodEntry = dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
282 &dummyMethodEntry,
283 (HashCompareFunc) compareMethod,
284 false);
285
286 /* This method has never been analyzed before - create an entry */
287 if (realMethodEntry == NULL) {
288 realMethodEntry =
289 (CompilerMethodStats *) calloc(1, sizeof(CompilerMethodStats));
290 realMethodEntry->method = method;
291
292 dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
293 realMethodEntry,
294 (HashCompareFunc) compareMethod,
295 true);
296 }
297
298 /* This method is invoked as a callee and has been analyzed - just return */
299 if ((isCallee == true) && (realMethodEntry->attributes & METHOD_IS_CALLEE))
300 return realMethodEntry;
301
302 /*
303 * Similarly, return if this method has been compiled before as a hot
304 * method already.
305 */
306 if ((isCallee == false) &&
307 (realMethodEntry->attributes & METHOD_IS_HOT))
308 return realMethodEntry;
309
310 int attributes;
311
312 /* Method hasn't been analyzed for the desired purpose yet */
313 if (isCallee) {
314 /* Aggressively set the attributes until proven otherwise */
315 attributes = METHOD_IS_LEAF | METHOD_IS_THROW_FREE | METHOD_IS_CALLEE |
316 METHOD_IS_GETTER | METHOD_IS_SETTER;
317 } else {
318 attributes = METHOD_IS_HOT;
319 }
320
321 /* Count the number of instructions */
322 while (codePtr < codeEnd) {
323 DecodedInstruction dalvikInsn;
324 int width = parseInsn(codePtr, &dalvikInsn, false);
325
326 /* Terminate when the data section is seen */
327 if (width == 0)
328 break;
329
330 if (isCallee) {
331 attributes = analyzeInlineTarget(&dalvikInsn, attributes, insnSize);
332 }
333
334 insnSize += width;
335 codePtr += width;
336 }
337
338 /*
339 * Only handle simple getters/setters with one instruction followed by
340 * return
341 */
342 if ((attributes & (METHOD_IS_GETTER | METHOD_IS_SETTER)) &&
343 (insnSize != 3)) {
344 attributes &= ~(METHOD_IS_GETTER | METHOD_IS_SETTER);
345 }
346
347 realMethodEntry->dalvikSize = insnSize * 2;
348 realMethodEntry->attributes |= attributes;
349
350 #if 0
351 /* Uncomment the following to explore various callee patterns */
352 if (attributes & METHOD_IS_THROW_FREE) {
353 LOGE("%s%s is inlinable%s", method->clazz->descriptor, method->name,
354 (attributes & METHOD_IS_EMPTY) ? " empty" : "");
355 }
356
357 if (attributes & METHOD_IS_LEAF) {
358 LOGE("%s%s is leaf %d%s", method->clazz->descriptor, method->name,
359 insnSize, insnSize < 5 ? " (small)" : "");
360 }
361
362 if (attributes & (METHOD_IS_GETTER | METHOD_IS_SETTER)) {
363 LOGE("%s%s is %s", method->clazz->descriptor, method->name,
364 attributes & METHOD_IS_GETTER ? "getter": "setter");
365 }
366 if (attributes ==
367 (METHOD_IS_LEAF | METHOD_IS_THROW_FREE | METHOD_IS_CALLEE)) {
368 LOGE("%s%s is inlinable non setter/getter", method->clazz->descriptor,
369 method->name);
370 }
371 #endif
372
373 return realMethodEntry;
374 }
375
376 /*
377 * Crawl the stack of the thread that requesed compilation to see if any of the
378 * ancestors are on the blacklist.
379 */
filterMethodByCallGraph(Thread * thread,const char * curMethodName)380 bool filterMethodByCallGraph(Thread *thread, const char *curMethodName)
381 {
382 /* Crawl the Dalvik stack frames and compare the method name*/
383 StackSaveArea *ssaPtr = ((StackSaveArea *) thread->curFrame) - 1;
384 while (ssaPtr != ((StackSaveArea *) NULL) - 1) {
385 const Method *method = ssaPtr->method;
386 if (method) {
387 int hashValue = dvmComputeUtf8Hash(method->name);
388 bool found =
389 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
390 (char *) method->name,
391 (HashCompareFunc) strcmp, false) !=
392 NULL;
393 if (found) {
394 LOGD("Method %s (--> %s) found on the JIT %s list",
395 method->name, curMethodName,
396 gDvmJit.includeSelectedMethod ? "white" : "black");
397 return true;
398 }
399
400 }
401 ssaPtr = ((StackSaveArea *) ssaPtr->prevFrame) - 1;
402 };
403 return false;
404 }
405
406 /*
407 * Main entry point to start trace compilation. Basic blocks are constructed
408 * first and they will be passed to the codegen routines to convert Dalvik
409 * bytecode into machine code.
410 */
dvmCompileTrace(JitTraceDescription * desc,int numMaxInsts,JitTranslationInfo * info,jmp_buf * bailPtr,int optHints)411 bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts,
412 JitTranslationInfo *info, jmp_buf *bailPtr,
413 int optHints)
414 {
415 const DexCode *dexCode = dvmGetMethodCode(desc->method);
416 const JitTraceRun* currRun = &desc->trace[0];
417 unsigned int curOffset = currRun->frag.startOffset;
418 unsigned int numInsts = currRun->frag.numInsts;
419 const u2 *codePtr = dexCode->insns + curOffset;
420 int traceSize = 0; // # of half-words
421 const u2 *startCodePtr = codePtr;
422 BasicBlock *startBB, *curBB, *lastBB;
423 int numBlocks = 0;
424 static int compilationId;
425 CompilationUnit cUnit;
426 #if defined(WITH_JIT_TUNING)
427 CompilerMethodStats *methodStats;
428 #endif
429
430 /* If we've already compiled this trace, just return success */
431 if (dvmJitGetCodeAddr(startCodePtr) && !info->discardResult) {
432 /*
433 * Make sure the codeAddress is NULL so that it won't clobber the
434 * existing entry.
435 */
436 info->codeAddress = NULL;
437 return true;
438 }
439
440 compilationId++;
441 memset(&cUnit, 0, sizeof(CompilationUnit));
442
443 #if defined(WITH_JIT_TUNING)
444 /* Locate the entry to store compilation statistics for this method */
445 methodStats = dvmCompilerAnalyzeMethodBody(desc->method, false);
446 #endif
447
448 /* Set the recover buffer pointer */
449 cUnit.bailPtr = bailPtr;
450
451 /* Initialize the printMe flag */
452 cUnit.printMe = gDvmJit.printMe;
453
454 /* Initialize the profile flag */
455 cUnit.executionCount = gDvmJit.profile;
456
457 /* Setup the method */
458 cUnit.method = desc->method;
459
460 /* Initialize the PC reconstruction list */
461 dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
462
463 /* Identify traces that we don't want to compile */
464 if (gDvmJit.methodTable) {
465 int len = strlen(desc->method->clazz->descriptor) +
466 strlen(desc->method->name) + 1;
467 char *fullSignature = dvmCompilerNew(len, true);
468 strcpy(fullSignature, desc->method->clazz->descriptor);
469 strcat(fullSignature, desc->method->name);
470
471 int hashValue = dvmComputeUtf8Hash(fullSignature);
472
473 /*
474 * Doing three levels of screening to see whether we want to skip
475 * compiling this method
476 */
477
478 /* First, check the full "class;method" signature */
479 bool methodFound =
480 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
481 fullSignature, (HashCompareFunc) strcmp,
482 false) !=
483 NULL;
484
485 /* Full signature not found - check the enclosing class */
486 if (methodFound == false) {
487 int hashValue = dvmComputeUtf8Hash(desc->method->clazz->descriptor);
488 methodFound =
489 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
490 (char *) desc->method->clazz->descriptor,
491 (HashCompareFunc) strcmp, false) !=
492 NULL;
493 /* Enclosing class not found - check the method name */
494 if (methodFound == false) {
495 int hashValue = dvmComputeUtf8Hash(desc->method->name);
496 methodFound =
497 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
498 (char *) desc->method->name,
499 (HashCompareFunc) strcmp, false) !=
500 NULL;
501
502 /*
503 * Debug by call-graph is enabled. Check if the debug list
504 * covers any methods on the VM stack.
505 */
506 if (methodFound == false && gDvmJit.checkCallGraph == true) {
507 methodFound =
508 filterMethodByCallGraph(info->requestingThread,
509 desc->method->name);
510 }
511 }
512 }
513
514 /*
515 * Under the following conditions, the trace will be *conservatively*
516 * compiled by only containing single-step instructions to and from the
517 * interpreter.
518 * 1) If includeSelectedMethod == false, the method matches the full or
519 * partial signature stored in the hash table.
520 *
521 * 2) If includeSelectedMethod == true, the method does not match the
522 * full and partial signature stored in the hash table.
523 */
524 if (gDvmJit.includeSelectedMethod != methodFound) {
525 cUnit.allSingleStep = true;
526 } else {
527 /* Compile the trace as normal */
528
529 /* Print the method we cherry picked */
530 if (gDvmJit.includeSelectedMethod == true) {
531 cUnit.printMe = true;
532 }
533 }
534 }
535
536 /* Allocate the entry block */
537 lastBB = startBB = curBB = dvmCompilerNewBB(kTraceEntryBlock);
538 curBB->startOffset = curOffset;
539 curBB->id = numBlocks++;
540
541 curBB = dvmCompilerNewBB(kDalvikByteCode);
542 curBB->startOffset = curOffset;
543 curBB->id = numBlocks++;
544
545 /* Make the first real dalvik block the fallthrough of the entry block */
546 startBB->fallThrough = curBB;
547 lastBB->next = curBB;
548 lastBB = curBB;
549
550 if (cUnit.printMe) {
551 LOGD("--------\nCompiler: Building trace for %s, offset 0x%x\n",
552 desc->method->name, curOffset);
553 }
554
555 /*
556 * Analyze the trace descriptor and include up to the maximal number
557 * of Dalvik instructions into the IR.
558 */
559 while (1) {
560 MIR *insn;
561 int width;
562 insn = dvmCompilerNew(sizeof(MIR), true);
563 insn->offset = curOffset;
564 width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe);
565
566 /* The trace should never incude instruction data */
567 assert(width);
568 insn->width = width;
569 traceSize += width;
570 dvmCompilerAppendMIR(curBB, insn);
571 cUnit.numInsts++;
572
573 int flags = dexGetInstrFlags(gDvm.instrFlags, insn->dalvikInsn.opCode);
574
575 if ((flags & kInstrInvoke) &&
576 (insn->dalvikInsn.opCode != OP_INVOKE_DIRECT_EMPTY)) {
577 assert(numInsts == 1);
578 CallsiteInfo *callsiteInfo =
579 dvmCompilerNew(sizeof(CallsiteInfo), true);
580 callsiteInfo->clazz = currRun[1].meta;
581 callsiteInfo->method = currRun[2].meta;
582 insn->meta.callsiteInfo = callsiteInfo;
583 }
584
585 /* Instruction limit reached - terminate the trace here */
586 if (cUnit.numInsts >= numMaxInsts) {
587 break;
588 }
589 if (--numInsts == 0) {
590 if (currRun->frag.runEnd) {
591 break;
592 } else {
593 /* Advance to the next trace description (ie non-meta info) */
594 do {
595 currRun++;
596 } while (!currRun->frag.isCode);
597
598 /* Dummy end-of-run marker seen */
599 if (currRun->frag.numInsts == 0) {
600 break;
601 }
602
603 curBB = dvmCompilerNewBB(kDalvikByteCode);
604 lastBB->next = curBB;
605 lastBB = curBB;
606 curBB->id = numBlocks++;
607 curOffset = currRun->frag.startOffset;
608 numInsts = currRun->frag.numInsts;
609 curBB->startOffset = curOffset;
610 codePtr = dexCode->insns + curOffset;
611 }
612 } else {
613 curOffset += width;
614 codePtr += width;
615 }
616 }
617
618 #if defined(WITH_JIT_TUNING)
619 /* Convert # of half-word to bytes */
620 methodStats->compiledDalvikSize += traceSize * 2;
621 #endif
622
623 /*
624 * Now scan basic blocks containing real code to connect the
625 * taken/fallthrough links. Also create chaining cells for code not included
626 * in the trace.
627 */
628 for (curBB = startBB; curBB; curBB = curBB->next) {
629 MIR *lastInsn = curBB->lastMIRInsn;
630 /* Skip empty blocks */
631 if (lastInsn == NULL) {
632 continue;
633 }
634 curOffset = lastInsn->offset;
635 unsigned int targetOffset = curOffset;
636 unsigned int fallThroughOffset = curOffset + lastInsn->width;
637 bool isInvoke = false;
638 const Method *callee = NULL;
639
640 findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset,
641 &targetOffset, &isInvoke, &callee);
642
643 /* Link the taken and fallthrough blocks */
644 BasicBlock *searchBB;
645
646 int flags = dexGetInstrFlags(gDvm.instrFlags,
647 lastInsn->dalvikInsn.opCode);
648
649 if (flags & kInstrInvoke) {
650 cUnit.hasInvoke = true;
651 }
652
653 /* No backward branch in the trace - start searching the next BB */
654 for (searchBB = curBB->next; searchBB; searchBB = searchBB->next) {
655 if (targetOffset == searchBB->startOffset) {
656 curBB->taken = searchBB;
657 }
658 if (fallThroughOffset == searchBB->startOffset) {
659 curBB->fallThrough = searchBB;
660
661 /*
662 * Fallthrough block of an invoke instruction needs to be
663 * aligned to 4-byte boundary (alignment instruction to be
664 * inserted later.
665 */
666 if (flags & kInstrInvoke) {
667 searchBB->isFallThroughFromInvoke = true;
668 }
669 }
670 }
671
672 /*
673 * Some blocks are ended by non-control-flow-change instructions,
674 * currently only due to trace length constraint. In this case we need
675 * to generate an explicit branch at the end of the block to jump to
676 * the chaining cell.
677 *
678 * NOTE: INVOKE_DIRECT_EMPTY is actually not an invoke but a nop
679 */
680 curBB->needFallThroughBranch =
681 ((flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
682 kInstrInvoke)) == 0) ||
683 (lastInsn->dalvikInsn.opCode == OP_INVOKE_DIRECT_EMPTY);
684
685 /* Only form a loop if JIT_OPT_NO_LOOP is not set */
686 if (curBB->taken == NULL &&
687 curBB->fallThrough == NULL &&
688 flags == (kInstrCanBranch | kInstrCanContinue) &&
689 fallThroughOffset == startBB->startOffset &&
690 JIT_OPT_NO_LOOP != (optHints & JIT_OPT_NO_LOOP)) {
691 BasicBlock *loopBranch = curBB;
692 BasicBlock *exitBB;
693 BasicBlock *exitChainingCell;
694
695 if (cUnit.printMe) {
696 LOGD("Natural loop detected!");
697 }
698 exitBB = dvmCompilerNewBB(kTraceExitBlock);
699 lastBB->next = exitBB;
700 lastBB = exitBB;
701
702 exitBB->startOffset = targetOffset;
703 exitBB->id = numBlocks++;
704 exitBB->needFallThroughBranch = true;
705
706 loopBranch->taken = exitBB;
707 #if defined(WITH_SELF_VERIFICATION)
708 BasicBlock *backwardCell =
709 dvmCompilerNewBB(kChainingCellBackwardBranch);
710 lastBB->next = backwardCell;
711 lastBB = backwardCell;
712
713 backwardCell->startOffset = startBB->startOffset;
714 backwardCell->id = numBlocks++;
715 loopBranch->fallThrough = backwardCell;
716 #elif defined(WITH_JIT_TUNING)
717 if (gDvmJit.profile) {
718 BasicBlock *backwardCell =
719 dvmCompilerNewBB(kChainingCellBackwardBranch);
720 lastBB->next = backwardCell;
721 lastBB = backwardCell;
722
723 backwardCell->startOffset = startBB->startOffset;
724 backwardCell->id = numBlocks++;
725 loopBranch->fallThrough = backwardCell;
726 } else {
727 loopBranch->fallThrough = startBB->next;
728 }
729 #else
730 loopBranch->fallThrough = startBB->next;
731 #endif
732
733 /* Create the chaining cell as the fallthrough of the exit block */
734 exitChainingCell = dvmCompilerNewBB(kChainingCellNormal);
735 lastBB->next = exitChainingCell;
736 lastBB = exitChainingCell;
737
738 exitChainingCell->startOffset = targetOffset;
739 exitChainingCell->id = numBlocks++;
740
741 exitBB->fallThrough = exitChainingCell;
742
743 cUnit.hasLoop = true;
744 }
745
746 if (lastInsn->dalvikInsn.opCode == OP_PACKED_SWITCH ||
747 lastInsn->dalvikInsn.opCode == OP_SPARSE_SWITCH) {
748 int i;
749 const u2 *switchData = desc->method->insns + lastInsn->offset +
750 lastInsn->dalvikInsn.vB;
751 int size = switchData[1];
752 int maxChains = MIN(size, MAX_CHAINED_SWITCH_CASES);
753
754 /*
755 * Generate the landing pad for cases whose ranks are higher than
756 * MAX_CHAINED_SWITCH_CASES. The code will re-enter the interpreter
757 * through the NoChain point.
758 */
759 if (maxChains != size) {
760 cUnit.switchOverflowPad =
761 desc->method->insns + lastInsn->offset;
762 }
763
764 s4 *targets = (s4 *) (switchData + 2 +
765 (lastInsn->dalvikInsn.opCode == OP_PACKED_SWITCH ?
766 2 : size * 2));
767
768 /* One chaining cell for the first MAX_CHAINED_SWITCH_CASES cases */
769 for (i = 0; i < maxChains; i++) {
770 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
771 lastBB->next = caseChain;
772 lastBB = caseChain;
773
774 caseChain->startOffset = lastInsn->offset + targets[i];
775 caseChain->id = numBlocks++;
776 }
777
778 /* One more chaining cell for the default case */
779 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
780 lastBB->next = caseChain;
781 lastBB = caseChain;
782
783 caseChain->startOffset = lastInsn->offset + lastInsn->width;
784 caseChain->id = numBlocks++;
785 /* Fallthrough block not included in the trace */
786 } else if (!isUnconditionalBranch(lastInsn) &&
787 curBB->fallThrough == NULL) {
788 /*
789 * If the chaining cell is after an invoke or
790 * instruction that cannot change the control flow, request a hot
791 * chaining cell.
792 */
793 if (isInvoke || curBB->needFallThroughBranch) {
794 lastBB->next = dvmCompilerNewBB(kChainingCellHot);
795 } else {
796 lastBB->next = dvmCompilerNewBB(kChainingCellNormal);
797 }
798 lastBB = lastBB->next;
799 lastBB->id = numBlocks++;
800 lastBB->startOffset = fallThroughOffset;
801 curBB->fallThrough = lastBB;
802 }
803 /* Target block not included in the trace */
804 if (curBB->taken == NULL &&
805 (isGoto(lastInsn) || isInvoke ||
806 (targetOffset != UNKNOWN_TARGET && targetOffset != curOffset))) {
807 BasicBlock *newBB;
808 if (isInvoke) {
809 /* Monomorphic callee */
810 if (callee) {
811 newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton);
812 newBB->startOffset = 0;
813 newBB->containingMethod = callee;
814 /* Will resolve at runtime */
815 } else {
816 newBB = dvmCompilerNewBB(kChainingCellInvokePredicted);
817 newBB->startOffset = 0;
818 }
819 /* For unconditional branches, request a hot chaining cell */
820 } else {
821 #if !defined(WITH_SELF_VERIFICATION)
822 newBB = dvmCompilerNewBB(flags & kInstrUnconditional ?
823 kChainingCellHot :
824 kChainingCellNormal);
825 newBB->startOffset = targetOffset;
826 #else
827 /* Handle branches that branch back into the block */
828 if (targetOffset >= curBB->firstMIRInsn->offset &&
829 targetOffset <= curBB->lastMIRInsn->offset) {
830 newBB = dvmCompilerNewBB(kChainingCellBackwardBranch);
831 } else {
832 newBB = dvmCompilerNewBB(flags & kInstrUnconditional ?
833 kChainingCellHot :
834 kChainingCellNormal);
835 }
836 newBB->startOffset = targetOffset;
837 #endif
838 }
839 newBB->id = numBlocks++;
840 curBB->taken = newBB;
841 lastBB->next = newBB;
842 lastBB = newBB;
843 }
844 }
845
846 /* Now create a special block to host PC reconstruction code */
847 lastBB->next = dvmCompilerNewBB(kPCReconstruction);
848 lastBB = lastBB->next;
849 lastBB->id = numBlocks++;
850
851 /* And one final block that publishes the PC and raise the exception */
852 lastBB->next = dvmCompilerNewBB(kExceptionHandling);
853 lastBB = lastBB->next;
854 lastBB->id = numBlocks++;
855
856 if (cUnit.printMe) {
857 char* signature = dexProtoCopyMethodDescriptor(&desc->method->prototype);
858 LOGD("TRACEINFO (%d): 0x%08x %s%s.%s 0x%x %d of %d, %d blocks",
859 compilationId,
860 (intptr_t) desc->method->insns,
861 desc->method->clazz->descriptor,
862 desc->method->name,
863 signature,
864 desc->trace[0].frag.startOffset,
865 traceSize,
866 dexCode->insnsSize,
867 numBlocks);
868 free(signature);
869 }
870
871 BasicBlock **blockList;
872
873 cUnit.traceDesc = desc;
874 cUnit.numBlocks = numBlocks;
875 blockList = cUnit.blockList =
876 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
877
878 int i;
879
880 for (i = 0, curBB = startBB; i < numBlocks; i++) {
881 blockList[i] = curBB;
882 curBB = curBB->next;
883 }
884 /* Make sure all blocks are added to the cUnit */
885 assert(curBB == NULL);
886
887 /* Set the instruction set to use (NOTE: later components may change it) */
888 cUnit.instructionSet = dvmCompilerInstructionSet();
889
890 /* Inline transformation @ the MIR level */
891 if (cUnit.hasInvoke && !(gDvmJit.disableOpt & (1 << kMethodInlining))) {
892 dvmCompilerInlineMIR(&cUnit);
893 }
894
895 /* Preparation for SSA conversion */
896 dvmInitializeSSAConversion(&cUnit);
897
898 if (cUnit.hasLoop) {
899 /*
900 * Loop is not optimizable (for example lack of a single induction
901 * variable), punt and recompile the trace with loop optimization
902 * disabled.
903 */
904 bool loopOpt = dvmCompilerLoopOpt(&cUnit);
905 if (loopOpt == false) {
906 if (cUnit.printMe) {
907 LOGD("Loop is not optimizable - retry codegen");
908 }
909 /* Reset the compiler resource pool */
910 dvmCompilerArenaReset();
911 return dvmCompileTrace(desc, cUnit.numInsts, info, bailPtr,
912 optHints | JIT_OPT_NO_LOOP);
913 }
914 }
915 else {
916 dvmCompilerNonLoopAnalysis(&cUnit);
917 }
918
919 dvmCompilerInitializeRegAlloc(&cUnit); // Needs to happen after SSA naming
920
921 if (cUnit.printMe) {
922 dvmCompilerDumpCompilationUnit(&cUnit);
923 }
924
925 /* Allocate Registers */
926 dvmCompilerRegAlloc(&cUnit);
927
928 /* Convert MIR to LIR, etc. */
929 dvmCompilerMIR2LIR(&cUnit);
930
931 /* Convert LIR into machine code. Loop for recoverable retries */
932 do {
933 dvmCompilerAssembleLIR(&cUnit, info);
934 cUnit.assemblerRetries++;
935 if (cUnit.printMe && cUnit.assemblerStatus != kSuccess)
936 LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries,
937 cUnit.assemblerStatus);
938 } while (cUnit.assemblerStatus == kRetryAll);
939
940 if (cUnit.printMe) {
941 dvmCompilerCodegenDump(&cUnit);
942 LOGD("End %s%s, %d Dalvik instructions",
943 desc->method->clazz->descriptor, desc->method->name,
944 cUnit.numInsts);
945 }
946
947 /* Reset the compiler resource pool */
948 dvmCompilerArenaReset();
949
950 if (cUnit.assemblerStatus == kRetryHalve) {
951 /* Halve the instruction count and start from the top */
952 return dvmCompileTrace(desc, cUnit.numInsts / 2, info, bailPtr,
953 optHints);
954 }
955
956 assert(cUnit.assemblerStatus == kSuccess);
957 #if defined(WITH_JIT_TUNING)
958 methodStats->nativeSize += cUnit.totalSize;
959 #endif
960 return info->codeAddress != NULL;
961 }
962
963 /*
964 * Since we are including instructions from possibly a cold method into the
965 * current trace, we need to make sure that all the associated information
966 * with the callee is properly initialized. If not, we punt on this inline
967 * target.
968 *
969 * TODO: volatile instructions will be handled later.
970 */
dvmCompilerCanIncludeThisInstruction(const Method * method,const DecodedInstruction * insn)971 bool dvmCompilerCanIncludeThisInstruction(const Method *method,
972 const DecodedInstruction *insn)
973 {
974 switch (insn->opCode) {
975 case OP_NEW_INSTANCE:
976 case OP_CHECK_CAST: {
977 ClassObject *classPtr = (void*)
978 (method->clazz->pDvmDex->pResClasses[insn->vB]);
979
980 /* Class hasn't been initialized yet */
981 if (classPtr == NULL) {
982 return false;
983 }
984 return true;
985 }
986 case OP_SGET_OBJECT:
987 case OP_SGET_BOOLEAN:
988 case OP_SGET_CHAR:
989 case OP_SGET_BYTE:
990 case OP_SGET_SHORT:
991 case OP_SGET:
992 case OP_SGET_WIDE:
993 case OP_SPUT_OBJECT:
994 case OP_SPUT_BOOLEAN:
995 case OP_SPUT_CHAR:
996 case OP_SPUT_BYTE:
997 case OP_SPUT_SHORT:
998 case OP_SPUT:
999 case OP_SPUT_WIDE: {
1000 void *fieldPtr = (void*)
1001 (method->clazz->pDvmDex->pResFields[insn->vB]);
1002
1003 if (fieldPtr == NULL) {
1004 return false;
1005 }
1006 return true;
1007 }
1008 case OP_INVOKE_SUPER:
1009 case OP_INVOKE_SUPER_RANGE: {
1010 int mIndex = method->clazz->pDvmDex->
1011 pResMethods[insn->vB]->methodIndex;
1012 const Method *calleeMethod = method->clazz->super->vtable[mIndex];
1013 if (calleeMethod == NULL) {
1014 return false;
1015 }
1016 return true;
1017 }
1018 case OP_INVOKE_SUPER_QUICK:
1019 case OP_INVOKE_SUPER_QUICK_RANGE: {
1020 const Method *calleeMethod = method->clazz->super->vtable[insn->vB];
1021 if (calleeMethod == NULL) {
1022 return false;
1023 }
1024 return true;
1025 }
1026 case OP_INVOKE_STATIC:
1027 case OP_INVOKE_STATIC_RANGE:
1028 case OP_INVOKE_DIRECT:
1029 case OP_INVOKE_DIRECT_RANGE: {
1030 const Method *calleeMethod =
1031 method->clazz->pDvmDex->pResMethods[insn->vB];
1032 if (calleeMethod == NULL) {
1033 return false;
1034 }
1035 return true;
1036 }
1037 case OP_CONST_CLASS: {
1038 void *classPtr = (void*)
1039 (method->clazz->pDvmDex->pResClasses[insn->vB]);
1040
1041 if (classPtr == NULL) {
1042 return false;
1043 }
1044 return true;
1045 }
1046 case OP_CONST_STRING_JUMBO:
1047 case OP_CONST_STRING: {
1048 void *strPtr = (void*)
1049 (method->clazz->pDvmDex->pResStrings[insn->vB]);
1050
1051 if (strPtr == NULL) {
1052 return false;
1053 }
1054 return true;
1055 }
1056 default:
1057 return true;
1058 }
1059 }
1060
1061 /*
1062 * Similar to dvmCompileTrace, but the entity processed here is the whole
1063 * method.
1064 *
1065 * TODO: implementation will be revisited when the trace builder can provide
1066 * whole-method traces.
1067 */
dvmCompileMethod(CompilationUnit * cUnit,const Method * method,JitTranslationInfo * info)1068 bool dvmCompileMethod(CompilationUnit *cUnit, const Method *method,
1069 JitTranslationInfo *info)
1070 {
1071 const DexCode *dexCode = dvmGetMethodCode(method);
1072 const u2 *codePtr = dexCode->insns;
1073 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
1074 int blockID = 0;
1075 unsigned int curOffset = 0;
1076
1077 /* If we've already compiled this trace, just return success */
1078 if (dvmJitGetCodeAddr(codePtr) && !info->discardResult) {
1079 return true;
1080 }
1081
1082 /* Doing method-based compilation */
1083 cUnit->wholeMethod = true;
1084
1085 BasicBlock *firstBlock = dvmCompilerNewBB(kDalvikByteCode);
1086 firstBlock->id = blockID++;
1087
1088 /* Allocate the bit-vector to track the beginning of basic blocks */
1089 BitVector *bbStartAddr = dvmCompilerAllocBitVector(dexCode->insnsSize+1,
1090 false);
1091 dvmCompilerSetBit(bbStartAddr, 0);
1092
1093 int numInvokeTargets = 0;
1094
1095 /*
1096 * Sequentially go through every instruction first and put them in a single
1097 * basic block. Identify block boundaries at the mean time.
1098 */
1099 while (codePtr < codeEnd) {
1100 MIR *insn = dvmCompilerNew(sizeof(MIR), true);
1101 insn->offset = curOffset;
1102 int width = parseInsn(codePtr, &insn->dalvikInsn, false);
1103 bool isInvoke = false;
1104 const Method *callee;
1105 insn->width = width;
1106
1107 /* Terminate when the data section is seen */
1108 if (width == 0)
1109 break;
1110
1111 if (!dvmCompilerCanIncludeThisInstruction(cUnit->method,
1112 &insn->dalvikInsn)) {
1113 return false;
1114 }
1115
1116 dvmCompilerAppendMIR(firstBlock, insn);
1117 /*
1118 * Check whether this is a block ending instruction and whether it
1119 * suggests the start of a new block
1120 */
1121 unsigned int target = curOffset;
1122
1123 /*
1124 * If findBlockBoundary returns true, it means the current instruction
1125 * is terminating the current block. If it is a branch, the target
1126 * address will be recorded in target.
1127 */
1128 if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke,
1129 &callee)) {
1130 dvmCompilerSetBit(bbStartAddr, curOffset + width);
1131 /* Each invoke needs a chaining cell block */
1132 if (isInvoke) {
1133 numInvokeTargets++;
1134 }
1135 /* A branch will end the current block */
1136 else if (target != curOffset && target != UNKNOWN_TARGET) {
1137 dvmCompilerSetBit(bbStartAddr, target);
1138 }
1139 }
1140
1141 codePtr += width;
1142 /* each bit represents 16-bit quantity */
1143 curOffset += width;
1144 }
1145
1146 /*
1147 * The number of blocks will be equal to the number of bits set to 1 in the
1148 * bit vector minus 1, because the bit representing the location after the
1149 * last instruction is set to one.
1150 *
1151 * We also add additional blocks for invoke chaining and the number is
1152 * denoted by numInvokeTargets.
1153 */
1154 int numBlocks = dvmCountSetBits(bbStartAddr);
1155 if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) {
1156 numBlocks--;
1157 }
1158
1159 BasicBlock **blockList;
1160 blockList = cUnit->blockList =
1161 dvmCompilerNew(sizeof(BasicBlock *) * (numBlocks + numInvokeTargets),
1162 true);
1163
1164 /*
1165 * Register the first block onto the list and start splitting it into
1166 * sub-blocks.
1167 */
1168 blockList[0] = firstBlock;
1169 cUnit->numBlocks = 1;
1170
1171 int i;
1172 for (i = 0; i < numBlocks; i++) {
1173 MIR *insn;
1174 BasicBlock *curBB = blockList[i];
1175 curOffset = curBB->lastMIRInsn->offset;
1176
1177 for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) {
1178 /* Found the beginning of a new block, see if it is created yet */
1179 if (dvmIsBitSet(bbStartAddr, insn->offset)) {
1180 int j;
1181 for (j = 0; j < cUnit->numBlocks; j++) {
1182 if (blockList[j]->firstMIRInsn->offset == insn->offset)
1183 break;
1184 }
1185
1186 /* Block not split yet - do it now */
1187 if (j == cUnit->numBlocks) {
1188 BasicBlock *newBB = dvmCompilerNewBB(kDalvikByteCode);
1189 newBB->id = blockID++;
1190 newBB->firstMIRInsn = insn;
1191 newBB->startOffset = insn->offset;
1192 newBB->lastMIRInsn = curBB->lastMIRInsn;
1193 curBB->lastMIRInsn = insn->prev;
1194 insn->prev->next = NULL;
1195 insn->prev = NULL;
1196
1197 /*
1198 * If the insn is not an unconditional branch, set up the
1199 * fallthrough link.
1200 */
1201 if (!isUnconditionalBranch(curBB->lastMIRInsn)) {
1202 curBB->fallThrough = newBB;
1203 }
1204
1205 /*
1206 * Fallthrough block of an invoke instruction needs to be
1207 * aligned to 4-byte boundary (alignment instruction to be
1208 * inserted later.
1209 */
1210 if (dexGetInstrFlags(gDvm.instrFlags,
1211 curBB->lastMIRInsn->dalvikInsn.opCode) &
1212 kInstrInvoke) {
1213 newBB->isFallThroughFromInvoke = true;
1214 }
1215
1216 /* enqueue the new block */
1217 blockList[cUnit->numBlocks++] = newBB;
1218 break;
1219 }
1220 }
1221 }
1222 }
1223
1224 if (numBlocks != cUnit->numBlocks) {
1225 LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit->numBlocks);
1226 dvmCompilerAbort(cUnit);
1227 }
1228
1229 /* Connect the basic blocks through the taken links */
1230 for (i = 0; i < numBlocks; i++) {
1231 BasicBlock *curBB = blockList[i];
1232 MIR *insn = curBB->lastMIRInsn;
1233 unsigned int target = insn->offset;
1234 bool isInvoke = false;
1235 const Method *callee = NULL;
1236
1237 findBlockBoundary(method, insn, target, &target, &isInvoke, &callee);
1238
1239 /* Found a block ended on a branch (not invoke) */
1240 if (isInvoke == false && target != insn->offset) {
1241 int j;
1242 /* Forward branch */
1243 if (target > insn->offset) {
1244 j = i + 1;
1245 } else {
1246 /* Backward branch */
1247 j = 0;
1248 }
1249 for (; j < numBlocks; j++) {
1250 if (blockList[j]->firstMIRInsn->offset == target) {
1251 curBB->taken = blockList[j];
1252 break;
1253 }
1254 }
1255 }
1256
1257 if (isInvoke) {
1258 BasicBlock *newBB;
1259 /* Monomorphic callee */
1260 if (callee) {
1261 newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton);
1262 newBB->startOffset = 0;
1263 newBB->containingMethod = callee;
1264 /* Will resolve at runtime */
1265 } else {
1266 newBB = dvmCompilerNewBB(kChainingCellInvokePredicted);
1267 newBB->startOffset = 0;
1268 }
1269 newBB->id = blockID++;
1270 curBB->taken = newBB;
1271 /* enqueue the new block */
1272 blockList[cUnit->numBlocks++] = newBB;
1273 }
1274 }
1275
1276 if (cUnit->numBlocks != numBlocks + numInvokeTargets) {
1277 LOGE("Expect %d vs %d total blocks\n", numBlocks + numInvokeTargets,
1278 cUnit->numBlocks);
1279 dvmCompilerDumpCompilationUnit(cUnit);
1280 dvmCompilerAbort(cUnit);
1281 }
1282
1283 /* Set the instruction set to use (NOTE: later components may change it) */
1284 cUnit->instructionSet = dvmCompilerInstructionSet();
1285
1286 /* Preparation for SSA conversion */
1287 dvmInitializeSSAConversion(cUnit);
1288
1289 /* SSA analysis */
1290 dvmCompilerNonLoopAnalysis(cUnit);
1291
1292 /* Needs to happen after SSA naming */
1293 dvmCompilerInitializeRegAlloc(cUnit);
1294
1295 /* Allocate Registers */
1296 dvmCompilerRegAlloc(cUnit);
1297
1298 /* Convert MIR to LIR, etc. */
1299 dvmCompilerMIR2LIR(cUnit);
1300
1301 /* Convert LIR into machine code. */
1302 dvmCompilerAssembleLIR(cUnit, info);
1303
1304 if (cUnit->assemblerStatus != kSuccess) {
1305 return false;
1306 }
1307
1308 dvmCompilerDumpCompilationUnit(cUnit);
1309
1310 dvmCompilerArenaReset();
1311
1312 return info->codeAddress != NULL;
1313 }
1314