blob: c71797557d28a7920cdc360990f349b86f4f1b0b [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.
431 */
432 curBB->needFallThroughBranch =
433 (flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
434 kInstrInvoke)) == 0;
435
Ben Chengba4fc8b2009-06-01 13:00:29 -0700436 /* Target block not included in the trace */
Ben Cheng38329f52009-07-07 14:19:20 -0700437 if (curBB->taken == NULL &&
438 (isInvoke || (targetOffset != curOffset))) {
439 BasicBlock *newBB;
Ben Cheng1efc9c52009-06-08 18:25:27 -0700440 if (isInvoke) {
Ben Cheng38329f52009-07-07 14:19:20 -0700441 /* Monomorphic callee */
442 if (callee) {
443 newBB = dvmCompilerNewBB(CHAINING_CELL_INVOKE_SINGLETON);
444 newBB->startOffset = 0;
445 newBB->containingMethod = callee;
446 /* Will resolve at runtime */
447 } else {
448 newBB = dvmCompilerNewBB(CHAINING_CELL_INVOKE_PREDICTED);
449 newBB->startOffset = 0;
450 }
Ben Cheng1efc9c52009-06-08 18:25:27 -0700451 /* For unconditional branches, request a hot chaining cell */
452 } else {
Ben Cheng38329f52009-07-07 14:19:20 -0700453 newBB = dvmCompilerNewBB(flags & kInstrUnconditional ?
Ben Cheng1efc9c52009-06-08 18:25:27 -0700454 CHAINING_CELL_HOT :
455 CHAINING_CELL_NORMAL);
Ben Cheng38329f52009-07-07 14:19:20 -0700456 newBB->startOffset = targetOffset;
Ben Cheng1efc9c52009-06-08 18:25:27 -0700457 }
Ben Cheng38329f52009-07-07 14:19:20 -0700458 newBB->id = numBlocks++;
459 curBB->taken = newBB;
460 lastBB->next = newBB;
461 lastBB = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700462 }
463
464 /* Fallthrough block not included in the trace */
465 if (!isUnconditionalBranch(lastInsn) && curBB->fallThrough == NULL) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700466 /*
467 * If the chaining cell is after an invoke or
468 * instruction that cannot change the control flow, request a hot
469 * chaining cell.
470 */
471 if (isInvoke || curBB->needFallThroughBranch) {
472 lastBB->next = dvmCompilerNewBB(CHAINING_CELL_HOT);
473 } else {
474 lastBB->next = dvmCompilerNewBB(CHAINING_CELL_NORMAL);
475 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700476 lastBB = lastBB->next;
477 lastBB->id = numBlocks++;
478 lastBB->startOffset = fallThroughOffset;
479 curBB->fallThrough = lastBB;
480 }
481 }
482
483 /* Now create a special block to host PC reconstruction code */
484 lastBB->next = dvmCompilerNewBB(PC_RECONSTRUCTION);
485 lastBB = lastBB->next;
486 lastBB->id = numBlocks++;
487
488 /* And one final block that publishes the PC and raise the exception */
489 lastBB->next = dvmCompilerNewBB(EXCEPTION_HANDLING);
490 lastBB = lastBB->next;
491 lastBB->id = numBlocks++;
492
493 if (cUnit.printMe) {
494 LOGD("TRACEINFO (%d): 0x%08x %s%s 0x%x %d of %d, %d blocks",
Ben Chenge9695e52009-06-16 16:11:47 -0700495 compilationId,
Ben Chengba4fc8b2009-06-01 13:00:29 -0700496 (intptr_t) desc->method->insns,
497 desc->method->clazz->descriptor,
498 desc->method->name,
499 desc->trace[0].frag.startOffset,
500 traceSize,
501 dexCode->insnsSize,
502 numBlocks);
503 }
504
505 BasicBlock **blockList;
506
507 cUnit.method = desc->method;
508 cUnit.traceDesc = desc;
509 cUnit.numBlocks = numBlocks;
510 dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
511 blockList = cUnit.blockList =
512 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
513
514 int i;
515
516 for (i = 0, curBB = startBB; i < numBlocks; i++) {
517 blockList[i] = curBB;
518 curBB = curBB->next;
519 }
520 /* Make sure all blocks are added to the cUnit */
521 assert(curBB == NULL);
522
523 if (cUnit.printMe) {
524 dvmCompilerDumpCompilationUnit(&cUnit);
525 }
526
Bill Buzbee716f1202009-07-23 13:22:09 -0700527 /* Set the instruction set to use (NOTE: later components may change it) */
528 cUnit.instructionSet = dvmCompilerInstructionSet(&cUnit);
529
Ben Chengba4fc8b2009-06-01 13:00:29 -0700530 /* Convert MIR to LIR, etc. */
531 dvmCompilerMIR2LIR(&cUnit);
532
Ben Cheng1efc9c52009-06-08 18:25:27 -0700533 /* Convert LIR into machine code. */
Bill Buzbee716f1202009-07-23 13:22:09 -0700534 dvmCompilerAssembleLIR(&cUnit, info);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700535
536 if (cUnit.printMe) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700537 if (cUnit.halveInstCount) {
538 LOGD("Assembler aborted");
539 } else {
540 dvmCompilerCodegenDump(&cUnit);
541 }
542 LOGD("End %s%s, %d Dalvik instructions",
543 desc->method->clazz->descriptor, desc->method->name,
544 cUnit.numInsts);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700545 }
546
547 /* Reset the compiler resource pool */
548 dvmCompilerArenaReset();
549
Ben Chenge9695e52009-06-16 16:11:47 -0700550 /* Free the bit vector tracking null-checked registers */
551 dvmFreeBitVector(cUnit.registerScoreboard.nullCheckedRegs);
552
Ben Cheng1efc9c52009-06-08 18:25:27 -0700553 if (!cUnit.halveInstCount) {
Bill Buzbee716f1202009-07-23 13:22:09 -0700554 /* Success */
Ben Cheng8b258bf2009-06-24 17:27:07 -0700555 methodStats->nativeSize += cUnit.totalSize;
Bill Buzbee716f1202009-07-23 13:22:09 -0700556 return info->codeAddress != NULL;
Ben Cheng1efc9c52009-06-08 18:25:27 -0700557
558 /* Halve the instruction count and retry again */
559 } else {
Bill Buzbee716f1202009-07-23 13:22:09 -0700560 return dvmCompileTrace(desc, cUnit.numInsts / 2, info);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700561 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700562}
563
564/*
565 * Similar to dvmCompileTrace, but the entity processed here is the whole
566 * method.
567 *
568 * TODO: implementation will be revisited when the trace builder can provide
569 * whole-method traces.
570 */
Bill Buzbee716f1202009-07-23 13:22:09 -0700571bool dvmCompileMethod(const Method *method, JitTranslationInfo *info)
Ben Chengba4fc8b2009-06-01 13:00:29 -0700572{
573 const DexCode *dexCode = dvmGetMethodCode(method);
574 const u2 *codePtr = dexCode->insns;
575 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
576 int blockID = 0;
577 unsigned int curOffset = 0;
578
579 BasicBlock *firstBlock = dvmCompilerNewBB(DALVIK_BYTECODE);
580 firstBlock->id = blockID++;
581
582 /* Allocate the bit-vector to track the beginning of basic blocks */
583 BitVector *bbStartAddr = dvmAllocBitVector(dexCode->insnsSize+1, false);
584 dvmSetBit(bbStartAddr, 0);
585
586 /*
587 * Sequentially go through every instruction first and put them in a single
588 * basic block. Identify block boundaries at the mean time.
589 */
590 while (codePtr < codeEnd) {
591 MIR *insn = dvmCompilerNew(sizeof(MIR), false);
592 insn->offset = curOffset;
593 int width = parseInsn(codePtr, &insn->dalvikInsn, false);
594 bool isInvoke = false;
595 const Method *callee;
596 insn->width = width;
597
Ben Cheng8b258bf2009-06-24 17:27:07 -0700598 /* Terminate when the data section is seen */
599 if (width == 0)
600 break;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700601 dvmCompilerAppendMIR(firstBlock, insn);
602 /*
603 * Check whether this is a block ending instruction and whether it
604 * suggests the start of a new block
605 */
606 unsigned int target = curOffset;
607
608 /*
609 * If findBlockBoundary returns true, it means the current instruction
610 * is terminating the current block. If it is a branch, the target
611 * address will be recorded in target.
612 */
613 if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke,
614 &callee)) {
615 dvmSetBit(bbStartAddr, curOffset + width);
616 if (target != curOffset) {
617 dvmSetBit(bbStartAddr, target);
618 }
619 }
620
621 codePtr += width;
622 /* each bit represents 16-bit quantity */
623 curOffset += width;
624 }
625
626 /*
627 * The number of blocks will be equal to the number of bits set to 1 in the
628 * bit vector minus 1, because the bit representing the location after the
629 * last instruction is set to one.
630 */
631 int numBlocks = dvmCountSetBits(bbStartAddr);
632 if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) {
633 numBlocks--;
634 }
635
636 CompilationUnit cUnit;
637 BasicBlock **blockList;
638
639 memset(&cUnit, 0, sizeof(CompilationUnit));
640 cUnit.method = method;
641 blockList = cUnit.blockList =
642 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
643
644 /*
645 * Register the first block onto the list and start split it into block
646 * boundaries from there.
647 */
648 blockList[0] = firstBlock;
649 cUnit.numBlocks = 1;
650
651 int i;
652 for (i = 0; i < numBlocks; i++) {
653 MIR *insn;
654 BasicBlock *curBB = blockList[i];
655 curOffset = curBB->lastMIRInsn->offset;
656
657 for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) {
658 /* Found the beginning of a new block, see if it is created yet */
659 if (dvmIsBitSet(bbStartAddr, insn->offset)) {
660 int j;
661 for (j = 0; j < cUnit.numBlocks; j++) {
662 if (blockList[j]->firstMIRInsn->offset == insn->offset)
663 break;
664 }
665
666 /* Block not split yet - do it now */
667 if (j == cUnit.numBlocks) {
668 BasicBlock *newBB = dvmCompilerNewBB(DALVIK_BYTECODE);
669 newBB->id = blockID++;
670 newBB->firstMIRInsn = insn;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700671 newBB->startOffset = insn->offset;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700672 newBB->lastMIRInsn = curBB->lastMIRInsn;
673 curBB->lastMIRInsn = insn->prev;
674 insn->prev->next = NULL;
675 insn->prev = NULL;
676
677 /*
678 * If the insn is not an unconditional branch, set up the
679 * fallthrough link.
680 */
681 if (!isUnconditionalBranch(curBB->lastMIRInsn)) {
682 curBB->fallThrough = newBB;
683 }
684
685 /* enqueue the new block */
686 blockList[cUnit.numBlocks++] = newBB;
687 break;
688 }
689 }
690 }
691 }
692
693 if (numBlocks != cUnit.numBlocks) {
694 LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit.numBlocks);
695 dvmAbort();
696 }
697
698 dvmFreeBitVector(bbStartAddr);
699
700 /* Connect the basic blocks through the taken links */
701 for (i = 0; i < numBlocks; i++) {
702 BasicBlock *curBB = blockList[i];
703 MIR *insn = curBB->lastMIRInsn;
704 unsigned int target = insn->offset;
705 bool isInvoke;
706 const Method *callee;
707
708 findBlockBoundary(method, insn, target, &target, &isInvoke, &callee);
709
710 /* Found a block ended on a branch */
711 if (target != insn->offset) {
712 int j;
713 /* Forward branch */
714 if (target > insn->offset) {
715 j = i + 1;
716 } else {
717 /* Backward branch */
718 j = 0;
719 }
720 for (; j < numBlocks; j++) {
721 if (blockList[j]->firstMIRInsn->offset == target) {
722 curBB->taken = blockList[j];
723 break;
724 }
725 }
726
Ben Cheng8b258bf2009-06-24 17:27:07 -0700727 /* Don't create dummy block for the callee yet */
728 if (j == numBlocks && !isInvoke) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700729 LOGE("Target not found for insn %x: expect target %x\n",
730 curBB->lastMIRInsn->offset, target);
731 dvmAbort();
732 }
733 }
734 }
735
Bill Buzbee716f1202009-07-23 13:22:09 -0700736 /* Set the instruction set to use (NOTE: later components may change it) */
737 cUnit.instructionSet = dvmCompilerInstructionSet(&cUnit);
738
Ben Chengba4fc8b2009-06-01 13:00:29 -0700739 dvmCompilerMIR2LIR(&cUnit);
740
Bill Buzbee716f1202009-07-23 13:22:09 -0700741 dvmCompilerAssembleLIR(&cUnit, info);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700742
743 dvmCompilerDumpCompilationUnit(&cUnit);
744
745 dvmCompilerArenaReset();
746
Bill Buzbee716f1202009-07-23 13:22:09 -0700747 return info->codeAddress != NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700748}