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