blob: 3c1e837baea348bdf645bbe0dc9e25da75441c5a [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"
Ben Chengba4fc8b2009-06-01 13:00:29 -070019#include "interp/Jit.h"
20#include "CompilerInternals.h"
Ben Cheng7a2697d2010-06-07 13:44:23 -070021#include "Dataflow.h"
Ben Chengba4fc8b2009-06-01 13:00:29 -070022
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 {
Dan Bornstein44a38f42010-11-10 17:34:32 -080037 insnWidth = gDvm.instrInfo.widths[opcode];
Ben Chengba4fc8b2009-06-01 13:00:29 -070038 if (insnWidth < 0) {
39 insnWidth = -insnWidth;
40 }
41 }
42
Dan Bornstein44a38f42010-11-10 17:34:32 -080043 dexDecodeInstruction(&gDvm.instrInfo, codePtr, decInsn);
Ben Chengba4fc8b2009-06-01 13:00:29 -070044 if (printMe) {
Ben Cheng7a2697d2010-06-07 13:44:23 -070045 char *decodedString = dvmCompilerGetDalvikDisassembly(decInsn, NULL);
Ben Chengccd6c012009-10-15 14:52:45 -070046 LOGD("%p: %#06x %s\n", codePtr, opcode, decodedString);
Ben Chengba4fc8b2009-06-01 13:00:29 -070047 }
48 return insnWidth;
49}
50
Ben Cheng9c147b82009-10-07 16:41:46 -070051#define UNKNOWN_TARGET 0xffffffff
52
Ben Chengba4fc8b2009-06-01 13:00:29 -070053/*
54 * Identify block-ending instructions and collect supplemental information
55 * regarding the following instructions.
56 */
57static 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:
Ben Cheng9c147b82009-10-07 16:41:46 -070069 *target = UNKNOWN_TARGET;
70 break;
Ben Chengba4fc8b2009-06-01 13:00:29 -070071 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
Ben Cheng8b258bf2009-06-24 17:27:07 -070086 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -070087 *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
Ben Cheng8b258bf2009-06-24 17:27:07 -070098 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -070099 *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
Ben Cheng8b258bf2009-06-24 17:27:07 -0700110 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700111 *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];
Ben Cheng8b258bf2009-06-24 17:27:07 -0700121 if (calleeMethod && !dvmIsNativeMethod(calleeMethod)) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700122 *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;
Ben Cheng9c147b82009-10-07 16:41:46 -0700154 }
155 return true;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700156}
157
Bill Buzbee324b3ac2009-12-04 13:17:36 -0800158static 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
Ben Chengba4fc8b2009-06-01 13:00:29 -0700170/*
Bill Buzbee324b3ac2009-12-04 13:17:36 -0800171 * Identify unconditional branch instructions
Ben Chengba4fc8b2009-06-01 13:00:29 -0700172 */
173static 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:
Ben Chengba4fc8b2009-06-01 13:00:29 -0700180 return true;
181 default:
Bill Buzbee324b3ac2009-12-04 13:17:36 -0800182 return isGoto(insn);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700183 }
184}
185
186/*
Ben Cheng8b258bf2009-06-24 17:27:07 -0700187 * dvmHashTableLookup() callback
188 */
189static int compareMethod(const CompilerMethodStats *m1,
190 const CompilerMethodStats *m2)
191{
192 return (int) m1->method - (int) m2->method;
193}
194
195/*
Ben Cheng7a2697d2010-06-07 13:44:23 -0700196 * 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 */
205static int analyzeInlineTarget(DecodedInstruction *dalvikInsn, int attributes,
206 int offset)
207{
Dan Bornstein44a38f42010-11-10 17:34:32 -0800208 int flags = dexGetInstrFlags(gDvm.instrInfo.flags, dalvikInsn->opCode);
Ben Cheng34dc7962010-08-26 14:56:31 -0700209 int dalvikOpCode = dalvikInsn->opCode;
Ben Cheng7a2697d2010-06-07 13:44:23 -0700210
211 if ((flags & kInstrInvoke) &&
Ben Cheng34dc7962010-08-26 14:56:31 -0700212 (dalvikOpCode != OP_INVOKE_DIRECT_EMPTY)) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700213 attributes &= ~METHOD_IS_LEAF;
214 }
215
216 if (!(flags & kInstrCanReturn)) {
Ben Cheng34dc7962010-08-26 14:56:31 -0700217 if (!(dvmCompilerDataFlowAttributes[dalvikOpCode] &
Ben Cheng7a2697d2010-06-07 13:44:23 -0700218 DF_IS_GETTER)) {
219 attributes &= ~METHOD_IS_GETTER;
220 }
Ben Cheng34dc7962010-08-26 14:56:31 -0700221 if (!(dvmCompilerDataFlowAttributes[dalvikOpCode] &
Ben Cheng7a2697d2010-06-07 13:44:23 -0700222 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) {
Ben Cheng34dc7962010-08-26 14:56:31 -0700233 if (dalvikOpCode == OP_RETURN_VOID) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700234 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
Ben Cheng34dc7962010-08-26 14:56:31 -0700245 if (offset == 0 && dalvikOpCode == OP_RETURN_VOID) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700246 attributes |= METHOD_IS_EMPTY;
247 }
248
Ben Cheng34dc7962010-08-26 14:56:31 -0700249 /*
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
Ben Cheng7a2697d2010-06-07 13:44:23 -0700258 return attributes;
259}
260
261/*
Ben Cheng8b258bf2009-06-24 17:27:07 -0700262 * 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
Ben Cheng7a2697d2010-06-07 13:44:23 -0700264 * ratios. If isCallee is true, also analyze each instruction in more details
265 * to see if it is suitable for inlining.
Ben Cheng8b258bf2009-06-24 17:27:07 -0700266 */
Ben Cheng7a2697d2010-06-07 13:44:23 -0700267CompilerMethodStats *dvmCompilerAnalyzeMethodBody(const Method *method,
268 bool isCallee)
Ben Cheng8b258bf2009-06-24 17:27:07 -0700269{
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
Ben Cheng7a2697d2010-06-07 13:44:23 -0700286 /* 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);
Ben Cheng8b258bf2009-06-24 17:27:07 -0700296 }
297
Ben Cheng7a2697d2010-06-07 13:44:23 -0700298 /* 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;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700301
Ben Cheng7a2697d2010-06-07 13:44:23 -0700302 /*
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 }
Ben Cheng8b258bf2009-06-24 17:27:07 -0700320
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
Ben Cheng7a2697d2010-06-07 13:44:23 -0700330 if (isCallee) {
331 attributes = analyzeInlineTarget(&dalvikInsn, attributes, insnSize);
332 }
333
Ben Cheng8b258bf2009-06-24 17:27:07 -0700334 insnSize += width;
335 codePtr += width;
336 }
337
Ben Cheng7a2697d2010-06-07 13:44:23 -0700338 /*
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
Ben Cheng8b258bf2009-06-24 17:27:07 -0700347 realMethodEntry->dalvikSize = insnSize * 2;
Ben Cheng7a2697d2010-06-07 13:44:23 -0700348 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
Ben Cheng8b258bf2009-06-24 17:27:07 -0700373 return realMethodEntry;
374}
375
376/*
Ben Cheng33672452010-01-12 14:59:30 -0800377 * Crawl the stack of the thread that requesed compilation to see if any of the
378 * ancestors are on the blacklist.
379 */
Andy McFadden953a0ed2010-09-17 15:48:38 -0700380static bool filterMethodByCallGraph(Thread *thread, const char *curMethodName)
Ben Cheng33672452010-01-12 14:59:30 -0800381{
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/*
Ben Chengba4fc8b2009-06-01 13:00:29 -0700407 * 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 */
Bill Buzbee716f1202009-07-23 13:22:09 -0700411bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts,
Ben Cheng4a419582010-08-04 13:23:09 -0700412 JitTranslationInfo *info, jmp_buf *bailPtr,
413 int optHints)
Ben Chengba4fc8b2009-06-01 13:00:29 -0700414{
415 const DexCode *dexCode = dvmGetMethodCode(desc->method);
416 const JitTraceRun* currRun = &desc->trace[0];
Ben Chengba4fc8b2009-06-01 13:00:29 -0700417 unsigned int curOffset = currRun->frag.startOffset;
418 unsigned int numInsts = currRun->frag.numInsts;
419 const u2 *codePtr = dexCode->insns + curOffset;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700420 int traceSize = 0; // # of half-words
Ben Chengba4fc8b2009-06-01 13:00:29 -0700421 const u2 *startCodePtr = codePtr;
422 BasicBlock *startBB, *curBB, *lastBB;
423 int numBlocks = 0;
424 static int compilationId;
425 CompilationUnit cUnit;
Ben Cheng1357e942010-02-10 17:21:39 -0800426#if defined(WITH_JIT_TUNING)
Ben Cheng8b258bf2009-06-24 17:27:07 -0700427 CompilerMethodStats *methodStats;
Ben Cheng1357e942010-02-10 17:21:39 -0800428#endif
Ben Chengba4fc8b2009-06-01 13:00:29 -0700429
Bill Buzbee964a7b02010-01-28 12:54:19 -0800430 /* If we've already compiled this trace, just return success */
jeffhao9e45c0b2010-02-03 10:24:05 -0800431 if (dvmJitGetCodeAddr(startCodePtr) && !info->discardResult) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700432 /*
433 * Make sure the codeAddress is NULL so that it won't clobber the
434 * existing entry.
435 */
436 info->codeAddress = NULL;
Bill Buzbee964a7b02010-01-28 12:54:19 -0800437 return true;
438 }
439
Ben Chenge9695e52009-06-16 16:11:47 -0700440 compilationId++;
Ben Cheng8b258bf2009-06-24 17:27:07 -0700441 memset(&cUnit, 0, sizeof(CompilationUnit));
442
Ben Cheng1357e942010-02-10 17:21:39 -0800443#if defined(WITH_JIT_TUNING)
Ben Cheng8b258bf2009-06-24 17:27:07 -0700444 /* Locate the entry to store compilation statistics for this method */
Ben Cheng7a2697d2010-06-07 13:44:23 -0700445 methodStats = dvmCompilerAnalyzeMethodBody(desc->method, false);
Ben Cheng1357e942010-02-10 17:21:39 -0800446#endif
Ben Chenge9695e52009-06-16 16:11:47 -0700447
Bill Buzbeefc519dc2010-03-06 23:30:57 -0800448 /* Set the recover buffer pointer */
449 cUnit.bailPtr = bailPtr;
450
Ben Chengba4fc8b2009-06-01 13:00:29 -0700451 /* Initialize the printMe flag */
452 cUnit.printMe = gDvmJit.printMe;
453
Bill Buzbee6e963e12009-06-17 16:56:19 -0700454 /* Initialize the profile flag */
455 cUnit.executionCount = gDvmJit.profile;
456
Ben Cheng7a2697d2010-06-07 13:44:23 -0700457 /* Setup the method */
458 cUnit.method = desc->method;
459
460 /* Initialize the PC reconstruction list */
461 dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
462
Ben Chengba4fc8b2009-06-01 13:00:29 -0700463 /* 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;
Ben Cheng33672452010-01-12 14:59:30 -0800501
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 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700511 }
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
Ben Cheng4238ec22009-08-24 16:32:22 -0700536 /* Allocate the entry block */
Ben Cheng7a2697d2010-06-07 13:44:23 -0700537 lastBB = startBB = curBB = dvmCompilerNewBB(kTraceEntryBlock);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700538 curBB->startOffset = curOffset;
539 curBB->id = numBlocks++;
540
Bill Buzbee1465db52009-09-23 17:17:35 -0700541 curBB = dvmCompilerNewBB(kDalvikByteCode);
Ben Cheng4238ec22009-08-24 16:32:22 -0700542 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
Ben Chengba4fc8b2009-06-01 13:00:29 -0700550 if (cUnit.printMe) {
551 LOGD("--------\nCompiler: Building trace for %s, offset 0x%x\n",
552 desc->method->name, curOffset);
553 }
554
Ben Cheng1efc9c52009-06-08 18:25:27 -0700555 /*
556 * Analyze the trace descriptor and include up to the maximal number
557 * of Dalvik instructions into the IR.
558 */
559 while (1) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700560 MIR *insn;
561 int width;
Ben Cheng4238ec22009-08-24 16:32:22 -0700562 insn = dvmCompilerNew(sizeof(MIR), true);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700563 insn->offset = curOffset;
564 width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe);
Ben Cheng8b258bf2009-06-24 17:27:07 -0700565
566 /* The trace should never incude instruction data */
567 assert(width);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700568 insn->width = width;
569 traceSize += width;
570 dvmCompilerAppendMIR(curBB, insn);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700571 cUnit.numInsts++;
Ben Cheng7a2697d2010-06-07 13:44:23 -0700572
Dan Bornstein44a38f42010-11-10 17:34:32 -0800573 int flags =
574 dexGetInstrFlags(gDvm.instrInfo.flags, insn->dalvikInsn.opCode);
Ben Cheng7a2697d2010-06-07 13:44:23 -0700575
576 if ((flags & kInstrInvoke) &&
577 (insn->dalvikInsn.opCode != OP_INVOKE_DIRECT_EMPTY)) {
578 assert(numInsts == 1);
579 CallsiteInfo *callsiteInfo =
580 dvmCompilerNew(sizeof(CallsiteInfo), true);
581 callsiteInfo->clazz = currRun[1].meta;
582 callsiteInfo->method = currRun[2].meta;
583 insn->meta.callsiteInfo = callsiteInfo;
584 }
585
Ben Cheng1efc9c52009-06-08 18:25:27 -0700586 /* Instruction limit reached - terminate the trace here */
587 if (cUnit.numInsts >= numMaxInsts) {
588 break;
589 }
590 if (--numInsts == 0) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700591 if (currRun->frag.runEnd) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700592 break;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700593 } else {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700594 /* Advance to the next trace description (ie non-meta info) */
595 do {
596 currRun++;
597 } while (!currRun->frag.isCode);
598
599 /* Dummy end-of-run marker seen */
600 if (currRun->frag.numInsts == 0) {
601 break;
602 }
603
Bill Buzbee1465db52009-09-23 17:17:35 -0700604 curBB = dvmCompilerNewBB(kDalvikByteCode);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700605 lastBB->next = curBB;
606 lastBB = curBB;
607 curBB->id = numBlocks++;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700608 curOffset = currRun->frag.startOffset;
609 numInsts = currRun->frag.numInsts;
610 curBB->startOffset = curOffset;
611 codePtr = dexCode->insns + curOffset;
612 }
613 } else {
614 curOffset += width;
615 codePtr += width;
616 }
617 }
618
Ben Cheng1357e942010-02-10 17:21:39 -0800619#if defined(WITH_JIT_TUNING)
Ben Cheng8b258bf2009-06-24 17:27:07 -0700620 /* Convert # of half-word to bytes */
621 methodStats->compiledDalvikSize += traceSize * 2;
Ben Cheng1357e942010-02-10 17:21:39 -0800622#endif
Ben Cheng8b258bf2009-06-24 17:27:07 -0700623
Ben Chengba4fc8b2009-06-01 13:00:29 -0700624 /*
625 * Now scan basic blocks containing real code to connect the
626 * taken/fallthrough links. Also create chaining cells for code not included
627 * in the trace.
628 */
629 for (curBB = startBB; curBB; curBB = curBB->next) {
630 MIR *lastInsn = curBB->lastMIRInsn;
Ben Cheng4238ec22009-08-24 16:32:22 -0700631 /* Skip empty blocks */
Ben Chengba4fc8b2009-06-01 13:00:29 -0700632 if (lastInsn == NULL) {
Ben Cheng4238ec22009-08-24 16:32:22 -0700633 continue;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700634 }
635 curOffset = lastInsn->offset;
636 unsigned int targetOffset = curOffset;
637 unsigned int fallThroughOffset = curOffset + lastInsn->width;
638 bool isInvoke = false;
639 const Method *callee = NULL;
640
641 findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset,
642 &targetOffset, &isInvoke, &callee);
643
644 /* Link the taken and fallthrough blocks */
645 BasicBlock *searchBB;
646
Dan Bornstein44a38f42010-11-10 17:34:32 -0800647 int flags = dexGetInstrFlags(gDvm.instrInfo.flags,
Ben Cheng7a2697d2010-06-07 13:44:23 -0700648 lastInsn->dalvikInsn.opCode);
649
650 if (flags & kInstrInvoke) {
651 cUnit.hasInvoke = true;
652 }
653
Ben Chengba4fc8b2009-06-01 13:00:29 -0700654 /* No backward branch in the trace - start searching the next BB */
655 for (searchBB = curBB->next; searchBB; searchBB = searchBB->next) {
656 if (targetOffset == searchBB->startOffset) {
657 curBB->taken = searchBB;
658 }
659 if (fallThroughOffset == searchBB->startOffset) {
660 curBB->fallThrough = searchBB;
Ben Cheng7a2697d2010-06-07 13:44:23 -0700661
662 /*
663 * Fallthrough block of an invoke instruction needs to be
664 * aligned to 4-byte boundary (alignment instruction to be
665 * inserted later.
666 */
667 if (flags & kInstrInvoke) {
668 searchBB->isFallThroughFromInvoke = true;
669 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700670 }
671 }
672
Ben Cheng1efc9c52009-06-08 18:25:27 -0700673 /*
674 * Some blocks are ended by non-control-flow-change instructions,
675 * currently only due to trace length constraint. In this case we need
676 * to generate an explicit branch at the end of the block to jump to
677 * the chaining cell.
Ben Cheng17f15ce2009-07-27 16:21:52 -0700678 *
679 * NOTE: INVOKE_DIRECT_EMPTY is actually not an invoke but a nop
Ben Cheng1efc9c52009-06-08 18:25:27 -0700680 */
681 curBB->needFallThroughBranch =
Ben Cheng17f15ce2009-07-27 16:21:52 -0700682 ((flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
683 kInstrInvoke)) == 0) ||
684 (lastInsn->dalvikInsn.opCode == OP_INVOKE_DIRECT_EMPTY);
685
Ben Cheng4a419582010-08-04 13:23:09 -0700686 /* Only form a loop if JIT_OPT_NO_LOOP is not set */
Ben Cheng4238ec22009-08-24 16:32:22 -0700687 if (curBB->taken == NULL &&
688 curBB->fallThrough == NULL &&
689 flags == (kInstrCanBranch | kInstrCanContinue) &&
Ben Cheng4a419582010-08-04 13:23:09 -0700690 fallThroughOffset == startBB->startOffset &&
691 JIT_OPT_NO_LOOP != (optHints & JIT_OPT_NO_LOOP)) {
Ben Cheng0fd31e42009-09-03 14:40:16 -0700692 BasicBlock *loopBranch = curBB;
693 BasicBlock *exitBB;
694 BasicBlock *exitChainingCell;
Ben Cheng4238ec22009-08-24 16:32:22 -0700695
696 if (cUnit.printMe) {
697 LOGD("Natural loop detected!");
698 }
Ben Cheng7a2697d2010-06-07 13:44:23 -0700699 exitBB = dvmCompilerNewBB(kTraceExitBlock);
Ben Cheng0fd31e42009-09-03 14:40:16 -0700700 lastBB->next = exitBB;
701 lastBB = exitBB;
Ben Cheng4238ec22009-08-24 16:32:22 -0700702
Ben Cheng0fd31e42009-09-03 14:40:16 -0700703 exitBB->startOffset = targetOffset;
704 exitBB->id = numBlocks++;
705 exitBB->needFallThroughBranch = true;
Ben Cheng4238ec22009-08-24 16:32:22 -0700706
Ben Cheng0fd31e42009-09-03 14:40:16 -0700707 loopBranch->taken = exitBB;
Bill Buzbee9c4b7c82009-09-10 10:10:38 -0700708#if defined(WITH_SELF_VERIFICATION)
Ben Cheng0fd31e42009-09-03 14:40:16 -0700709 BasicBlock *backwardCell =
Bill Buzbee1465db52009-09-23 17:17:35 -0700710 dvmCompilerNewBB(kChainingCellBackwardBranch);
Ben Cheng0fd31e42009-09-03 14:40:16 -0700711 lastBB->next = backwardCell;
712 lastBB = backwardCell;
Ben Cheng4238ec22009-08-24 16:32:22 -0700713
Ben Cheng0fd31e42009-09-03 14:40:16 -0700714 backwardCell->startOffset = startBB->startOffset;
715 backwardCell->id = numBlocks++;
716 loopBranch->fallThrough = backwardCell;
Bill Buzbee9c4b7c82009-09-10 10:10:38 -0700717#elif defined(WITH_JIT_TUNING)
718 if (gDvmJit.profile) {
719 BasicBlock *backwardCell =
Bill Buzbee1465db52009-09-23 17:17:35 -0700720 dvmCompilerNewBB(kChainingCellBackwardBranch);
Bill Buzbee9c4b7c82009-09-10 10:10:38 -0700721 lastBB->next = backwardCell;
722 lastBB = backwardCell;
723
724 backwardCell->startOffset = startBB->startOffset;
725 backwardCell->id = numBlocks++;
726 loopBranch->fallThrough = backwardCell;
727 } else {
728 loopBranch->fallThrough = startBB->next;
729 }
730#else
731 loopBranch->fallThrough = startBB->next;
Ben Cheng0fd31e42009-09-03 14:40:16 -0700732#endif
733
734 /* Create the chaining cell as the fallthrough of the exit block */
Bill Buzbee1465db52009-09-23 17:17:35 -0700735 exitChainingCell = dvmCompilerNewBB(kChainingCellNormal);
Ben Cheng0fd31e42009-09-03 14:40:16 -0700736 lastBB->next = exitChainingCell;
737 lastBB = exitChainingCell;
738
739 exitChainingCell->startOffset = targetOffset;
740 exitChainingCell->id = numBlocks++;
741
742 exitBB->fallThrough = exitChainingCell;
743
Ben Cheng4238ec22009-08-24 16:32:22 -0700744 cUnit.hasLoop = true;
745 }
746
Ben Cheng6c10a972009-10-29 14:39:18 -0700747 if (lastInsn->dalvikInsn.opCode == OP_PACKED_SWITCH ||
748 lastInsn->dalvikInsn.opCode == OP_SPARSE_SWITCH) {
749 int i;
750 const u2 *switchData = desc->method->insns + lastInsn->offset +
751 lastInsn->dalvikInsn.vB;
752 int size = switchData[1];
753 int maxChains = MIN(size, MAX_CHAINED_SWITCH_CASES);
754
755 /*
756 * Generate the landing pad for cases whose ranks are higher than
757 * MAX_CHAINED_SWITCH_CASES. The code will re-enter the interpreter
758 * through the NoChain point.
759 */
760 if (maxChains != size) {
761 cUnit.switchOverflowPad =
762 desc->method->insns + lastInsn->offset;
763 }
764
765 s4 *targets = (s4 *) (switchData + 2 +
766 (lastInsn->dalvikInsn.opCode == OP_PACKED_SWITCH ?
767 2 : size * 2));
768
769 /* One chaining cell for the first MAX_CHAINED_SWITCH_CASES cases */
770 for (i = 0; i < maxChains; i++) {
771 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
772 lastBB->next = caseChain;
773 lastBB = caseChain;
774
775 caseChain->startOffset = lastInsn->offset + targets[i];
776 caseChain->id = numBlocks++;
777 }
778
779 /* One more chaining cell for the default case */
780 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
781 lastBB->next = caseChain;
782 lastBB = caseChain;
783
784 caseChain->startOffset = lastInsn->offset + lastInsn->width;
785 caseChain->id = numBlocks++;
Ben Cheng6d576092009-09-01 17:01:58 -0700786 /* Fallthrough block not included in the trace */
Ben Cheng6c10a972009-10-29 14:39:18 -0700787 } else if (!isUnconditionalBranch(lastInsn) &&
788 curBB->fallThrough == NULL) {
Ben Cheng6d576092009-09-01 17:01:58 -0700789 /*
790 * If the chaining cell is after an invoke or
791 * instruction that cannot change the control flow, request a hot
792 * chaining cell.
793 */
794 if (isInvoke || curBB->needFallThroughBranch) {
Bill Buzbee1465db52009-09-23 17:17:35 -0700795 lastBB->next = dvmCompilerNewBB(kChainingCellHot);
Ben Cheng6d576092009-09-01 17:01:58 -0700796 } else {
Bill Buzbee1465db52009-09-23 17:17:35 -0700797 lastBB->next = dvmCompilerNewBB(kChainingCellNormal);
Ben Cheng6d576092009-09-01 17:01:58 -0700798 }
799 lastBB = lastBB->next;
800 lastBB->id = numBlocks++;
801 lastBB->startOffset = fallThroughOffset;
802 curBB->fallThrough = lastBB;
803 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700804 /* Target block not included in the trace */
Ben Cheng38329f52009-07-07 14:19:20 -0700805 if (curBB->taken == NULL &&
Bill Buzbee324b3ac2009-12-04 13:17:36 -0800806 (isGoto(lastInsn) || isInvoke ||
807 (targetOffset != UNKNOWN_TARGET && targetOffset != curOffset))) {
Ben Cheng38329f52009-07-07 14:19:20 -0700808 BasicBlock *newBB;
Ben Cheng1efc9c52009-06-08 18:25:27 -0700809 if (isInvoke) {
Ben Cheng38329f52009-07-07 14:19:20 -0700810 /* Monomorphic callee */
811 if (callee) {
Bill Buzbee1465db52009-09-23 17:17:35 -0700812 newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton);
Ben Cheng38329f52009-07-07 14:19:20 -0700813 newBB->startOffset = 0;
814 newBB->containingMethod = callee;
815 /* Will resolve at runtime */
816 } else {
Bill Buzbee1465db52009-09-23 17:17:35 -0700817 newBB = dvmCompilerNewBB(kChainingCellInvokePredicted);
Ben Cheng38329f52009-07-07 14:19:20 -0700818 newBB->startOffset = 0;
819 }
Ben Cheng1efc9c52009-06-08 18:25:27 -0700820 /* For unconditional branches, request a hot chaining cell */
821 } else {
Jeff Hao97319a82009-08-12 16:57:15 -0700822#if !defined(WITH_SELF_VERIFICATION)
Dan Bornsteinc2b486f2010-11-12 16:07:16 -0800823 newBB = dvmCompilerNewBB(dexIsGoto(flags) ?
Bill Buzbee1465db52009-09-23 17:17:35 -0700824 kChainingCellHot :
825 kChainingCellNormal);
Ben Cheng38329f52009-07-07 14:19:20 -0700826 newBB->startOffset = targetOffset;
Jeff Hao97319a82009-08-12 16:57:15 -0700827#else
828 /* Handle branches that branch back into the block */
829 if (targetOffset >= curBB->firstMIRInsn->offset &&
830 targetOffset <= curBB->lastMIRInsn->offset) {
Bill Buzbee1465db52009-09-23 17:17:35 -0700831 newBB = dvmCompilerNewBB(kChainingCellBackwardBranch);
Jeff Hao97319a82009-08-12 16:57:15 -0700832 } else {
Dan Bornsteinc2b486f2010-11-12 16:07:16 -0800833 newBB = dvmCompilerNewBB(dexIsGoto(flags) ?
Bill Buzbee1465db52009-09-23 17:17:35 -0700834 kChainingCellHot :
835 kChainingCellNormal);
Jeff Hao97319a82009-08-12 16:57:15 -0700836 }
837 newBB->startOffset = targetOffset;
838#endif
Ben Cheng1efc9c52009-06-08 18:25:27 -0700839 }
Ben Cheng38329f52009-07-07 14:19:20 -0700840 newBB->id = numBlocks++;
841 curBB->taken = newBB;
842 lastBB->next = newBB;
843 lastBB = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700844 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700845 }
846
847 /* Now create a special block to host PC reconstruction code */
Bill Buzbee1465db52009-09-23 17:17:35 -0700848 lastBB->next = dvmCompilerNewBB(kPCReconstruction);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700849 lastBB = lastBB->next;
850 lastBB->id = numBlocks++;
851
852 /* And one final block that publishes the PC and raise the exception */
Bill Buzbee1465db52009-09-23 17:17:35 -0700853 lastBB->next = dvmCompilerNewBB(kExceptionHandling);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700854 lastBB = lastBB->next;
855 lastBB->id = numBlocks++;
856
857 if (cUnit.printMe) {
Elliott Hughescc6fac82010-07-02 13:38:44 -0700858 char* signature = dexProtoCopyMethodDescriptor(&desc->method->prototype);
859 LOGD("TRACEINFO (%d): 0x%08x %s%s.%s 0x%x %d of %d, %d blocks",
Ben Chenge9695e52009-06-16 16:11:47 -0700860 compilationId,
Ben Chengba4fc8b2009-06-01 13:00:29 -0700861 (intptr_t) desc->method->insns,
862 desc->method->clazz->descriptor,
863 desc->method->name,
Elliott Hughescc6fac82010-07-02 13:38:44 -0700864 signature,
Ben Chengba4fc8b2009-06-01 13:00:29 -0700865 desc->trace[0].frag.startOffset,
866 traceSize,
867 dexCode->insnsSize,
868 numBlocks);
Elliott Hughescc6fac82010-07-02 13:38:44 -0700869 free(signature);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700870 }
871
872 BasicBlock **blockList;
873
Ben Chengba4fc8b2009-06-01 13:00:29 -0700874 cUnit.traceDesc = desc;
875 cUnit.numBlocks = numBlocks;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700876 blockList = cUnit.blockList =
877 dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
878
879 int i;
880
881 for (i = 0, curBB = startBB; i < numBlocks; i++) {
882 blockList[i] = curBB;
883 curBB = curBB->next;
884 }
885 /* Make sure all blocks are added to the cUnit */
886 assert(curBB == NULL);
887
Ben Cheng7a2697d2010-06-07 13:44:23 -0700888 /* Set the instruction set to use (NOTE: later components may change it) */
889 cUnit.instructionSet = dvmCompilerInstructionSet();
890
891 /* Inline transformation @ the MIR level */
892 if (cUnit.hasInvoke && !(gDvmJit.disableOpt & (1 << kMethodInlining))) {
893 dvmCompilerInlineMIR(&cUnit);
894 }
895
Ben Cheng4238ec22009-08-24 16:32:22 -0700896 /* Preparation for SSA conversion */
897 dvmInitializeSSAConversion(&cUnit);
898
899 if (cUnit.hasLoop) {
Ben Cheng4a419582010-08-04 13:23:09 -0700900 /*
901 * Loop is not optimizable (for example lack of a single induction
902 * variable), punt and recompile the trace with loop optimization
903 * disabled.
904 */
905 bool loopOpt = dvmCompilerLoopOpt(&cUnit);
906 if (loopOpt == false) {
907 if (cUnit.printMe) {
908 LOGD("Loop is not optimizable - retry codegen");
909 }
910 /* Reset the compiler resource pool */
911 dvmCompilerArenaReset();
912 return dvmCompileTrace(desc, cUnit.numInsts, info, bailPtr,
913 optHints | JIT_OPT_NO_LOOP);
914 }
Ben Cheng4238ec22009-08-24 16:32:22 -0700915 }
916 else {
917 dvmCompilerNonLoopAnalysis(&cUnit);
918 }
919
Bill Buzbee1465db52009-09-23 17:17:35 -0700920 dvmCompilerInitializeRegAlloc(&cUnit); // Needs to happen after SSA naming
921
Ben Chengba4fc8b2009-06-01 13:00:29 -0700922 if (cUnit.printMe) {
923 dvmCompilerDumpCompilationUnit(&cUnit);
924 }
925
Bill Buzbee1465db52009-09-23 17:17:35 -0700926 /* Allocate Registers */
927 dvmCompilerRegAlloc(&cUnit);
928
Ben Chengba4fc8b2009-06-01 13:00:29 -0700929 /* Convert MIR to LIR, etc. */
930 dvmCompilerMIR2LIR(&cUnit);
931
buzbeebff121a2010-08-04 15:25:06 -0700932 /* Convert LIR into machine code. Loop for recoverable retries */
933 do {
934 dvmCompilerAssembleLIR(&cUnit, info);
935 cUnit.assemblerRetries++;
936 if (cUnit.printMe && cUnit.assemblerStatus != kSuccess)
937 LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries,
938 cUnit.assemblerStatus);
939 } while (cUnit.assemblerStatus == kRetryAll);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700940
941 if (cUnit.printMe) {
buzbeebff121a2010-08-04 15:25:06 -0700942 dvmCompilerCodegenDump(&cUnit);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700943 LOGD("End %s%s, %d Dalvik instructions",
944 desc->method->clazz->descriptor, desc->method->name,
945 cUnit.numInsts);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700946 }
947
948 /* Reset the compiler resource pool */
949 dvmCompilerArenaReset();
950
buzbeebff121a2010-08-04 15:25:06 -0700951 if (cUnit.assemblerStatus == kRetryHalve) {
952 /* Halve the instruction count and start from the top */
Ben Cheng4a419582010-08-04 13:23:09 -0700953 return dvmCompileTrace(desc, cUnit.numInsts / 2, info, bailPtr,
954 optHints);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700955 }
buzbeebff121a2010-08-04 15:25:06 -0700956
957 assert(cUnit.assemblerStatus == kSuccess);
958#if defined(WITH_JIT_TUNING)
959 methodStats->nativeSize += cUnit.totalSize;
960#endif
961 return info->codeAddress != NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700962}
963
964/*
Ben Cheng7a2697d2010-06-07 13:44:23 -0700965 * Since we are including instructions from possibly a cold method into the
966 * current trace, we need to make sure that all the associated information
967 * with the callee is properly initialized. If not, we punt on this inline
968 * target.
969 *
Ben Cheng34dc7962010-08-26 14:56:31 -0700970 * TODO: volatile instructions will be handled later.
Ben Cheng7a2697d2010-06-07 13:44:23 -0700971 */
972bool dvmCompilerCanIncludeThisInstruction(const Method *method,
973 const DecodedInstruction *insn)
974{
975 switch (insn->opCode) {
976 case OP_NEW_INSTANCE:
977 case OP_CHECK_CAST: {
978 ClassObject *classPtr = (void*)
979 (method->clazz->pDvmDex->pResClasses[insn->vB]);
980
981 /* Class hasn't been initialized yet */
982 if (classPtr == NULL) {
983 return false;
984 }
985 return true;
986 }
987 case OP_SGET_OBJECT:
988 case OP_SGET_BOOLEAN:
989 case OP_SGET_CHAR:
990 case OP_SGET_BYTE:
991 case OP_SGET_SHORT:
992 case OP_SGET:
993 case OP_SGET_WIDE:
994 case OP_SPUT_OBJECT:
995 case OP_SPUT_BOOLEAN:
996 case OP_SPUT_CHAR:
997 case OP_SPUT_BYTE:
998 case OP_SPUT_SHORT:
999 case OP_SPUT:
1000 case OP_SPUT_WIDE: {
1001 void *fieldPtr = (void*)
1002 (method->clazz->pDvmDex->pResFields[insn->vB]);
1003
1004 if (fieldPtr == NULL) {
1005 return false;
1006 }
1007 return true;
1008 }
1009 case OP_INVOKE_SUPER:
1010 case OP_INVOKE_SUPER_RANGE: {
1011 int mIndex = method->clazz->pDvmDex->
1012 pResMethods[insn->vB]->methodIndex;
1013 const Method *calleeMethod = method->clazz->super->vtable[mIndex];
1014 if (calleeMethod == NULL) {
1015 return false;
1016 }
1017 return true;
1018 }
1019 case OP_INVOKE_SUPER_QUICK:
1020 case OP_INVOKE_SUPER_QUICK_RANGE: {
1021 const Method *calleeMethod = method->clazz->super->vtable[insn->vB];
1022 if (calleeMethod == NULL) {
1023 return false;
1024 }
1025 return true;
1026 }
1027 case OP_INVOKE_STATIC:
1028 case OP_INVOKE_STATIC_RANGE:
1029 case OP_INVOKE_DIRECT:
1030 case OP_INVOKE_DIRECT_RANGE: {
1031 const Method *calleeMethod =
1032 method->clazz->pDvmDex->pResMethods[insn->vB];
1033 if (calleeMethod == NULL) {
1034 return false;
1035 }
1036 return true;
1037 }
1038 case OP_CONST_CLASS: {
1039 void *classPtr = (void*)
1040 (method->clazz->pDvmDex->pResClasses[insn->vB]);
1041
1042 if (classPtr == NULL) {
1043 return false;
1044 }
1045 return true;
1046 }
1047 case OP_CONST_STRING_JUMBO:
1048 case OP_CONST_STRING: {
1049 void *strPtr = (void*)
1050 (method->clazz->pDvmDex->pResStrings[insn->vB]);
1051
1052 if (strPtr == NULL) {
1053 return false;
1054 }
1055 return true;
1056 }
1057 default:
1058 return true;
1059 }
1060}
1061
1062/*
Ben Chengba4fc8b2009-06-01 13:00:29 -07001063 * Similar to dvmCompileTrace, but the entity processed here is the whole
1064 * method.
1065 *
1066 * TODO: implementation will be revisited when the trace builder can provide
1067 * whole-method traces.
1068 */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001069bool dvmCompileMethod(CompilationUnit *cUnit, const Method *method,
1070 JitTranslationInfo *info)
Ben Chengba4fc8b2009-06-01 13:00:29 -07001071{
1072 const DexCode *dexCode = dvmGetMethodCode(method);
1073 const u2 *codePtr = dexCode->insns;
1074 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
1075 int blockID = 0;
1076 unsigned int curOffset = 0;
1077
Ben Cheng7a2697d2010-06-07 13:44:23 -07001078 /* If we've already compiled this trace, just return success */
1079 if (dvmJitGetCodeAddr(codePtr) && !info->discardResult) {
1080 return true;
1081 }
1082
1083 /* Doing method-based compilation */
1084 cUnit->wholeMethod = true;
1085
Bill Buzbee1465db52009-09-23 17:17:35 -07001086 BasicBlock *firstBlock = dvmCompilerNewBB(kDalvikByteCode);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001087 firstBlock->id = blockID++;
1088
1089 /* Allocate the bit-vector to track the beginning of basic blocks */
Ben Cheng4238ec22009-08-24 16:32:22 -07001090 BitVector *bbStartAddr = dvmCompilerAllocBitVector(dexCode->insnsSize+1,
1091 false);
1092 dvmCompilerSetBit(bbStartAddr, 0);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001093
Ben Cheng7a2697d2010-06-07 13:44:23 -07001094 int numInvokeTargets = 0;
1095
Ben Chengba4fc8b2009-06-01 13:00:29 -07001096 /*
1097 * Sequentially go through every instruction first and put them in a single
1098 * basic block. Identify block boundaries at the mean time.
1099 */
1100 while (codePtr < codeEnd) {
Ben Cheng4238ec22009-08-24 16:32:22 -07001101 MIR *insn = dvmCompilerNew(sizeof(MIR), true);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001102 insn->offset = curOffset;
1103 int width = parseInsn(codePtr, &insn->dalvikInsn, false);
1104 bool isInvoke = false;
1105 const Method *callee;
1106 insn->width = width;
1107
Ben Cheng8b258bf2009-06-24 17:27:07 -07001108 /* Terminate when the data section is seen */
1109 if (width == 0)
1110 break;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001111
1112 if (!dvmCompilerCanIncludeThisInstruction(cUnit->method,
1113 &insn->dalvikInsn)) {
1114 return false;
1115 }
1116
Ben Chengba4fc8b2009-06-01 13:00:29 -07001117 dvmCompilerAppendMIR(firstBlock, insn);
1118 /*
1119 * Check whether this is a block ending instruction and whether it
1120 * suggests the start of a new block
1121 */
1122 unsigned int target = curOffset;
1123
1124 /*
1125 * If findBlockBoundary returns true, it means the current instruction
1126 * is terminating the current block. If it is a branch, the target
1127 * address will be recorded in target.
1128 */
1129 if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke,
1130 &callee)) {
Ben Cheng4238ec22009-08-24 16:32:22 -07001131 dvmCompilerSetBit(bbStartAddr, curOffset + width);
Ben Cheng7a2697d2010-06-07 13:44:23 -07001132 /* Each invoke needs a chaining cell block */
1133 if (isInvoke) {
1134 numInvokeTargets++;
1135 }
1136 /* A branch will end the current block */
1137 else if (target != curOffset && target != UNKNOWN_TARGET) {
Ben Cheng4238ec22009-08-24 16:32:22 -07001138 dvmCompilerSetBit(bbStartAddr, target);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001139 }
1140 }
1141
1142 codePtr += width;
1143 /* each bit represents 16-bit quantity */
1144 curOffset += width;
1145 }
1146
1147 /*
1148 * The number of blocks will be equal to the number of bits set to 1 in the
1149 * bit vector minus 1, because the bit representing the location after the
1150 * last instruction is set to one.
Ben Cheng7a2697d2010-06-07 13:44:23 -07001151 *
1152 * We also add additional blocks for invoke chaining and the number is
1153 * denoted by numInvokeTargets.
Ben Chengba4fc8b2009-06-01 13:00:29 -07001154 */
1155 int numBlocks = dvmCountSetBits(bbStartAddr);
1156 if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) {
1157 numBlocks--;
1158 }
1159
Ben Chengba4fc8b2009-06-01 13:00:29 -07001160 BasicBlock **blockList;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001161 blockList = cUnit->blockList =
1162 dvmCompilerNew(sizeof(BasicBlock *) * (numBlocks + numInvokeTargets),
1163 true);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001164
1165 /*
Ben Cheng7a2697d2010-06-07 13:44:23 -07001166 * Register the first block onto the list and start splitting it into
1167 * sub-blocks.
Ben Chengba4fc8b2009-06-01 13:00:29 -07001168 */
1169 blockList[0] = firstBlock;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001170 cUnit->numBlocks = 1;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001171
1172 int i;
1173 for (i = 0; i < numBlocks; i++) {
1174 MIR *insn;
1175 BasicBlock *curBB = blockList[i];
1176 curOffset = curBB->lastMIRInsn->offset;
1177
1178 for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) {
1179 /* Found the beginning of a new block, see if it is created yet */
1180 if (dvmIsBitSet(bbStartAddr, insn->offset)) {
1181 int j;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001182 for (j = 0; j < cUnit->numBlocks; j++) {
Ben Chengba4fc8b2009-06-01 13:00:29 -07001183 if (blockList[j]->firstMIRInsn->offset == insn->offset)
1184 break;
1185 }
1186
1187 /* Block not split yet - do it now */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001188 if (j == cUnit->numBlocks) {
Bill Buzbee1465db52009-09-23 17:17:35 -07001189 BasicBlock *newBB = dvmCompilerNewBB(kDalvikByteCode);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001190 newBB->id = blockID++;
1191 newBB->firstMIRInsn = insn;
Ben Cheng8b258bf2009-06-24 17:27:07 -07001192 newBB->startOffset = insn->offset;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001193 newBB->lastMIRInsn = curBB->lastMIRInsn;
1194 curBB->lastMIRInsn = insn->prev;
1195 insn->prev->next = NULL;
1196 insn->prev = NULL;
1197
1198 /*
1199 * If the insn is not an unconditional branch, set up the
1200 * fallthrough link.
1201 */
1202 if (!isUnconditionalBranch(curBB->lastMIRInsn)) {
1203 curBB->fallThrough = newBB;
1204 }
1205
Ben Cheng7a2697d2010-06-07 13:44:23 -07001206 /*
1207 * Fallthrough block of an invoke instruction needs to be
1208 * aligned to 4-byte boundary (alignment instruction to be
1209 * inserted later.
1210 */
Dan Bornstein44a38f42010-11-10 17:34:32 -08001211 if (dexGetInstrFlags(gDvm.instrInfo.flags,
Ben Cheng7a2697d2010-06-07 13:44:23 -07001212 curBB->lastMIRInsn->dalvikInsn.opCode) &
1213 kInstrInvoke) {
1214 newBB->isFallThroughFromInvoke = true;
1215 }
1216
Ben Chengba4fc8b2009-06-01 13:00:29 -07001217 /* enqueue the new block */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001218 blockList[cUnit->numBlocks++] = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001219 break;
1220 }
1221 }
1222 }
1223 }
1224
Ben Cheng7a2697d2010-06-07 13:44:23 -07001225 if (numBlocks != cUnit->numBlocks) {
1226 LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit->numBlocks);
1227 dvmCompilerAbort(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001228 }
1229
Ben Chengba4fc8b2009-06-01 13:00:29 -07001230 /* Connect the basic blocks through the taken links */
1231 for (i = 0; i < numBlocks; i++) {
1232 BasicBlock *curBB = blockList[i];
1233 MIR *insn = curBB->lastMIRInsn;
1234 unsigned int target = insn->offset;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001235 bool isInvoke = false;
1236 const Method *callee = NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001237
1238 findBlockBoundary(method, insn, target, &target, &isInvoke, &callee);
1239
Ben Cheng7a2697d2010-06-07 13:44:23 -07001240 /* Found a block ended on a branch (not invoke) */
1241 if (isInvoke == false && target != insn->offset) {
Ben Chengba4fc8b2009-06-01 13:00:29 -07001242 int j;
1243 /* Forward branch */
1244 if (target > insn->offset) {
1245 j = i + 1;
1246 } else {
1247 /* Backward branch */
1248 j = 0;
1249 }
1250 for (; j < numBlocks; j++) {
1251 if (blockList[j]->firstMIRInsn->offset == target) {
1252 curBB->taken = blockList[j];
1253 break;
1254 }
1255 }
Ben Cheng7a2697d2010-06-07 13:44:23 -07001256 }
Ben Chengba4fc8b2009-06-01 13:00:29 -07001257
Ben Cheng7a2697d2010-06-07 13:44:23 -07001258 if (isInvoke) {
1259 BasicBlock *newBB;
1260 /* Monomorphic callee */
1261 if (callee) {
1262 newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton);
1263 newBB->startOffset = 0;
1264 newBB->containingMethod = callee;
1265 /* Will resolve at runtime */
1266 } else {
1267 newBB = dvmCompilerNewBB(kChainingCellInvokePredicted);
1268 newBB->startOffset = 0;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001269 }
Ben Cheng7a2697d2010-06-07 13:44:23 -07001270 newBB->id = blockID++;
1271 curBB->taken = newBB;
1272 /* enqueue the new block */
1273 blockList[cUnit->numBlocks++] = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001274 }
1275 }
1276
Ben Cheng7a2697d2010-06-07 13:44:23 -07001277 if (cUnit->numBlocks != numBlocks + numInvokeTargets) {
1278 LOGE("Expect %d vs %d total blocks\n", numBlocks + numInvokeTargets,
1279 cUnit->numBlocks);
1280 dvmCompilerDumpCompilationUnit(cUnit);
1281 dvmCompilerAbort(cUnit);
1282 }
1283
Bill Buzbee716f1202009-07-23 13:22:09 -07001284 /* Set the instruction set to use (NOTE: later components may change it) */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001285 cUnit->instructionSet = dvmCompilerInstructionSet();
Bill Buzbee716f1202009-07-23 13:22:09 -07001286
Ben Cheng7a2697d2010-06-07 13:44:23 -07001287 /* Preparation for SSA conversion */
1288 dvmInitializeSSAConversion(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001289
Ben Cheng7a2697d2010-06-07 13:44:23 -07001290 /* SSA analysis */
1291 dvmCompilerNonLoopAnalysis(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001292
Ben Cheng7a2697d2010-06-07 13:44:23 -07001293 /* Needs to happen after SSA naming */
1294 dvmCompilerInitializeRegAlloc(cUnit);
1295
1296 /* Allocate Registers */
1297 dvmCompilerRegAlloc(cUnit);
1298
1299 /* Convert MIR to LIR, etc. */
1300 dvmCompilerMIR2LIR(cUnit);
1301
1302 /* Convert LIR into machine code. */
1303 dvmCompilerAssembleLIR(cUnit, info);
1304
buzbeebff121a2010-08-04 15:25:06 -07001305 if (cUnit->assemblerStatus != kSuccess) {
Ben Cheng7a2697d2010-06-07 13:44:23 -07001306 return false;
1307 }
1308
1309 dvmCompilerDumpCompilationUnit(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001310
1311 dvmCompilerArenaReset();
1312
Bill Buzbee716f1202009-07-23 13:22:09 -07001313 return info->codeAddress != NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001314}