blob: 6e8d964684fd60e41b9ce80274f6c17009f21534 [file] [log] [blame]
Ben Chengba4fc8b2009-06-01 13:00:29 -07001/*
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 "dexdump/OpCodeNames.h"
20#include "interp/Jit.h"
21#include "CompilerInternals.h"
22
23/*
24 * Parse an instruction, return the length of the instruction
25 */
26static 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 // Need to check if this is a real NOP or a pseudo opcode
34 if (opcode == OP_NOP && instr != 0) {
35 if (instr == kPackedSwitchSignature) {
36 insnWidth = 4 + codePtr[1] * 2;
37 } else if (instr == kSparseSwitchSignature) {
38 insnWidth = 2 + codePtr[1] * 4;
39 } else if (instr == kArrayDataSignature) {
40 int width = codePtr[1];
41 int size = codePtr[2] | (codePtr[3] << 16);
42 // The plus 1 is to round up for odd size and width
43 insnWidth = 4 + ((size * width) + 1) / 2;
44 }
45 insnWidth = 0;
46 } else {
47 insnWidth = gDvm.instrWidth[opcode];
48 if (insnWidth < 0) {
49 insnWidth = -insnWidth;
50 }
51 }
52
53 dexDecodeInstruction(gDvm.instrFormat, codePtr, decInsn);
54 if (printMe) {
55 LOGD("%p: %#06x %s\n", codePtr, opcode, getOpcodeName(opcode));
56 }
57 return insnWidth;
58}
59
60/*
61 * Identify block-ending instructions and collect supplemental information
62 * regarding the following instructions.
63 */
64static inline bool findBlockBoundary(const Method *caller, MIR *insn,
65 unsigned int curOffset,
66 unsigned int *target, bool *isInvoke,
67 const Method **callee)
68{
69 switch (insn->dalvikInsn.opCode) {
70 /* Target is not compile-time constant */
71 case OP_RETURN_VOID:
72 case OP_RETURN:
73 case OP_RETURN_WIDE:
74 case OP_RETURN_OBJECT:
75 case OP_THROW:
76 case OP_INVOKE_VIRTUAL:
77 case OP_INVOKE_VIRTUAL_RANGE:
78 case OP_INVOKE_INTERFACE:
79 case OP_INVOKE_INTERFACE_RANGE:
80 case OP_INVOKE_VIRTUAL_QUICK:
81 case OP_INVOKE_VIRTUAL_QUICK_RANGE:
82 *isInvoke = true;
83 break;
84 case OP_INVOKE_SUPER:
85 case OP_INVOKE_SUPER_RANGE: {
86 int mIndex = caller->clazz->pDvmDex->
87 pResMethods[insn->dalvikInsn.vB]->methodIndex;
88 const Method *calleeMethod =
89 caller->clazz->super->vtable[mIndex];
90
91 if (!dvmIsNativeMethod(calleeMethod)) {
92 *target = (unsigned int) calleeMethod->insns;
93 }
94 *isInvoke = true;
95 *callee = calleeMethod;
96 break;
97 }
98 case OP_INVOKE_STATIC:
99 case OP_INVOKE_STATIC_RANGE: {
100 const Method *calleeMethod =
101 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
102
103 if (!dvmIsNativeMethod(calleeMethod)) {
104 *target = (unsigned int) calleeMethod->insns;
105 }
106 *isInvoke = true;
107 *callee = calleeMethod;
108 break;
109 }
110 case OP_INVOKE_SUPER_QUICK:
111 case OP_INVOKE_SUPER_QUICK_RANGE: {
112 const Method *calleeMethod =
113 caller->clazz->super->vtable[insn->dalvikInsn.vB];
114
115 if (!dvmIsNativeMethod(calleeMethod)) {
116 *target = (unsigned int) calleeMethod->insns;
117 }
118 *isInvoke = true;
119 *callee = calleeMethod;
120 break;
121 }
122 case OP_INVOKE_DIRECT:
123 case OP_INVOKE_DIRECT_RANGE: {
124 const Method *calleeMethod =
125 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
126 if (!dvmIsNativeMethod(calleeMethod)) {
127 *target = (unsigned int) calleeMethod->insns;
128 }
129 *isInvoke = true;
130 *callee = calleeMethod;
131 break;
132 }
133 case OP_GOTO:
134 case OP_GOTO_16:
135 case OP_GOTO_32:
136 *target = curOffset + (int) insn->dalvikInsn.vA;
137 break;
138
139 case OP_IF_EQ:
140 case OP_IF_NE:
141 case OP_IF_LT:
142 case OP_IF_GE:
143 case OP_IF_GT:
144 case OP_IF_LE:
145 *target = curOffset + (int) insn->dalvikInsn.vC;
146 break;
147
148 case OP_IF_EQZ:
149 case OP_IF_NEZ:
150 case OP_IF_LTZ:
151 case OP_IF_GEZ:
152 case OP_IF_GTZ:
153 case OP_IF_LEZ:
154 *target = curOffset + (int) insn->dalvikInsn.vB;
155 break;
156
157 default:
158 return false;
159 } return true;
160}
161
162/*
163 * Identify conditional branch instructions
164 */
165static inline bool isUnconditionalBranch(MIR *insn)
166{
167 switch (insn->dalvikInsn.opCode) {
168 case OP_RETURN_VOID:
169 case OP_RETURN:
170 case OP_RETURN_WIDE:
171 case OP_RETURN_OBJECT:
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 * Main entry point to start trace compilation. Basic blocks are constructed
183 * first and they will be passed to the codegen routines to convert Dalvik
184 * bytecode into machine code.
185 */
Ben Cheng1efc9c52009-06-08 18:25:27 -0700186void *dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts)
Ben Chengba4fc8b2009-06-01 13:00:29 -0700187{
188 const DexCode *dexCode = dvmGetMethodCode(desc->method);
189 const JitTraceRun* currRun = &desc->trace[0];
Ben Chengba4fc8b2009-06-01 13:00:29 -0700190 unsigned int curOffset = currRun->frag.startOffset;
191 unsigned int numInsts = currRun->frag.numInsts;
192 const u2 *codePtr = dexCode->insns + curOffset;
193 int traceSize = 0;
194 const u2 *startCodePtr = codePtr;
195 BasicBlock *startBB, *curBB, *lastBB;
196 int numBlocks = 0;
197 static int compilationId;
198 CompilationUnit cUnit;
199 memset(&cUnit, 0, sizeof(CompilationUnit));
200
201 /* Initialize the printMe flag */
202 cUnit.printMe = gDvmJit.printMe;
203
204 /* Identify traces that we don't want to compile */
205 if (gDvmJit.methodTable) {
206 int len = strlen(desc->method->clazz->descriptor) +
207 strlen(desc->method->name) + 1;
208 char *fullSignature = dvmCompilerNew(len, true);
209 strcpy(fullSignature, desc->method->clazz->descriptor);
210 strcat(fullSignature, desc->method->name);
211
212 int hashValue = dvmComputeUtf8Hash(fullSignature);
213
214 /*
215 * Doing three levels of screening to see whether we want to skip
216 * compiling this method
217 */
218
219 /* First, check the full "class;method" signature */
220 bool methodFound =
221 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
222 fullSignature, (HashCompareFunc) strcmp,
223 false) !=
224 NULL;
225
226 /* Full signature not found - check the enclosing class */
227 if (methodFound == false) {
228 int hashValue = dvmComputeUtf8Hash(desc->method->clazz->descriptor);
229 methodFound =
230 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
231 (char *) desc->method->clazz->descriptor,
232 (HashCompareFunc) strcmp, false) !=
233 NULL;
234 /* Enclosing class not found - check the method name */
235 if (methodFound == false) {
236 int hashValue = dvmComputeUtf8Hash(desc->method->name);
237 methodFound =
238 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
239 (char *) desc->method->name,
240 (HashCompareFunc) strcmp, false) !=
241 NULL;
242 }
243 }
244
245 /*
246 * Under the following conditions, the trace will be *conservatively*
247 * compiled by only containing single-step instructions to and from the
248 * interpreter.
249 * 1) If includeSelectedMethod == false, the method matches the full or
250 * partial signature stored in the hash table.
251 *
252 * 2) If includeSelectedMethod == true, the method does not match the
253 * full and partial signature stored in the hash table.
254 */
255 if (gDvmJit.includeSelectedMethod != methodFound) {
256 cUnit.allSingleStep = true;
257 } else {
258 /* Compile the trace as normal */
259
260 /* Print the method we cherry picked */
261 if (gDvmJit.includeSelectedMethod == true) {
262 cUnit.printMe = true;
263 }
264 }
265 }
266
267 /* Allocate the first basic block */
268 lastBB = startBB = curBB = dvmCompilerNewBB(DALVIK_BYTECODE);
269 curBB->startOffset = curOffset;
270 curBB->id = numBlocks++;
271
272 if (cUnit.printMe) {
273 LOGD("--------\nCompiler: Building trace for %s, offset 0x%x\n",
274 desc->method->name, curOffset);
275 }
276
Ben Cheng1efc9c52009-06-08 18:25:27 -0700277 /*
278 * Analyze the trace descriptor and include up to the maximal number
279 * of Dalvik instructions into the IR.
280 */
281 while (1) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700282 MIR *insn;
283 int width;
284 insn = dvmCompilerNew(sizeof(MIR),false);
285 insn->offset = curOffset;
286 width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe);
287 insn->width = width;
288 traceSize += width;
289 dvmCompilerAppendMIR(curBB, insn);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700290 cUnit.numInsts++;
291 /* Instruction limit reached - terminate the trace here */
292 if (cUnit.numInsts >= numMaxInsts) {
293 break;
294 }
295 if (--numInsts == 0) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700296 if (currRun->frag.runEnd) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700297 break;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700298 } else {
299 curBB = dvmCompilerNewBB(DALVIK_BYTECODE);
300 lastBB->next = curBB;
301 lastBB = curBB;
302 curBB->id = numBlocks++;
303 currRun++;
304 curOffset = currRun->frag.startOffset;
305 numInsts = currRun->frag.numInsts;
306 curBB->startOffset = curOffset;
307 codePtr = dexCode->insns + curOffset;
308 }
309 } else {
310 curOffset += width;
311 codePtr += width;
312 }
313 }
314
315 /*
316 * Now scan basic blocks containing real code to connect the
317 * taken/fallthrough links. Also create chaining cells for code not included
318 * in the trace.
319 */
320 for (curBB = startBB; curBB; curBB = curBB->next) {
321 MIR *lastInsn = curBB->lastMIRInsn;
322 /* Hit a pseudo block - exit the search now */
323 if (lastInsn == NULL) {
324 break;
325 }
326 curOffset = lastInsn->offset;
327 unsigned int targetOffset = curOffset;
328 unsigned int fallThroughOffset = curOffset + lastInsn->width;
329 bool isInvoke = false;
330 const Method *callee = NULL;
331
332 findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset,
333 &targetOffset, &isInvoke, &callee);
334
335 /* Link the taken and fallthrough blocks */
336 BasicBlock *searchBB;
337
338 /* No backward branch in the trace - start searching the next BB */
339 for (searchBB = curBB->next; searchBB; searchBB = searchBB->next) {
340 if (targetOffset == searchBB->startOffset) {
341 curBB->taken = searchBB;
342 }
343 if (fallThroughOffset == searchBB->startOffset) {
344 curBB->fallThrough = searchBB;
345 }
346 }
347
Ben Cheng1efc9c52009-06-08 18:25:27 -0700348 int flags = dexGetInstrFlags(gDvm.instrFlags,
349 lastInsn->dalvikInsn.opCode);
350
351 /*
352 * Some blocks are ended by non-control-flow-change instructions,
353 * currently only due to trace length constraint. In this case we need
354 * to generate an explicit branch at the end of the block to jump to
355 * the chaining cell.
356 */
357 curBB->needFallThroughBranch =
358 (flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
359 kInstrInvoke)) == 0;
360
Ben Chengba4fc8b2009-06-01 13:00:29 -0700361 /* Target block not included in the trace */
362 if (targetOffset != curOffset && curBB->taken == NULL) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700363 if (isInvoke) {
364 lastBB->next = dvmCompilerNewBB(CHAINING_CELL_INVOKE);
365 /* For unconditional branches, request a hot chaining cell */
366 } else {
367 lastBB->next = dvmCompilerNewBB(flags & kInstrUnconditional ?
368 CHAINING_CELL_HOT :
369 CHAINING_CELL_NORMAL);
370 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700371 lastBB = lastBB->next;
372 lastBB->id = numBlocks++;
373 if (isInvoke) {
374 lastBB->startOffset = 0;
375 lastBB->containingMethod = callee;
376 } else {
377 lastBB->startOffset = targetOffset;
378 }
379 curBB->taken = lastBB;
380 }
381
382 /* Fallthrough block not included in the trace */
383 if (!isUnconditionalBranch(lastInsn) && curBB->fallThrough == NULL) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700384 /*
385 * If the chaining cell is after an invoke or
386 * instruction that cannot change the control flow, request a hot
387 * chaining cell.
388 */
389 if (isInvoke || curBB->needFallThroughBranch) {
390 lastBB->next = dvmCompilerNewBB(CHAINING_CELL_HOT);
391 } else {
392 lastBB->next = dvmCompilerNewBB(CHAINING_CELL_NORMAL);
393 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700394 lastBB = lastBB->next;
395 lastBB->id = numBlocks++;
396 lastBB->startOffset = fallThroughOffset;
397 curBB->fallThrough = lastBB;
398 }
399 }
400
401 /* Now create a special block to host PC reconstruction code */
402 lastBB->next = dvmCompilerNewBB(PC_RECONSTRUCTION);
403 lastBB = lastBB->next;
404 lastBB->id = numBlocks++;
405
406 /* And one final block that publishes the PC and raise the exception */
407 lastBB->next = dvmCompilerNewBB(EXCEPTION_HANDLING);
408 lastBB = lastBB->next;
409 lastBB->id = numBlocks++;
410
411 if (cUnit.printMe) {
412 LOGD("TRACEINFO (%d): 0x%08x %s%s 0x%x %d of %d, %d blocks",
413 compilationId++,
414 (intptr_t) desc->method->insns,
415 desc->method->clazz->descriptor,
416 desc->method->name,
417 desc->trace[0].frag.startOffset,
418 traceSize,
419 dexCode->insnsSize,
420 numBlocks);
421 }
422
423 BasicBlock **blockList;
424
425 cUnit.method = desc->method;
426 cUnit.traceDesc = desc;
427 cUnit.numBlocks = numBlocks;
428 dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
429 blockList = cUnit.blockList =
430 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
431
432 int i;
433
434 for (i = 0, curBB = startBB; i < numBlocks; i++) {
435 blockList[i] = curBB;
436 curBB = curBB->next;
437 }
438 /* Make sure all blocks are added to the cUnit */
439 assert(curBB == NULL);
440
441 if (cUnit.printMe) {
442 dvmCompilerDumpCompilationUnit(&cUnit);
443 }
444
445 /* Convert MIR to LIR, etc. */
446 dvmCompilerMIR2LIR(&cUnit);
447
Ben Cheng1efc9c52009-06-08 18:25:27 -0700448 /* Convert LIR into machine code. */
Ben Chengba4fc8b2009-06-01 13:00:29 -0700449 dvmCompilerAssembleLIR(&cUnit);
450
451 if (cUnit.printMe) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700452 if (cUnit.halveInstCount) {
453 LOGD("Assembler aborted");
454 } else {
455 dvmCompilerCodegenDump(&cUnit);
456 }
457 LOGD("End %s%s, %d Dalvik instructions",
458 desc->method->clazz->descriptor, desc->method->name,
459 cUnit.numInsts);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700460 }
461
462 /* Reset the compiler resource pool */
463 dvmCompilerArenaReset();
464
Ben Cheng1efc9c52009-06-08 18:25:27 -0700465 /*
466 * Things have gone smoothly - publish the starting address of
467 * translation's entry point.
468 */
469 if (!cUnit.halveInstCount) {
470 return cUnit.baseAddr + cUnit.headerSize;
471
472 /* Halve the instruction count and retry again */
473 } else {
474 return dvmCompileTrace(desc, cUnit.numInsts / 2);
475 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700476}
477
478/*
479 * Similar to dvmCompileTrace, but the entity processed here is the whole
480 * method.
481 *
482 * TODO: implementation will be revisited when the trace builder can provide
483 * whole-method traces.
484 */
485void *dvmCompileMethod(Method *method)
486{
487 const DexCode *dexCode = dvmGetMethodCode(method);
488 const u2 *codePtr = dexCode->insns;
489 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
490 int blockID = 0;
491 unsigned int curOffset = 0;
492
493 BasicBlock *firstBlock = dvmCompilerNewBB(DALVIK_BYTECODE);
494 firstBlock->id = blockID++;
495
496 /* Allocate the bit-vector to track the beginning of basic blocks */
497 BitVector *bbStartAddr = dvmAllocBitVector(dexCode->insnsSize+1, false);
498 dvmSetBit(bbStartAddr, 0);
499
500 /*
501 * Sequentially go through every instruction first and put them in a single
502 * basic block. Identify block boundaries at the mean time.
503 */
504 while (codePtr < codeEnd) {
505 MIR *insn = dvmCompilerNew(sizeof(MIR), false);
506 insn->offset = curOffset;
507 int width = parseInsn(codePtr, &insn->dalvikInsn, false);
508 bool isInvoke = false;
509 const Method *callee;
510 insn->width = width;
511
512 dvmCompilerAppendMIR(firstBlock, insn);
513 /*
514 * Check whether this is a block ending instruction and whether it
515 * suggests the start of a new block
516 */
517 unsigned int target = curOffset;
518
519 /*
520 * If findBlockBoundary returns true, it means the current instruction
521 * is terminating the current block. If it is a branch, the target
522 * address will be recorded in target.
523 */
524 if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke,
525 &callee)) {
526 dvmSetBit(bbStartAddr, curOffset + width);
527 if (target != curOffset) {
528 dvmSetBit(bbStartAddr, target);
529 }
530 }
531
532 codePtr += width;
533 /* each bit represents 16-bit quantity */
534 curOffset += width;
535 }
536
537 /*
538 * The number of blocks will be equal to the number of bits set to 1 in the
539 * bit vector minus 1, because the bit representing the location after the
540 * last instruction is set to one.
541 */
542 int numBlocks = dvmCountSetBits(bbStartAddr);
543 if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) {
544 numBlocks--;
545 }
546
547 CompilationUnit cUnit;
548 BasicBlock **blockList;
549
550 memset(&cUnit, 0, sizeof(CompilationUnit));
551 cUnit.method = method;
552 blockList = cUnit.blockList =
553 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
554
555 /*
556 * Register the first block onto the list and start split it into block
557 * boundaries from there.
558 */
559 blockList[0] = firstBlock;
560 cUnit.numBlocks = 1;
561
562 int i;
563 for (i = 0; i < numBlocks; i++) {
564 MIR *insn;
565 BasicBlock *curBB = blockList[i];
566 curOffset = curBB->lastMIRInsn->offset;
567
568 for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) {
569 /* Found the beginning of a new block, see if it is created yet */
570 if (dvmIsBitSet(bbStartAddr, insn->offset)) {
571 int j;
572 for (j = 0; j < cUnit.numBlocks; j++) {
573 if (blockList[j]->firstMIRInsn->offset == insn->offset)
574 break;
575 }
576
577 /* Block not split yet - do it now */
578 if (j == cUnit.numBlocks) {
579 BasicBlock *newBB = dvmCompilerNewBB(DALVIK_BYTECODE);
580 newBB->id = blockID++;
581 newBB->firstMIRInsn = insn;
582 newBB->lastMIRInsn = curBB->lastMIRInsn;
583 curBB->lastMIRInsn = insn->prev;
584 insn->prev->next = NULL;
585 insn->prev = NULL;
586
587 /*
588 * If the insn is not an unconditional branch, set up the
589 * fallthrough link.
590 */
591 if (!isUnconditionalBranch(curBB->lastMIRInsn)) {
592 curBB->fallThrough = newBB;
593 }
594
595 /* enqueue the new block */
596 blockList[cUnit.numBlocks++] = newBB;
597 break;
598 }
599 }
600 }
601 }
602
603 if (numBlocks != cUnit.numBlocks) {
604 LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit.numBlocks);
605 dvmAbort();
606 }
607
608 dvmFreeBitVector(bbStartAddr);
609
610 /* Connect the basic blocks through the taken links */
611 for (i = 0; i < numBlocks; i++) {
612 BasicBlock *curBB = blockList[i];
613 MIR *insn = curBB->lastMIRInsn;
614 unsigned int target = insn->offset;
615 bool isInvoke;
616 const Method *callee;
617
618 findBlockBoundary(method, insn, target, &target, &isInvoke, &callee);
619
620 /* Found a block ended on a branch */
621 if (target != insn->offset) {
622 int j;
623 /* Forward branch */
624 if (target > insn->offset) {
625 j = i + 1;
626 } else {
627 /* Backward branch */
628 j = 0;
629 }
630 for (; j < numBlocks; j++) {
631 if (blockList[j]->firstMIRInsn->offset == target) {
632 curBB->taken = blockList[j];
633 break;
634 }
635 }
636
637 if (j == numBlocks) {
638 LOGE("Target not found for insn %x: expect target %x\n",
639 curBB->lastMIRInsn->offset, target);
640 dvmAbort();
641 }
642 }
643 }
644
645 dvmCompilerMIR2LIR(&cUnit);
646
647 dvmCompilerAssembleLIR(&cUnit);
648
649 dvmCompilerDumpCompilationUnit(&cUnit);
650
651 dvmCompilerArenaReset();
652
Ben Cheng1efc9c52009-06-08 18:25:27 -0700653 return cUnit.baseAddr + cUnit.headerSize;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700654}