blob: 76783ae92a8d1256a2270debe9cf05adf36d1e3f [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"
Dan Bornsteindf4daaf2010-12-01 14:23:44 -080018#include "libdex/DexOpcodes.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;
Dan Bornstein9a1f8162010-12-01 17:02:26 -080030 Opcode opcode = dexOpcodeFromCodeUnit(instr);
Ben Chengba4fc8b2009-06-01 13:00:29 -070031 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 Bornsteine4852762010-12-02 12:45:00 -080037 insnWidth = dexGetWidthFromOpcode(opcode);
Ben Chengba4fc8b2009-06-01 13:00:29 -070038 if (insnWidth < 0) {
39 insnWidth = -insnWidth;
40 }
41 }
42
Dan Bornstein54322392010-11-17 14:16:56 -080043 dexDecodeInstruction(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{
Dan Bornstein9a1f8162010-12-01 17:02:26 -080062 switch (insn->dalvikInsn.opcode) {
Ben Chengba4fc8b2009-06-01 13:00:29 -070063 /* 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{
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800160 switch (insn->dalvikInsn.opcode) {
Bill Buzbee324b3ac2009-12-04 13:17:36 -0800161 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{
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800175 switch (insn->dalvikInsn.opcode) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700176 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 Bornsteine4852762010-12-02 12:45:00 -0800208 int flags = dexGetFlagsFromOpcode(dalvikInsn->opcode);
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800209 int dalvikOpcode = dalvikInsn->opcode;
Ben Cheng7a2697d2010-06-07 13:44:23 -0700210
Dan Bornstein0759f522010-11-30 14:58:53 -0800211 if (flags & kInstrInvoke) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700212 attributes &= ~METHOD_IS_LEAF;
213 }
214
215 if (!(flags & kInstrCanReturn)) {
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800216 if (!(dvmCompilerDataFlowAttributes[dalvikOpcode] &
Ben Cheng7a2697d2010-06-07 13:44:23 -0700217 DF_IS_GETTER)) {
218 attributes &= ~METHOD_IS_GETTER;
219 }
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800220 if (!(dvmCompilerDataFlowAttributes[dalvikOpcode] &
Ben Cheng7a2697d2010-06-07 13:44:23 -0700221 DF_IS_SETTER)) {
222 attributes &= ~METHOD_IS_SETTER;
223 }
224 }
225
226 /*
227 * The expected instruction sequence is setter will never return value and
228 * getter will also do. Clear the bits if the behavior is discovered
229 * otherwise.
230 */
231 if (flags & kInstrCanReturn) {
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800232 if (dalvikOpcode == OP_RETURN_VOID) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700233 attributes &= ~METHOD_IS_GETTER;
234 }
235 else {
236 attributes &= ~METHOD_IS_SETTER;
237 }
238 }
239
240 if (flags & kInstrCanThrow) {
241 attributes &= ~METHOD_IS_THROW_FREE;
242 }
243
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800244 if (offset == 0 && dalvikOpcode == OP_RETURN_VOID) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700245 attributes |= METHOD_IS_EMPTY;
246 }
247
Ben Cheng34dc7962010-08-26 14:56:31 -0700248 /*
249 * Check if this opcode is selected for single stepping.
250 * If so, don't inline the callee as there is no stack frame for the
251 * interpreter to single-step through the instruction.
252 */
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800253 if (SINGLE_STEP_OP(dalvikOpcode)) {
Ben Cheng34dc7962010-08-26 14:56:31 -0700254 attributes &= ~(METHOD_IS_GETTER | METHOD_IS_SETTER);
255 }
256
Ben Cheng7a2697d2010-06-07 13:44:23 -0700257 return attributes;
258}
259
260/*
Ben Cheng8b258bf2009-06-24 17:27:07 -0700261 * Analyze each method whose traces are ever compiled. Collect a variety of
262 * statistics like the ratio of exercised vs overall code and code bloat
Ben Cheng7a2697d2010-06-07 13:44:23 -0700263 * ratios. If isCallee is true, also analyze each instruction in more details
264 * to see if it is suitable for inlining.
Ben Cheng8b258bf2009-06-24 17:27:07 -0700265 */
Ben Cheng7a2697d2010-06-07 13:44:23 -0700266CompilerMethodStats *dvmCompilerAnalyzeMethodBody(const Method *method,
267 bool isCallee)
Ben Cheng8b258bf2009-06-24 17:27:07 -0700268{
269 const DexCode *dexCode = dvmGetMethodCode(method);
270 const u2 *codePtr = dexCode->insns;
271 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
272 int insnSize = 0;
273 int hashValue = dvmComputeUtf8Hash(method->name);
274
275 CompilerMethodStats dummyMethodEntry; // For hash table lookup
276 CompilerMethodStats *realMethodEntry; // For hash table storage
277
278 /* For lookup only */
279 dummyMethodEntry.method = method;
Carl Shapirofc75f3e2010-12-07 11:43:38 -0800280 realMethodEntry =
281 (CompilerMethodStats *) dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue,
282 &dummyMethodEntry,
283 (HashCompareFunc) compareMethod,
284 false);
Ben Cheng8b258bf2009-06-24 17:27:07 -0700285
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;
Carl Shapirofc75f3e2010-12-07 11:43:38 -0800467 char *fullSignature = (char *)dvmCompilerNew(len, true);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700468 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;
Carl Shapirofc75f3e2010-12-07 11:43:38 -0800562 insn = (MIR *)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 Bornsteine4852762010-12-02 12:45:00 -0800573 int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode);
Ben Cheng7a2697d2010-06-07 13:44:23 -0700574
Dan Bornstein0759f522010-11-30 14:58:53 -0800575 if (flags & kInstrInvoke) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700576 assert(numInsts == 1);
577 CallsiteInfo *callsiteInfo =
Carl Shapirofc75f3e2010-12-07 11:43:38 -0800578 (CallsiteInfo *)dvmCompilerNew(sizeof(CallsiteInfo), true);
579 callsiteInfo->clazz = (ClassObject *)currRun[1].meta;
580 callsiteInfo->method = (Method *)currRun[2].meta;
Ben Cheng7a2697d2010-06-07 13:44:23 -0700581 insn->meta.callsiteInfo = callsiteInfo;
582 }
583
Ben Cheng1efc9c52009-06-08 18:25:27 -0700584 /* Instruction limit reached - terminate the trace here */
585 if (cUnit.numInsts >= numMaxInsts) {
586 break;
587 }
588 if (--numInsts == 0) {
Ben Chengba4fc8b2009-06-01 13:00:29 -0700589 if (currRun->frag.runEnd) {
Ben Cheng1efc9c52009-06-08 18:25:27 -0700590 break;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700591 } else {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700592 /* Advance to the next trace description (ie non-meta info) */
593 do {
594 currRun++;
595 } while (!currRun->frag.isCode);
596
597 /* Dummy end-of-run marker seen */
598 if (currRun->frag.numInsts == 0) {
599 break;
600 }
601
Bill Buzbee1465db52009-09-23 17:17:35 -0700602 curBB = dvmCompilerNewBB(kDalvikByteCode);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700603 lastBB->next = curBB;
604 lastBB = curBB;
605 curBB->id = numBlocks++;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700606 curOffset = currRun->frag.startOffset;
607 numInsts = currRun->frag.numInsts;
608 curBB->startOffset = curOffset;
609 codePtr = dexCode->insns + curOffset;
610 }
611 } else {
612 curOffset += width;
613 codePtr += width;
614 }
615 }
616
Ben Cheng1357e942010-02-10 17:21:39 -0800617#if defined(WITH_JIT_TUNING)
Ben Cheng8b258bf2009-06-24 17:27:07 -0700618 /* Convert # of half-word to bytes */
619 methodStats->compiledDalvikSize += traceSize * 2;
Ben Cheng1357e942010-02-10 17:21:39 -0800620#endif
Ben Cheng8b258bf2009-06-24 17:27:07 -0700621
Ben Chengba4fc8b2009-06-01 13:00:29 -0700622 /*
623 * Now scan basic blocks containing real code to connect the
624 * taken/fallthrough links. Also create chaining cells for code not included
625 * in the trace.
626 */
627 for (curBB = startBB; curBB; curBB = curBB->next) {
628 MIR *lastInsn = curBB->lastMIRInsn;
Ben Cheng4238ec22009-08-24 16:32:22 -0700629 /* Skip empty blocks */
Ben Chengba4fc8b2009-06-01 13:00:29 -0700630 if (lastInsn == NULL) {
Ben Cheng4238ec22009-08-24 16:32:22 -0700631 continue;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700632 }
633 curOffset = lastInsn->offset;
634 unsigned int targetOffset = curOffset;
635 unsigned int fallThroughOffset = curOffset + lastInsn->width;
636 bool isInvoke = false;
637 const Method *callee = NULL;
638
639 findBlockBoundary(desc->method, curBB->lastMIRInsn, curOffset,
640 &targetOffset, &isInvoke, &callee);
641
642 /* Link the taken and fallthrough blocks */
643 BasicBlock *searchBB;
644
Dan Bornsteine4852762010-12-02 12:45:00 -0800645 int flags = dexGetFlagsFromOpcode(lastInsn->dalvikInsn.opcode);
Ben Cheng7a2697d2010-06-07 13:44:23 -0700646
647 if (flags & kInstrInvoke) {
648 cUnit.hasInvoke = true;
649 }
650
Ben Chengba4fc8b2009-06-01 13:00:29 -0700651 /* No backward branch in the trace - start searching the next BB */
652 for (searchBB = curBB->next; searchBB; searchBB = searchBB->next) {
653 if (targetOffset == searchBB->startOffset) {
654 curBB->taken = searchBB;
655 }
656 if (fallThroughOffset == searchBB->startOffset) {
657 curBB->fallThrough = searchBB;
Ben Cheng7a2697d2010-06-07 13:44:23 -0700658
659 /*
660 * Fallthrough block of an invoke instruction needs to be
661 * aligned to 4-byte boundary (alignment instruction to be
662 * inserted later.
663 */
664 if (flags & kInstrInvoke) {
665 searchBB->isFallThroughFromInvoke = true;
666 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700667 }
668 }
669
Ben Cheng1efc9c52009-06-08 18:25:27 -0700670 /*
671 * Some blocks are ended by non-control-flow-change instructions,
672 * currently only due to trace length constraint. In this case we need
673 * to generate an explicit branch at the end of the block to jump to
674 * the chaining cell.
675 */
676 curBB->needFallThroughBranch =
Ben Cheng17f15ce2009-07-27 16:21:52 -0700677 ((flags & (kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn |
Dan Bornstein0759f522010-11-30 14:58:53 -0800678 kInstrInvoke)) == 0);
Ben Cheng17f15ce2009-07-27 16:21:52 -0700679
Ben Cheng4a419582010-08-04 13:23:09 -0700680 /* Only form a loop if JIT_OPT_NO_LOOP is not set */
Ben Cheng4238ec22009-08-24 16:32:22 -0700681 if (curBB->taken == NULL &&
682 curBB->fallThrough == NULL &&
683 flags == (kInstrCanBranch | kInstrCanContinue) &&
Ben Cheng4a419582010-08-04 13:23:09 -0700684 fallThroughOffset == startBB->startOffset &&
685 JIT_OPT_NO_LOOP != (optHints & JIT_OPT_NO_LOOP)) {
Ben Cheng0fd31e42009-09-03 14:40:16 -0700686 BasicBlock *loopBranch = curBB;
687 BasicBlock *exitBB;
688 BasicBlock *exitChainingCell;
Ben Cheng4238ec22009-08-24 16:32:22 -0700689
690 if (cUnit.printMe) {
691 LOGD("Natural loop detected!");
692 }
Ben Cheng7a2697d2010-06-07 13:44:23 -0700693 exitBB = dvmCompilerNewBB(kTraceExitBlock);
Ben Cheng0fd31e42009-09-03 14:40:16 -0700694 lastBB->next = exitBB;
695 lastBB = exitBB;
Ben Cheng4238ec22009-08-24 16:32:22 -0700696
Ben Cheng0fd31e42009-09-03 14:40:16 -0700697 exitBB->startOffset = targetOffset;
698 exitBB->id = numBlocks++;
699 exitBB->needFallThroughBranch = true;
Ben Cheng4238ec22009-08-24 16:32:22 -0700700
Ben Cheng0fd31e42009-09-03 14:40:16 -0700701 loopBranch->taken = exitBB;
Bill Buzbee9c4b7c82009-09-10 10:10:38 -0700702#if defined(WITH_SELF_VERIFICATION)
Ben Cheng0fd31e42009-09-03 14:40:16 -0700703 BasicBlock *backwardCell =
Bill Buzbee1465db52009-09-23 17:17:35 -0700704 dvmCompilerNewBB(kChainingCellBackwardBranch);
Ben Cheng0fd31e42009-09-03 14:40:16 -0700705 lastBB->next = backwardCell;
706 lastBB = backwardCell;
Ben Cheng4238ec22009-08-24 16:32:22 -0700707
Ben Cheng0fd31e42009-09-03 14:40:16 -0700708 backwardCell->startOffset = startBB->startOffset;
709 backwardCell->id = numBlocks++;
710 loopBranch->fallThrough = backwardCell;
Bill Buzbee9c4b7c82009-09-10 10:10:38 -0700711#elif defined(WITH_JIT_TUNING)
712 if (gDvmJit.profile) {
713 BasicBlock *backwardCell =
Bill Buzbee1465db52009-09-23 17:17:35 -0700714 dvmCompilerNewBB(kChainingCellBackwardBranch);
Bill Buzbee9c4b7c82009-09-10 10:10:38 -0700715 lastBB->next = backwardCell;
716 lastBB = backwardCell;
717
718 backwardCell->startOffset = startBB->startOffset;
719 backwardCell->id = numBlocks++;
720 loopBranch->fallThrough = backwardCell;
721 } else {
722 loopBranch->fallThrough = startBB->next;
723 }
724#else
725 loopBranch->fallThrough = startBB->next;
Ben Cheng0fd31e42009-09-03 14:40:16 -0700726#endif
727
728 /* Create the chaining cell as the fallthrough of the exit block */
Bill Buzbee1465db52009-09-23 17:17:35 -0700729 exitChainingCell = dvmCompilerNewBB(kChainingCellNormal);
Ben Cheng0fd31e42009-09-03 14:40:16 -0700730 lastBB->next = exitChainingCell;
731 lastBB = exitChainingCell;
732
733 exitChainingCell->startOffset = targetOffset;
734 exitChainingCell->id = numBlocks++;
735
736 exitBB->fallThrough = exitChainingCell;
737
Ben Cheng4238ec22009-08-24 16:32:22 -0700738 cUnit.hasLoop = true;
739 }
740
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800741 if (lastInsn->dalvikInsn.opcode == OP_PACKED_SWITCH ||
742 lastInsn->dalvikInsn.opcode == OP_SPARSE_SWITCH) {
Ben Cheng6c10a972009-10-29 14:39:18 -0700743 int i;
744 const u2 *switchData = desc->method->insns + lastInsn->offset +
745 lastInsn->dalvikInsn.vB;
746 int size = switchData[1];
747 int maxChains = MIN(size, MAX_CHAINED_SWITCH_CASES);
748
749 /*
750 * Generate the landing pad for cases whose ranks are higher than
751 * MAX_CHAINED_SWITCH_CASES. The code will re-enter the interpreter
752 * through the NoChain point.
753 */
754 if (maxChains != size) {
755 cUnit.switchOverflowPad =
756 desc->method->insns + lastInsn->offset;
757 }
758
759 s4 *targets = (s4 *) (switchData + 2 +
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800760 (lastInsn->dalvikInsn.opcode == OP_PACKED_SWITCH ?
Ben Cheng6c10a972009-10-29 14:39:18 -0700761 2 : size * 2));
762
763 /* One chaining cell for the first MAX_CHAINED_SWITCH_CASES cases */
764 for (i = 0; i < maxChains; i++) {
765 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
766 lastBB->next = caseChain;
767 lastBB = caseChain;
768
769 caseChain->startOffset = lastInsn->offset + targets[i];
770 caseChain->id = numBlocks++;
771 }
772
773 /* One more chaining cell for the default case */
774 BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal);
775 lastBB->next = caseChain;
776 lastBB = caseChain;
777
778 caseChain->startOffset = lastInsn->offset + lastInsn->width;
779 caseChain->id = numBlocks++;
Ben Cheng6d576092009-09-01 17:01:58 -0700780 /* Fallthrough block not included in the trace */
Ben Cheng6c10a972009-10-29 14:39:18 -0700781 } else if (!isUnconditionalBranch(lastInsn) &&
782 curBB->fallThrough == NULL) {
Ben Cheng6d576092009-09-01 17:01:58 -0700783 /*
784 * If the chaining cell is after an invoke or
785 * instruction that cannot change the control flow, request a hot
786 * chaining cell.
787 */
788 if (isInvoke || curBB->needFallThroughBranch) {
Bill Buzbee1465db52009-09-23 17:17:35 -0700789 lastBB->next = dvmCompilerNewBB(kChainingCellHot);
Ben Cheng6d576092009-09-01 17:01:58 -0700790 } else {
Bill Buzbee1465db52009-09-23 17:17:35 -0700791 lastBB->next = dvmCompilerNewBB(kChainingCellNormal);
Ben Cheng6d576092009-09-01 17:01:58 -0700792 }
793 lastBB = lastBB->next;
794 lastBB->id = numBlocks++;
795 lastBB->startOffset = fallThroughOffset;
796 curBB->fallThrough = lastBB;
797 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700798 /* Target block not included in the trace */
Ben Cheng38329f52009-07-07 14:19:20 -0700799 if (curBB->taken == NULL &&
Bill Buzbee324b3ac2009-12-04 13:17:36 -0800800 (isGoto(lastInsn) || isInvoke ||
801 (targetOffset != UNKNOWN_TARGET && targetOffset != curOffset))) {
Ben Cheng38329f52009-07-07 14:19:20 -0700802 BasicBlock *newBB;
Ben Cheng1efc9c52009-06-08 18:25:27 -0700803 if (isInvoke) {
Ben Cheng38329f52009-07-07 14:19:20 -0700804 /* Monomorphic callee */
805 if (callee) {
Bill Buzbee1465db52009-09-23 17:17:35 -0700806 newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton);
Ben Cheng38329f52009-07-07 14:19:20 -0700807 newBB->startOffset = 0;
808 newBB->containingMethod = callee;
809 /* Will resolve at runtime */
810 } else {
Bill Buzbee1465db52009-09-23 17:17:35 -0700811 newBB = dvmCompilerNewBB(kChainingCellInvokePredicted);
Ben Cheng38329f52009-07-07 14:19:20 -0700812 newBB->startOffset = 0;
813 }
Ben Cheng1efc9c52009-06-08 18:25:27 -0700814 /* For unconditional branches, request a hot chaining cell */
815 } else {
Jeff Hao97319a82009-08-12 16:57:15 -0700816#if !defined(WITH_SELF_VERIFICATION)
Dan Bornsteinc2b486f2010-11-12 16:07:16 -0800817 newBB = dvmCompilerNewBB(dexIsGoto(flags) ?
Bill Buzbee1465db52009-09-23 17:17:35 -0700818 kChainingCellHot :
819 kChainingCellNormal);
Ben Cheng38329f52009-07-07 14:19:20 -0700820 newBB->startOffset = targetOffset;
Jeff Hao97319a82009-08-12 16:57:15 -0700821#else
822 /* Handle branches that branch back into the block */
823 if (targetOffset >= curBB->firstMIRInsn->offset &&
824 targetOffset <= curBB->lastMIRInsn->offset) {
Bill Buzbee1465db52009-09-23 17:17:35 -0700825 newBB = dvmCompilerNewBB(kChainingCellBackwardBranch);
Jeff Hao97319a82009-08-12 16:57:15 -0700826 } else {
Dan Bornsteinc2b486f2010-11-12 16:07:16 -0800827 newBB = dvmCompilerNewBB(dexIsGoto(flags) ?
Bill Buzbee1465db52009-09-23 17:17:35 -0700828 kChainingCellHot :
829 kChainingCellNormal);
Jeff Hao97319a82009-08-12 16:57:15 -0700830 }
831 newBB->startOffset = targetOffset;
832#endif
Ben Cheng1efc9c52009-06-08 18:25:27 -0700833 }
Ben Cheng38329f52009-07-07 14:19:20 -0700834 newBB->id = numBlocks++;
835 curBB->taken = newBB;
836 lastBB->next = newBB;
837 lastBB = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700838 }
Ben Chengba4fc8b2009-06-01 13:00:29 -0700839 }
840
841 /* Now create a special block to host PC reconstruction code */
Bill Buzbee1465db52009-09-23 17:17:35 -0700842 lastBB->next = dvmCompilerNewBB(kPCReconstruction);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700843 lastBB = lastBB->next;
844 lastBB->id = numBlocks++;
845
846 /* And one final block that publishes the PC and raise the exception */
Bill Buzbee1465db52009-09-23 17:17:35 -0700847 lastBB->next = dvmCompilerNewBB(kExceptionHandling);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700848 lastBB = lastBB->next;
849 lastBB->id = numBlocks++;
850
851 if (cUnit.printMe) {
Elliott Hughescc6fac82010-07-02 13:38:44 -0700852 char* signature = dexProtoCopyMethodDescriptor(&desc->method->prototype);
853 LOGD("TRACEINFO (%d): 0x%08x %s%s.%s 0x%x %d of %d, %d blocks",
Ben Chenge9695e52009-06-16 16:11:47 -0700854 compilationId,
Ben Chengba4fc8b2009-06-01 13:00:29 -0700855 (intptr_t) desc->method->insns,
856 desc->method->clazz->descriptor,
857 desc->method->name,
Elliott Hughescc6fac82010-07-02 13:38:44 -0700858 signature,
Ben Chengba4fc8b2009-06-01 13:00:29 -0700859 desc->trace[0].frag.startOffset,
860 traceSize,
861 dexCode->insnsSize,
862 numBlocks);
Elliott Hughescc6fac82010-07-02 13:38:44 -0700863 free(signature);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700864 }
865
866 BasicBlock **blockList;
867
Ben Chengba4fc8b2009-06-01 13:00:29 -0700868 cUnit.traceDesc = desc;
869 cUnit.numBlocks = numBlocks;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700870 blockList = cUnit.blockList =
Carl Shapirofc75f3e2010-12-07 11:43:38 -0800871 (BasicBlock **)dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700872
873 int i;
874
875 for (i = 0, curBB = startBB; i < numBlocks; i++) {
876 blockList[i] = curBB;
877 curBB = curBB->next;
878 }
879 /* Make sure all blocks are added to the cUnit */
880 assert(curBB == NULL);
881
Ben Cheng7a2697d2010-06-07 13:44:23 -0700882 /* Set the instruction set to use (NOTE: later components may change it) */
883 cUnit.instructionSet = dvmCompilerInstructionSet();
884
885 /* Inline transformation @ the MIR level */
886 if (cUnit.hasInvoke && !(gDvmJit.disableOpt & (1 << kMethodInlining))) {
887 dvmCompilerInlineMIR(&cUnit);
888 }
889
Ben Cheng4238ec22009-08-24 16:32:22 -0700890 /* Preparation for SSA conversion */
891 dvmInitializeSSAConversion(&cUnit);
892
893 if (cUnit.hasLoop) {
Ben Cheng4a419582010-08-04 13:23:09 -0700894 /*
895 * Loop is not optimizable (for example lack of a single induction
896 * variable), punt and recompile the trace with loop optimization
897 * disabled.
898 */
899 bool loopOpt = dvmCompilerLoopOpt(&cUnit);
900 if (loopOpt == false) {
901 if (cUnit.printMe) {
902 LOGD("Loop is not optimizable - retry codegen");
903 }
904 /* Reset the compiler resource pool */
905 dvmCompilerArenaReset();
906 return dvmCompileTrace(desc, cUnit.numInsts, info, bailPtr,
907 optHints | JIT_OPT_NO_LOOP);
908 }
Ben Cheng4238ec22009-08-24 16:32:22 -0700909 }
910 else {
911 dvmCompilerNonLoopAnalysis(&cUnit);
912 }
913
Bill Buzbee1465db52009-09-23 17:17:35 -0700914 dvmCompilerInitializeRegAlloc(&cUnit); // Needs to happen after SSA naming
915
Ben Chengba4fc8b2009-06-01 13:00:29 -0700916 if (cUnit.printMe) {
917 dvmCompilerDumpCompilationUnit(&cUnit);
918 }
919
Bill Buzbee1465db52009-09-23 17:17:35 -0700920 /* Allocate Registers */
921 dvmCompilerRegAlloc(&cUnit);
922
Ben Chengba4fc8b2009-06-01 13:00:29 -0700923 /* Convert MIR to LIR, etc. */
924 dvmCompilerMIR2LIR(&cUnit);
925
buzbeebff121a2010-08-04 15:25:06 -0700926 /* Convert LIR into machine code. Loop for recoverable retries */
927 do {
928 dvmCompilerAssembleLIR(&cUnit, info);
929 cUnit.assemblerRetries++;
930 if (cUnit.printMe && cUnit.assemblerStatus != kSuccess)
931 LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries,
932 cUnit.assemblerStatus);
933 } while (cUnit.assemblerStatus == kRetryAll);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700934
935 if (cUnit.printMe) {
buzbeebff121a2010-08-04 15:25:06 -0700936 dvmCompilerCodegenDump(&cUnit);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700937 LOGD("End %s%s, %d Dalvik instructions",
938 desc->method->clazz->descriptor, desc->method->name,
939 cUnit.numInsts);
Ben Chengba4fc8b2009-06-01 13:00:29 -0700940 }
941
942 /* Reset the compiler resource pool */
943 dvmCompilerArenaReset();
944
buzbeebff121a2010-08-04 15:25:06 -0700945 if (cUnit.assemblerStatus == kRetryHalve) {
946 /* Halve the instruction count and start from the top */
Ben Cheng4a419582010-08-04 13:23:09 -0700947 return dvmCompileTrace(desc, cUnit.numInsts / 2, info, bailPtr,
948 optHints);
Ben Cheng1efc9c52009-06-08 18:25:27 -0700949 }
buzbeebff121a2010-08-04 15:25:06 -0700950
951 assert(cUnit.assemblerStatus == kSuccess);
952#if defined(WITH_JIT_TUNING)
953 methodStats->nativeSize += cUnit.totalSize;
954#endif
955 return info->codeAddress != NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -0700956}
957
958/*
Ben Cheng7a2697d2010-06-07 13:44:23 -0700959 * Since we are including instructions from possibly a cold method into the
960 * current trace, we need to make sure that all the associated information
961 * with the callee is properly initialized. If not, we punt on this inline
962 * target.
963 *
Ben Cheng34dc7962010-08-26 14:56:31 -0700964 * TODO: volatile instructions will be handled later.
Ben Cheng7a2697d2010-06-07 13:44:23 -0700965 */
966bool dvmCompilerCanIncludeThisInstruction(const Method *method,
967 const DecodedInstruction *insn)
968{
Dan Bornstein9a1f8162010-12-01 17:02:26 -0800969 switch (insn->opcode) {
Ben Cheng7a2697d2010-06-07 13:44:23 -0700970 case OP_NEW_INSTANCE:
971 case OP_CHECK_CAST: {
Carl Shapirofc75f3e2010-12-07 11:43:38 -0800972 ClassObject *classPtr = (ClassObject *)(void*)
Ben Cheng7a2697d2010-06-07 13:44:23 -0700973 (method->clazz->pDvmDex->pResClasses[insn->vB]);
974
975 /* Class hasn't been initialized yet */
976 if (classPtr == NULL) {
977 return false;
978 }
979 return true;
980 }
981 case OP_SGET_OBJECT:
982 case OP_SGET_BOOLEAN:
983 case OP_SGET_CHAR:
984 case OP_SGET_BYTE:
985 case OP_SGET_SHORT:
986 case OP_SGET:
987 case OP_SGET_WIDE:
988 case OP_SPUT_OBJECT:
989 case OP_SPUT_BOOLEAN:
990 case OP_SPUT_CHAR:
991 case OP_SPUT_BYTE:
992 case OP_SPUT_SHORT:
993 case OP_SPUT:
994 case OP_SPUT_WIDE: {
995 void *fieldPtr = (void*)
996 (method->clazz->pDvmDex->pResFields[insn->vB]);
997
998 if (fieldPtr == NULL) {
999 return false;
1000 }
1001 return true;
1002 }
1003 case OP_INVOKE_SUPER:
1004 case OP_INVOKE_SUPER_RANGE: {
1005 int mIndex = method->clazz->pDvmDex->
1006 pResMethods[insn->vB]->methodIndex;
1007 const Method *calleeMethod = method->clazz->super->vtable[mIndex];
1008 if (calleeMethod == NULL) {
1009 return false;
1010 }
1011 return true;
1012 }
1013 case OP_INVOKE_SUPER_QUICK:
1014 case OP_INVOKE_SUPER_QUICK_RANGE: {
1015 const Method *calleeMethod = method->clazz->super->vtable[insn->vB];
1016 if (calleeMethod == NULL) {
1017 return false;
1018 }
1019 return true;
1020 }
1021 case OP_INVOKE_STATIC:
1022 case OP_INVOKE_STATIC_RANGE:
1023 case OP_INVOKE_DIRECT:
1024 case OP_INVOKE_DIRECT_RANGE: {
1025 const Method *calleeMethod =
1026 method->clazz->pDvmDex->pResMethods[insn->vB];
1027 if (calleeMethod == NULL) {
1028 return false;
1029 }
1030 return true;
1031 }
1032 case OP_CONST_CLASS: {
1033 void *classPtr = (void*)
1034 (method->clazz->pDvmDex->pResClasses[insn->vB]);
1035
1036 if (classPtr == NULL) {
1037 return false;
1038 }
1039 return true;
1040 }
1041 case OP_CONST_STRING_JUMBO:
1042 case OP_CONST_STRING: {
1043 void *strPtr = (void*)
1044 (method->clazz->pDvmDex->pResStrings[insn->vB]);
1045
1046 if (strPtr == NULL) {
1047 return false;
1048 }
1049 return true;
1050 }
1051 default:
1052 return true;
1053 }
1054}
1055
1056/*
Ben Chengba4fc8b2009-06-01 13:00:29 -07001057 * Similar to dvmCompileTrace, but the entity processed here is the whole
1058 * method.
1059 *
1060 * TODO: implementation will be revisited when the trace builder can provide
1061 * whole-method traces.
1062 */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001063bool dvmCompileMethod(CompilationUnit *cUnit, const Method *method,
1064 JitTranslationInfo *info)
Ben Chengba4fc8b2009-06-01 13:00:29 -07001065{
1066 const DexCode *dexCode = dvmGetMethodCode(method);
1067 const u2 *codePtr = dexCode->insns;
1068 const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
1069 int blockID = 0;
1070 unsigned int curOffset = 0;
1071
Ben Cheng7a2697d2010-06-07 13:44:23 -07001072 /* If we've already compiled this trace, just return success */
1073 if (dvmJitGetCodeAddr(codePtr) && !info->discardResult) {
1074 return true;
1075 }
1076
1077 /* Doing method-based compilation */
1078 cUnit->wholeMethod = true;
1079
Bill Buzbee1465db52009-09-23 17:17:35 -07001080 BasicBlock *firstBlock = dvmCompilerNewBB(kDalvikByteCode);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001081 firstBlock->id = blockID++;
1082
1083 /* Allocate the bit-vector to track the beginning of basic blocks */
Ben Cheng4238ec22009-08-24 16:32:22 -07001084 BitVector *bbStartAddr = dvmCompilerAllocBitVector(dexCode->insnsSize+1,
1085 false);
1086 dvmCompilerSetBit(bbStartAddr, 0);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001087
Ben Cheng7a2697d2010-06-07 13:44:23 -07001088 int numInvokeTargets = 0;
1089
Ben Chengba4fc8b2009-06-01 13:00:29 -07001090 /*
1091 * Sequentially go through every instruction first and put them in a single
1092 * basic block. Identify block boundaries at the mean time.
1093 */
1094 while (codePtr < codeEnd) {
Carl Shapirofc75f3e2010-12-07 11:43:38 -08001095 MIR *insn = (MIR *)dvmCompilerNew(sizeof(MIR), true);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001096 insn->offset = curOffset;
1097 int width = parseInsn(codePtr, &insn->dalvikInsn, false);
1098 bool isInvoke = false;
1099 const Method *callee;
1100 insn->width = width;
1101
Ben Cheng8b258bf2009-06-24 17:27:07 -07001102 /* Terminate when the data section is seen */
1103 if (width == 0)
1104 break;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001105
1106 if (!dvmCompilerCanIncludeThisInstruction(cUnit->method,
1107 &insn->dalvikInsn)) {
1108 return false;
1109 }
1110
Ben Chengba4fc8b2009-06-01 13:00:29 -07001111 dvmCompilerAppendMIR(firstBlock, insn);
1112 /*
1113 * Check whether this is a block ending instruction and whether it
1114 * suggests the start of a new block
1115 */
1116 unsigned int target = curOffset;
1117
1118 /*
1119 * If findBlockBoundary returns true, it means the current instruction
1120 * is terminating the current block. If it is a branch, the target
1121 * address will be recorded in target.
1122 */
1123 if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke,
1124 &callee)) {
Ben Cheng4238ec22009-08-24 16:32:22 -07001125 dvmCompilerSetBit(bbStartAddr, curOffset + width);
Ben Cheng7a2697d2010-06-07 13:44:23 -07001126 /* Each invoke needs a chaining cell block */
1127 if (isInvoke) {
1128 numInvokeTargets++;
1129 }
1130 /* A branch will end the current block */
1131 else if (target != curOffset && target != UNKNOWN_TARGET) {
Ben Cheng4238ec22009-08-24 16:32:22 -07001132 dvmCompilerSetBit(bbStartAddr, target);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001133 }
1134 }
1135
1136 codePtr += width;
1137 /* each bit represents 16-bit quantity */
1138 curOffset += width;
1139 }
1140
1141 /*
1142 * The number of blocks will be equal to the number of bits set to 1 in the
1143 * bit vector minus 1, because the bit representing the location after the
1144 * last instruction is set to one.
Ben Cheng7a2697d2010-06-07 13:44:23 -07001145 *
1146 * We also add additional blocks for invoke chaining and the number is
1147 * denoted by numInvokeTargets.
Ben Chengba4fc8b2009-06-01 13:00:29 -07001148 */
1149 int numBlocks = dvmCountSetBits(bbStartAddr);
1150 if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) {
1151 numBlocks--;
1152 }
1153
Ben Chengba4fc8b2009-06-01 13:00:29 -07001154 BasicBlock **blockList;
Carl Shapirofc75f3e2010-12-07 11:43:38 -08001155 blockList = cUnit->blockList = (BasicBlock **)
Ben Cheng7a2697d2010-06-07 13:44:23 -07001156 dvmCompilerNew(sizeof(BasicBlock *) * (numBlocks + numInvokeTargets),
1157 true);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001158
1159 /*
Ben Cheng7a2697d2010-06-07 13:44:23 -07001160 * Register the first block onto the list and start splitting it into
1161 * sub-blocks.
Ben Chengba4fc8b2009-06-01 13:00:29 -07001162 */
1163 blockList[0] = firstBlock;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001164 cUnit->numBlocks = 1;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001165
1166 int i;
1167 for (i = 0; i < numBlocks; i++) {
1168 MIR *insn;
1169 BasicBlock *curBB = blockList[i];
1170 curOffset = curBB->lastMIRInsn->offset;
1171
1172 for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) {
1173 /* Found the beginning of a new block, see if it is created yet */
1174 if (dvmIsBitSet(bbStartAddr, insn->offset)) {
1175 int j;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001176 for (j = 0; j < cUnit->numBlocks; j++) {
Ben Chengba4fc8b2009-06-01 13:00:29 -07001177 if (blockList[j]->firstMIRInsn->offset == insn->offset)
1178 break;
1179 }
1180
1181 /* Block not split yet - do it now */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001182 if (j == cUnit->numBlocks) {
Bill Buzbee1465db52009-09-23 17:17:35 -07001183 BasicBlock *newBB = dvmCompilerNewBB(kDalvikByteCode);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001184 newBB->id = blockID++;
1185 newBB->firstMIRInsn = insn;
Ben Cheng8b258bf2009-06-24 17:27:07 -07001186 newBB->startOffset = insn->offset;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001187 newBB->lastMIRInsn = curBB->lastMIRInsn;
1188 curBB->lastMIRInsn = insn->prev;
1189 insn->prev->next = NULL;
1190 insn->prev = NULL;
1191
1192 /*
1193 * If the insn is not an unconditional branch, set up the
1194 * fallthrough link.
1195 */
1196 if (!isUnconditionalBranch(curBB->lastMIRInsn)) {
1197 curBB->fallThrough = newBB;
1198 }
1199
Ben Cheng7a2697d2010-06-07 13:44:23 -07001200 /*
1201 * Fallthrough block of an invoke instruction needs to be
1202 * aligned to 4-byte boundary (alignment instruction to be
1203 * inserted later.
1204 */
Dan Bornsteine4852762010-12-02 12:45:00 -08001205 if (dexGetFlagsFromOpcode(curBB->lastMIRInsn->dalvikInsn.opcode)
Dan Bornstein41e286c2010-11-19 12:36:19 -08001206 & kInstrInvoke) {
Ben Cheng7a2697d2010-06-07 13:44:23 -07001207 newBB->isFallThroughFromInvoke = true;
1208 }
1209
Ben Chengba4fc8b2009-06-01 13:00:29 -07001210 /* enqueue the new block */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001211 blockList[cUnit->numBlocks++] = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001212 break;
1213 }
1214 }
1215 }
1216 }
1217
Ben Cheng7a2697d2010-06-07 13:44:23 -07001218 if (numBlocks != cUnit->numBlocks) {
1219 LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit->numBlocks);
1220 dvmCompilerAbort(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001221 }
1222
Ben Chengba4fc8b2009-06-01 13:00:29 -07001223 /* Connect the basic blocks through the taken links */
1224 for (i = 0; i < numBlocks; i++) {
1225 BasicBlock *curBB = blockList[i];
1226 MIR *insn = curBB->lastMIRInsn;
1227 unsigned int target = insn->offset;
Ben Cheng7a2697d2010-06-07 13:44:23 -07001228 bool isInvoke = false;
1229 const Method *callee = NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001230
1231 findBlockBoundary(method, insn, target, &target, &isInvoke, &callee);
1232
Ben Cheng7a2697d2010-06-07 13:44:23 -07001233 /* Found a block ended on a branch (not invoke) */
1234 if (isInvoke == false && target != insn->offset) {
Ben Chengba4fc8b2009-06-01 13:00:29 -07001235 int j;
1236 /* Forward branch */
1237 if (target > insn->offset) {
1238 j = i + 1;
1239 } else {
1240 /* Backward branch */
1241 j = 0;
1242 }
1243 for (; j < numBlocks; j++) {
1244 if (blockList[j]->firstMIRInsn->offset == target) {
1245 curBB->taken = blockList[j];
1246 break;
1247 }
1248 }
Ben Cheng7a2697d2010-06-07 13:44:23 -07001249 }
Ben Chengba4fc8b2009-06-01 13:00:29 -07001250
Ben Cheng7a2697d2010-06-07 13:44:23 -07001251 if (isInvoke) {
1252 BasicBlock *newBB;
1253 /* Monomorphic callee */
1254 if (callee) {
1255 newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton);
1256 newBB->startOffset = 0;
1257 newBB->containingMethod = callee;
1258 /* Will resolve at runtime */
1259 } else {
1260 newBB = dvmCompilerNewBB(kChainingCellInvokePredicted);
1261 newBB->startOffset = 0;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001262 }
Ben Cheng7a2697d2010-06-07 13:44:23 -07001263 newBB->id = blockID++;
1264 curBB->taken = newBB;
1265 /* enqueue the new block */
1266 blockList[cUnit->numBlocks++] = newBB;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001267 }
1268 }
1269
Ben Cheng7a2697d2010-06-07 13:44:23 -07001270 if (cUnit->numBlocks != numBlocks + numInvokeTargets) {
1271 LOGE("Expect %d vs %d total blocks\n", numBlocks + numInvokeTargets,
1272 cUnit->numBlocks);
1273 dvmCompilerDumpCompilationUnit(cUnit);
1274 dvmCompilerAbort(cUnit);
1275 }
1276
Bill Buzbee716f1202009-07-23 13:22:09 -07001277 /* Set the instruction set to use (NOTE: later components may change it) */
Ben Cheng7a2697d2010-06-07 13:44:23 -07001278 cUnit->instructionSet = dvmCompilerInstructionSet();
Bill Buzbee716f1202009-07-23 13:22:09 -07001279
Ben Cheng7a2697d2010-06-07 13:44:23 -07001280 /* Preparation for SSA conversion */
1281 dvmInitializeSSAConversion(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001282
Ben Cheng7a2697d2010-06-07 13:44:23 -07001283 /* SSA analysis */
1284 dvmCompilerNonLoopAnalysis(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001285
Ben Cheng7a2697d2010-06-07 13:44:23 -07001286 /* Needs to happen after SSA naming */
1287 dvmCompilerInitializeRegAlloc(cUnit);
1288
1289 /* Allocate Registers */
1290 dvmCompilerRegAlloc(cUnit);
1291
1292 /* Convert MIR to LIR, etc. */
1293 dvmCompilerMIR2LIR(cUnit);
1294
1295 /* Convert LIR into machine code. */
1296 dvmCompilerAssembleLIR(cUnit, info);
1297
buzbeebff121a2010-08-04 15:25:06 -07001298 if (cUnit->assemblerStatus != kSuccess) {
Ben Cheng7a2697d2010-06-07 13:44:23 -07001299 return false;
1300 }
1301
1302 dvmCompilerDumpCompilationUnit(cUnit);
Ben Chengba4fc8b2009-06-01 13:00:29 -07001303
1304 dvmCompilerArenaReset();
1305
Bill Buzbee716f1202009-07-23 13:22:09 -07001306 return info->codeAddress != NULL;
Ben Chengba4fc8b2009-06-01 13:00:29 -07001307}