blob: 6ed32ca3b6dc3dec381b245a353a5e02091b6beb [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
Ben Cheng8b258bf2009-06-24 17:27:07 -070033 // Don't parse instruction data
Ben Chengba4fc8b2009-06-01 13:00:29 -070034 if (opcode == OP_NOP && instr != 0) {
Ben Cheng8b258bf2009-06-24 17:27:07 -070035 return 0;
Ben Chengba4fc8b2009-06-01 13:00:29 -070036 } 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 LOGD("%p: %#06x %s\n", codePtr, opcode, getOpcodeName(opcode));
46 }
47 return insnWidth;
48}
49
50/*
51 * Identify block-ending instructions and collect supplemental information
52 * regarding the following instructions.
53 */
54static inline bool findBlockBoundary(const Method *caller, MIR *insn,
55 unsigned int curOffset,
56 unsigned int *target, bool *isInvoke,
57 const Method **callee)
58{
59 switch (insn->dalvikInsn.opCode) {
60 /* Target is not compile-time constant */
61 case OP_RETURN_VOID:
62 case OP_RETURN:
63 case OP_RETURN_WIDE:
64 case OP_RETURN_OBJECT:
65 case OP_THROW:
66 case OP_INVOKE_VIRTUAL:
67 case OP_INVOKE_VIRTUAL_RANGE:
68 case OP_INVOKE_INTERFACE:
69 case OP_INVOKE_INTERFACE_RANGE:
70 case OP_INVOKE_VIRTUAL_QUICK:
71 case OP_INVOKE_VIRTUAL_QUICK_RANGE:
72 *isInvoke = true;
73 break;
74 case OP_INVOKE_SUPER:
75 case OP_INVOKE_SUPER_RANGE: {
76 int mIndex = caller->clazz->pDvmDex->
77 pResMethods[insn->dalvikInsn.vB]->methodIndex;
78 const Method *calleeMethod =
79 caller->clazz->super->vtable[mIndex];
80
Ben Cheng8b258bf2009-06-24 17:27:07 -070081 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -070082 *target = (unsigned int) calleeMethod->insns;
83 }
84 *isInvoke = true;
85 *callee = calleeMethod;
86 break;
87 }
88 case OP_INVOKE_STATIC:
89 case OP_INVOKE_STATIC_RANGE: {
90 const Method *calleeMethod =
91 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
92
Ben Cheng8b258bf2009-06-24 17:27:07 -070093 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -070094 *target = (unsigned int) calleeMethod->insns;
95 }
96 *isInvoke = true;
97 *callee = calleeMethod;
98 break;
99 }
100 case OP_INVOKE_SUPER_QUICK:
101 case OP_INVOKE_SUPER_QUICK_RANGE: {
102 const Method *calleeMethod =
103 caller->clazz->super->vtable[insn->dalvikInsn.vB];
104
Ben Cheng8b258bf2009-06-24 17:27:07 -0700105 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700106 *target = (unsigned int) calleeMethod->insns;
107 }
108 *isInvoke = true;
109 *callee = calleeMethod;
110 break;
111 }
112 case OP_INVOKE_DIRECT:
113 case OP_INVOKE_DIRECT_RANGE: {
114 const Method *calleeMethod =
115 caller->clazz->pDvmDex->pResMethods[insn->dalvikInsn.vB];
Ben Cheng8b258bf2009-06-24 17:27:07 -0700116 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700117 *target = (unsigned int) calleeMethod->insns;
118 }
119 *isInvoke = true;
120 *callee = calleeMethod;
121 break;
122 }
123 case OP_GOTO:
124 case OP_GOTO_16:
125 case OP_GOTO_32:
126 *target = curOffset + (int) insn->dalvikInsn.vA;
127 break;
128
129 case OP_IF_EQ:
130 case OP_IF_NE:
131 case OP_IF_LT:
132 case OP_IF_GE:
133 case OP_IF_GT:
134 case OP_IF_LE:
135 *target = curOffset + (int) insn->dalvikInsn.vC;
136 break;
137
138 case OP_IF_EQZ:
139 case OP_IF_NEZ:
140 case OP_IF_LTZ:
141 case OP_IF_GEZ:
142 case OP_IF_GTZ:
143 case OP_IF_LEZ:
144 *target = curOffset + (int) insn->dalvikInsn.vB;
145 break;
146
147 default:
148 return false;
149 } return true;
150}
151
152/*
153 * Identify conditional branch instructions
154 */
155static inline bool isUnconditionalBranch(MIR *insn)
156{
157 switch (insn->dalvikInsn.opCode) {
158 case OP_RETURN_VOID:
159 case OP_RETURN:
160 case OP_RETURN_WIDE:
161 case OP_RETURN_OBJECT:
162 case OP_GOTO:
163 case OP_GOTO_16:
164 case OP_GOTO_32:
165 return true;
166 default:
167 return false;
168 }
169}
170
171/*
Ben Cheng8b258bf2009-06-24 17:27:07 -0700172 * dvmHashTableLookup() callback
173 */
174static int compareMethod(const CompilerMethodStats *m1,
175 const CompilerMethodStats *m2)
176{
177 return (int) m1->method - (int) m2->method;
178}
179
180/*
181 * Analyze each method whose traces are ever compiled. Collect a variety of
182 * statistics like the ratio of exercised vs overall code and code bloat
183 * ratios.
184 */
185static CompilerMethodStats *analyzeMethodBody(const Method *method)
186{
187 const DexCode *dexCode = dvmGetMethodCode(method);
188 const u2 *codePtr = dexCode->insns;
189 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
190 int insnSize = 0;
191 int hashValue = dvmComputeUtf8Hash(method->name);
192
193 CompilerMethodStats dummyMethodEntry; // For hash table lookup
194 CompilerMethodStats *realMethodEntry; // For hash table storage
195
196 /* For lookup only */
197 dummyMethodEntry.method = method;
198 realMethodEntry = dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
199 &dummyMethodEntry,
200 (HashCompareFunc) compareMethod,
201 false);
202
203 /* Part of this method has been compiled before - just return the entry */
204 if (realMethodEntry != NULL) {
205 return realMethodEntry;
206 }
207
208 /*
209 * First time to compile this method - set up a new entry in the hash table
210 */
211 realMethodEntry =
212 (CompilerMethodStats *) calloc(1, sizeof(CompilerMethodStats));
213 realMethodEntry->method = method;
214
215 dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
216 realMethodEntry,
217 (HashCompareFunc) compareMethod,
218 true);
219
220 /* Count the number of instructions */
221 while (codePtr < codeEnd) {
222 DecodedInstruction dalvikInsn;
223 int width = parseInsn(codePtr, &dalvikInsn, false);
224
225 /* Terminate when the data section is seen */
226 if (width == 0)
227 break;
228
229 insnSize += width;
230 codePtr += width;
231 }
232
233 realMethodEntry->dalvikSize = insnSize * 2;
234 return realMethodEntry;
235}
236
237/*
Ben Chengba4fc8b2009-06-01 13:00:29 -0700238 * Main entry point to start trace compilation. Basic blocks are constructed
239 * first and they will be passed to the codegen routines to convert Dalvik
240 * bytecode into machine code.
241 */
Bill Buzbee716f1202009-07-23 13:22:09 -0700242bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts,
243 JitTranslationInfo *info)
Ben Chengba4fc8b2009-06-01 13:00:29 -0700244{
245 const DexCode *dexCode = dvmGetMethodCode(desc->method);
246 const JitTraceRun* currRun = &desc->trace[0];
Ben Chengba4fc8b2009-06-01 13:00:29 -0700247 unsigned int curOffset = currRun->frag.startOffset;
248 unsigned int numInsts = currRun->frag.numInsts;
249 const u2 *codePtr = dexCode->insns + curOffset;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700250 int traceSize = 0; // # of half-words
Ben Chengba4fc8b2009-06-01 13:00:29 -0700251 const u2 *startCodePtr = codePtr;
252 BasicBlock *startBB, *curBB, *lastBB;
253 int numBlocks = 0;
254 static int compilationId;
255 CompilationUnit cUnit;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700256 CompilerMethodStats *methodStats;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700257
Ben Chenge9695e52009-06-16 16:11:47 -0700258 compilationId++;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700259 memset(&cUnit, 0, sizeof(CompilationUnit));
260
261 /* Locate the entry to store compilation statistics for this method */
262 methodStats = analyzeMethodBody(desc->method);
Ben Chenge9695e52009-06-16 16:11:47 -0700263
264 cUnit.registerScoreboard.nullCheckedRegs =
265 dvmAllocBitVector(desc->method->registersSize, false);
266
Ben Chengba4fc8b2009-06-01 13:00:29 -0700267 /* Initialize the printMe flag */
268 cUnit.printMe = gDvmJit.printMe;
269
Bill Buzbee6e963e12009-06-17 16:56:19 -0700270 /* Initialize the profile flag */
271 cUnit.executionCount = gDvmJit.profile;
272
Ben Chengba4fc8b2009-06-01 13:00:29 -0700273 /* Identify traces that we don't want to compile */
274 if (gDvmJit.methodTable) {
275 int len = strlen(desc->method->clazz->descriptor) +
276 strlen(desc->method->name) + 1;
277 char *fullSignature = dvmCompilerNew(len, true);
278 strcpy(fullSignature, desc->method->clazz->descriptor);
279 strcat(fullSignature, desc->method->name);
280
281 int hashValue = dvmComputeUtf8Hash(fullSignature);
282
283 /*
284 * Doing three levels of screening to see whether we want to skip
285 * compiling this method
286 */
287
288 /* First, check the full "class;method" signature */
289 bool methodFound =
290 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
291 fullSignature, (HashCompareFunc) strcmp,
292 false) !=
293 NULL;
294
295 /* Full signature not found - check the enclosing class */
296 if (methodFound == false) {
297 int hashValue = dvmComputeUtf8Hash(desc->method->clazz->descriptor);
298 methodFound =
299 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
300 (char *) desc->method->clazz->descriptor,
301 (HashCompareFunc) strcmp, false) !=
302 NULL;
303 /* Enclosing class not found - check the method name */
304 if (methodFound == false) {
305 int hashValue = dvmComputeUtf8Hash(desc->method->name);
306 methodFound =
307 dvmHashTableLookup(gDvmJit.methodTable, hashValue,
308 (char *) desc->method->name,
309 (HashCompareFunc) strcmp, false) !=
310 NULL;
311 }
312 }
313
314 /*
315 * Under the following conditions, the trace will be *conservatively*
316 * compiled by only containing single-step instructions to and from the
317 * interpreter.
318 * 1) If includeSelectedMethod == false, the method matches the full or
319 * partial signature stored in the hash table.
320 *
321 * 2) If includeSelectedMethod == true, the method does not match the
322 * full and partial signature stored in the hash table.
323 */
324 if (gDvmJit.includeSelectedMethod != methodFound) {
325 cUnit.allSingleStep = true;
326 } else {
327 /* Compile the trace as normal */
328
329 /* Print the method we cherry picked */
330 if (gDvmJit.includeSelectedMethod == true) {
331 cUnit.printMe = true;
332 }
333 }
334 }
335
336 /* Allocate the first basic block */
337 lastBB = startBB = curBB = dvmCompilerNewBB(DALVIK_BYTECODE);
338 curBB->startOffset = curOffset;
339 curBB->id = numBlocks++;
340
341 if (cUnit.printMe) {
342 LOGD("--------\nCompiler: Building trace for %s, offset 0x%x\n",
343 desc->method->name, curOffset);
344 }
345
Ben Cheng1efc9c52009-06-08 18:25:27 -0700346 /*
347 * Analyze the trace descriptor and include up to the maximal number
348 * of Dalvik instructions into the IR.
349 */
350 while (1) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700351 MIR *insn;
352 int width;
353 insn = dvmCompilerNew(sizeof(MIR),false);
354 insn->offset = curOffset;
355 width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe);
Ben Cheng8b258bf2009-06-24 17:27:07 -0700356
357 /* The trace should never incude instruction data */
358 assert(width);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700359 insn->width = width;
360 traceSize += width;
361 dvmCompilerAppendMIR(curBB, insn);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700362 cUnit.numInsts++;
363 /* Instruction limit reached - terminate the trace here */
364 if (cUnit.numInsts >= numMaxInsts) {
365 break;
366 }
367 if (--numInsts == 0) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700368 if (currRun->frag.runEnd) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700369 break;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700370 } else {
371 curBB = dvmCompilerNewBB(DALVIK_BYTECODE);
372 lastBB->next = curBB;
373 lastBB = curBB;
374 curBB->id = numBlocks++;
375 currRun++;
376 curOffset = currRun->frag.startOffset;
377 numInsts = currRun->frag.numInsts;
378 curBB->startOffset = curOffset;
379 codePtr = dexCode->insns + curOffset;
380 }
381 } else {
382 curOffset += width;
383 codePtr += width;
384 }
385 }
386
Ben Cheng8b258bf2009-06-24 17:27:07 -0700387 /* Convert # of half-word to bytes */
388 methodStats->compiledDalvikSize += traceSize * 2;
389
Ben Chengba4fc8b2009-06-01 13:00:29 -0700390 /*
391 * Now scan basic blocks containing real code to connect the
392 * taken/fallthrough links. Also create chaining cells for code not included
393 * in the trace.
394 */
395 for (curBB = startBB; curBB; curBB = curBB->next) {
396 MIR *lastInsn = curBB->lastMIRInsn;
397 /* Hit a pseudo block - exit the search now */
398 if (lastInsn == NULL) {
399 break;
400 }
401 curOffset = lastInsn->offset;
402 unsigned int targetOffset = curOffset;
403 unsigned int fallThroughOffset = curOffset + lastInsn->width;
404 bool isInvoke = false;
405 const Method *callee = NULL;
406
407 findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset,
408 &targetOffset, &isInvoke, &callee);
409
410 /* Link the taken and fallthrough blocks */
411 BasicBlock *searchBB;
412
413 /* No backward branch in the trace - start searching the next BB */
414 for (searchBB = curBB->next; searchBB; searchBB = searchBB->next) {
415 if (targetOffset == searchBB->startOffset) {
416 curBB->taken = searchBB;
417 }
418 if (fallThroughOffset == searchBB->startOffset) {
419 curBB->fallThrough = searchBB;
420 }
421 }
422
Ben Cheng1efc9c52009-06-08 18:25:27 -0700423 int flags = dexGetInstrFlags(gDvm.instrFlags,
424 lastInsn->dalvikInsn.opCode);
425
426 /*
427 * Some blocks are ended by non-control-flow-change instructions,
428 * currently only due to trace length constraint. In this case we need
429 * to generate an explicit branch at the end of the block to jump to
430 * the chaining cell.
Ben Cheng17f15ce2009-07-27 16:21:52 -0700431 *
432 * NOTE: INVOKE_DIRECT_EMPTY is actually not an invoke but a nop
Ben Cheng1efc9c52009-06-08 18:25:27 -0700433 */
434 curBB->needFallThroughBranch =
Ben Cheng17f15ce2009-07-27 16:21:52 -0700435 ((flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
436 kInstrInvoke)) == 0) ||
437 (lastInsn->dalvikInsn.opCode == OP_INVOKE_DIRECT_EMPTY);
438
Ben Cheng1efc9c52009-06-08 18:25:27 -0700439
Ben Chengba4fc8b2009-06-01 13:00:29 -0700440 /* Target block not included in the trace */
Ben Cheng38329f52009-07-07 14:19:20 -0700441 if (curBB->taken == NULL &&
442 (isInvoke || (targetOffset != curOffset))) {
443 BasicBlock *newBB;
Ben Cheng1efc9c52009-06-08 18:25:27 -0700444 if (isInvoke) {
Ben Cheng38329f52009-07-07 14:19:20 -0700445 /* Monomorphic callee */
446 if (callee) {
447 newBB = dvmCompilerNewBB(CHAINING_CELL_INVOKE_SINGLETON);
448 newBB->startOffset = 0;
449 newBB->containingMethod = callee;
450 /* Will resolve at runtime */
451 } else {
452 newBB = dvmCompilerNewBB(CHAINING_CELL_INVOKE_PREDICTED);
453 newBB->startOffset = 0;
454 }
Ben Cheng1efc9c52009-06-08 18:25:27 -0700455 /* For unconditional branches, request a hot chaining cell */
456 } else {
Jeff Hao97319a82009-08-12 16:57:15 -0700457#if !defined(WITH_SELF_VERIFICATION)
Ben Cheng38329f52009-07-07 14:19:20 -0700458 newBB = dvmCompilerNewBB(flags & kInstrUnconditional ?
Ben Cheng1efc9c52009-06-08 18:25:27 -0700459 CHAINING_CELL_HOT :
460 CHAINING_CELL_NORMAL);
Ben Cheng38329f52009-07-07 14:19:20 -0700461 newBB->startOffset = targetOffset;
Jeff Hao97319a82009-08-12 16:57:15 -0700462#else
463 /* Handle branches that branch back into the block */
464 if (targetOffset >= curBB->firstMIRInsn->offset &&
465 targetOffset <= curBB->lastMIRInsn->offset) {
466 newBB = dvmCompilerNewBB(CHAINING_CELL_BACKWARD_BRANCH);
467 } else {
468 newBB = dvmCompilerNewBB(flags & kInstrUnconditional ?
469 CHAINING_CELL_HOT :
470 CHAINING_CELL_NORMAL);
471 }
472 newBB->startOffset = targetOffset;
473#endif
Ben Cheng1efc9c52009-06-08 18:25:27 -0700474 }
Ben Cheng38329f52009-07-07 14:19:20 -0700475 newBB->id = numBlocks++;
476 curBB->taken = newBB;
477 lastBB->next = newBB;
478 lastBB = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700479 }
480
481 /* Fallthrough block not included in the trace */
482 if (!isUnconditionalBranch(lastInsn) && curBB->fallThrough == NULL) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700483 /*
484 * If the chaining cell is after an invoke or
485 * instruction that cannot change the control flow, request a hot
486 * chaining cell.
487 */
488 if (isInvoke || curBB->needFallThroughBranch) {
489 lastBB->next = dvmCompilerNewBB(CHAINING_CELL_HOT);
490 } else {
491 lastBB->next = dvmCompilerNewBB(CHAINING_CELL_NORMAL);
492 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700493 lastBB = lastBB->next;
494 lastBB->id = numBlocks++;
495 lastBB->startOffset = fallThroughOffset;
496 curBB->fallThrough = lastBB;
497 }
498 }
499
500 /* Now create a special block to host PC reconstruction code */
501 lastBB->next = dvmCompilerNewBB(PC_RECONSTRUCTION);
502 lastBB = lastBB->next;
503 lastBB->id = numBlocks++;
504
505 /* And one final block that publishes the PC and raise the exception */
506 lastBB->next = dvmCompilerNewBB(EXCEPTION_HANDLING);
507 lastBB = lastBB->next;
508 lastBB->id = numBlocks++;
509
510 if (cUnit.printMe) {
511 LOGD("TRACEINFO (%d): 0x%08x %s%s 0x%x %d of %d, %d blocks",
Ben Chenge9695e52009-06-16 16:11:47 -0700512 compilationId,
Ben Chengba4fc8b2009-06-01 13:00:29 -0700513 (intptr_t) desc->method->insns,
514 desc->method->clazz->descriptor,
515 desc->method->name,
516 desc->trace[0].frag.startOffset,
517 traceSize,
518 dexCode->insnsSize,
519 numBlocks);
520 }
521
522 BasicBlock **blockList;
523
524 cUnit.method = desc->method;
525 cUnit.traceDesc = desc;
526 cUnit.numBlocks = numBlocks;
527 dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
528 blockList = cUnit.blockList =
529 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
530
531 int i;
532
533 for (i = 0, curBB = startBB; i < numBlocks; i++) {
534 blockList[i] = curBB;
535 curBB = curBB->next;
536 }
537 /* Make sure all blocks are added to the cUnit */
538 assert(curBB == NULL);
539
540 if (cUnit.printMe) {
541 dvmCompilerDumpCompilationUnit(&cUnit);
542 }
543
Bill Buzbee716f1202009-07-23 13:22:09 -0700544 /* Set the instruction set to use (NOTE: later components may change it) */
545 cUnit.instructionSet = dvmCompilerInstructionSet(&cUnit);
546
Ben Chengba4fc8b2009-06-01 13:00:29 -0700547 /* Convert MIR to LIR, etc. */
548 dvmCompilerMIR2LIR(&cUnit);
549
Ben Cheng1efc9c52009-06-08 18:25:27 -0700550 /* Convert LIR into machine code. */
Bill Buzbee716f1202009-07-23 13:22:09 -0700551 dvmCompilerAssembleLIR(&cUnit, info);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700552
553 if (cUnit.printMe) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700554 if (cUnit.halveInstCount) {
555 LOGD("Assembler aborted");
556 } else {
557 dvmCompilerCodegenDump(&cUnit);
558 }
559 LOGD("End %s%s, %d Dalvik instructions",
560 desc->method->clazz->descriptor, desc->method->name,
561 cUnit.numInsts);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700562 }
563
564 /* Reset the compiler resource pool */
565 dvmCompilerArenaReset();
566
Ben Chenge9695e52009-06-16 16:11:47 -0700567 /* Free the bit vector tracking null-checked registers */
568 dvmFreeBitVector(cUnit.registerScoreboard.nullCheckedRegs);
569
Ben Cheng1efc9c52009-06-08 18:25:27 -0700570 if (!cUnit.halveInstCount) {
Bill Buzbee716f1202009-07-23 13:22:09 -0700571 /* Success */
Ben Cheng8b258bf2009-06-24 17:27:07 -0700572 methodStats->nativeSize += cUnit.totalSize;
Bill Buzbee716f1202009-07-23 13:22:09 -0700573 return info->codeAddress != NULL;
Ben Cheng1efc9c52009-06-08 18:25:27 -0700574
575 /* Halve the instruction count and retry again */
576 } else {
Bill Buzbee716f1202009-07-23 13:22:09 -0700577 return dvmCompileTrace(desc, cUnit.numInsts / 2, info);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700578 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700579}
580
581/*
582 * Similar to dvmCompileTrace, but the entity processed here is the whole
583 * method.
584 *
585 * TODO: implementation will be revisited when the trace builder can provide
586 * whole-method traces.
587 */
Bill Buzbee716f1202009-07-23 13:22:09 -0700588bool dvmCompileMethod(const Method *method, JitTranslationInfo *info)
Ben Chengba4fc8b2009-06-01 13:00:29 -0700589{
590 const DexCode *dexCode = dvmGetMethodCode(method);
591 const u2 *codePtr = dexCode->insns;
592 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
593 int blockID = 0;
594 unsigned int curOffset = 0;
595
596 BasicBlock *firstBlock = dvmCompilerNewBB(DALVIK_BYTECODE);
597 firstBlock->id = blockID++;
598
599 /* Allocate the bit-vector to track the beginning of basic blocks */
600 BitVector *bbStartAddr = dvmAllocBitVector(dexCode->insnsSize+1, false);
601 dvmSetBit(bbStartAddr, 0);
602
603 /*
604 * Sequentially go through every instruction first and put them in a single
605 * basic block. Identify block boundaries at the mean time.
606 */
607 while (codePtr < codeEnd) {
608 MIR *insn = dvmCompilerNew(sizeof(MIR), false);
609 insn->offset = curOffset;
610 int width = parseInsn(codePtr, &insn->dalvikInsn, false);
611 bool isInvoke = false;
612 const Method *callee;
613 insn->width = width;
614
Ben Cheng8b258bf2009-06-24 17:27:07 -0700615 /* Terminate when the data section is seen */
616 if (width == 0)
617 break;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700618 dvmCompilerAppendMIR(firstBlock, insn);
619 /*
620 * Check whether this is a block ending instruction and whether it
621 * suggests the start of a new block
622 */
623 unsigned int target = curOffset;
624
625 /*
626 * If findBlockBoundary returns true, it means the current instruction
627 * is terminating the current block. If it is a branch, the target
628 * address will be recorded in target.
629 */
630 if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke,
631 &callee)) {
632 dvmSetBit(bbStartAddr, curOffset + width);
633 if (target != curOffset) {
634 dvmSetBit(bbStartAddr, target);
635 }
636 }
637
638 codePtr += width;
639 /* each bit represents 16-bit quantity */
640 curOffset += width;
641 }
642
643 /*
644 * The number of blocks will be equal to the number of bits set to 1 in the
645 * bit vector minus 1, because the bit representing the location after the
646 * last instruction is set to one.
647 */
648 int numBlocks = dvmCountSetBits(bbStartAddr);
649 if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) {
650 numBlocks--;
651 }
652
653 CompilationUnit cUnit;
654 BasicBlock **blockList;
655
656 memset(&cUnit, 0, sizeof(CompilationUnit));
657 cUnit.method = method;
658 blockList = cUnit.blockList =
659 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
660
661 /*
662 * Register the first block onto the list and start split it into block
663 * boundaries from there.
664 */
665 blockList[0] = firstBlock;
666 cUnit.numBlocks = 1;
667
668 int i;
669 for (i = 0; i < numBlocks; i++) {
670 MIR *insn;
671 BasicBlock *curBB = blockList[i];
672 curOffset = curBB->lastMIRInsn->offset;
673
674 for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) {
675 /* Found the beginning of a new block, see if it is created yet */
676 if (dvmIsBitSet(bbStartAddr, insn->offset)) {
677 int j;
678 for (j = 0; j < cUnit.numBlocks; j++) {
679 if (blockList[j]->firstMIRInsn->offset == insn->offset)
680 break;
681 }
682
683 /* Block not split yet - do it now */
684 if (j == cUnit.numBlocks) {
685 BasicBlock *newBB = dvmCompilerNewBB(DALVIK_BYTECODE);
686 newBB->id = blockID++;
687 newBB->firstMIRInsn = insn;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700688 newBB->startOffset = insn->offset;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700689 newBB->lastMIRInsn = curBB->lastMIRInsn;
690 curBB->lastMIRInsn = insn->prev;
691 insn->prev->next = NULL;
692 insn->prev = NULL;
693
694 /*
695 * If the insn is not an unconditional branch, set up the
696 * fallthrough link.
697 */
698 if (!isUnconditionalBranch(curBB->lastMIRInsn)) {
699 curBB->fallThrough = newBB;
700 }
701
702 /* enqueue the new block */
703 blockList[cUnit.numBlocks++] = newBB;
704 break;
705 }
706 }
707 }
708 }
709
710 if (numBlocks != cUnit.numBlocks) {
711 LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit.numBlocks);
712 dvmAbort();
713 }
714
715 dvmFreeBitVector(bbStartAddr);
716
717 /* Connect the basic blocks through the taken links */
718 for (i = 0; i < numBlocks; i++) {
719 BasicBlock *curBB = blockList[i];
720 MIR *insn = curBB->lastMIRInsn;
721 unsigned int target = insn->offset;
722 bool isInvoke;
723 const Method *callee;
724
725 findBlockBoundary(method, insn, target, &target, &isInvoke, &callee);
726
727 /* Found a block ended on a branch */
728 if (target != insn->offset) {
729 int j;
730 /* Forward branch */
731 if (target > insn->offset) {
732 j = i + 1;
733 } else {
734 /* Backward branch */
735 j = 0;
736 }
737 for (; j < numBlocks; j++) {
738 if (blockList[j]->firstMIRInsn->offset == target) {
739 curBB->taken = blockList[j];
740 break;
741 }
742 }
743
Ben Cheng8b258bf2009-06-24 17:27:07 -0700744 /* Don't create dummy block for the callee yet */
745 if (j == numBlocks && !isInvoke) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700746 LOGE("Target not found for insn %x: expect target %x\n",
747 curBB->lastMIRInsn->offset, target);
748 dvmAbort();
749 }
750 }
751 }
752
Bill Buzbee716f1202009-07-23 13:22:09 -0700753 /* Set the instruction set to use (NOTE: later components may change it) */
754 cUnit.instructionSet = dvmCompilerInstructionSet(&cUnit);
755
Ben Chengba4fc8b2009-06-01 13:00:29 -0700756 dvmCompilerMIR2LIR(&cUnit);
757
Bill Buzbee716f1202009-07-23 13:22:09 -0700758 dvmCompilerAssembleLIR(&cUnit, info);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700759
760 dvmCompilerDumpCompilationUnit(&cUnit);
761
762 dvmCompilerArenaReset();
763
Bill Buzbee716f1202009-07-23 13:22:09 -0700764 return info->codeAddress != NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700765}