blob: ab940af017d51337fa22d461c0041a08a81c7038 [file] [log] [blame]
buzbee67bf8852011-08-17 17:51:35 -07001/*
2 * Copyright (C) 2011 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 "CompilerInternals.h"
19#include "Dataflow.h"
Ian Rogers0571d352011-11-03 19:51:38 -070020#include "leb128.h"
Brian Carlstrom9baa4ae2011-09-01 21:14:14 -070021#include "object.h"
Brian Carlstrom1f870082011-08-23 16:02:11 -070022#include "runtime.h"
buzbee67bf8852011-08-17 17:51:35 -070023
Elliott Hughes11d1b0c2012-01-23 16:57:47 -080024namespace art {
25
buzbee692be802012-08-29 15:52:59 -070026#if defined(ART_USE_QUICK_COMPILER)
27QuickCompiler::QuickCompiler(art::Compiler* compiler)
28 : compiler_(compiler) {
29 // Create context, module, intrinsic helper & ir builder
30 llvm_context_.reset(new llvm::LLVMContext());
31 llvm_module_.reset(new llvm::Module("art", *llvm_context_));
32 llvm::StructType::create(*llvm_context_, "JavaObject");
33 llvm::StructType::create(*llvm_context_, "Method");
34 llvm::StructType::create(*llvm_context_, "Thread");
35 intrinsic_helper_.reset( new greenland::IntrinsicHelper(*llvm_context_, *llvm_module_));
36 ir_builder_.reset(new greenland::IRBuilder(*llvm_context_, *llvm_module_, *intrinsic_helper_));
37}
38
39QuickCompiler::~QuickCompiler() {
40}
41
42extern "C" void ArtInitQuickCompilerContext(art::Compiler& compiler) {
43 CHECK(compiler.GetCompilerContext() == NULL);
44 QuickCompiler* quickCompiler = new QuickCompiler(&compiler);
45 compiler.SetCompilerContext(quickCompiler);
46}
47
48extern "C" void ArtUnInitQuickCompilerContext(art::Compiler& compiler) {
49 delete reinterpret_cast<QuickCompiler*>(compiler.GetCompilerContext());
50 compiler.SetCompilerContext(NULL);
51}
52#endif
53
buzbeece302932011-10-04 14:32:18 -070054/* Default optimizer/debug setting for the compiler. */
Elliott Hughese52e49b2012-04-02 16:05:44 -070055static uint32_t kCompilerOptimizerDisableFlags = 0 | // Disable specific optimizations
Bill Buzbeea114add2012-05-03 15:00:40 -070056 //(1 << kLoadStoreElimination) |
57 //(1 << kLoadHoisting) |
58 //(1 << kSuppressLoads) |
59 //(1 << kNullCheckElimination) |
60 //(1 << kPromoteRegs) |
61 //(1 << kTrackLiveTemps) |
62 //(1 << kSkipLargeMethodOptimization) |
63 //(1 << kSafeOptimizations) |
64 //(1 << kBBOpt) |
65 //(1 << kMatch) |
66 //(1 << kPromoteCompilerTemps) |
67 0;
buzbeece302932011-10-04 14:32:18 -070068
Elliott Hughese52e49b2012-04-02 16:05:44 -070069static uint32_t kCompilerDebugFlags = 0 | // Enable debug/testing modes
Bill Buzbeea114add2012-05-03 15:00:40 -070070 //(1 << kDebugDisplayMissingTargets) |
71 //(1 << kDebugVerbose) |
72 //(1 << kDebugDumpCFG) |
73 //(1 << kDebugSlowFieldPath) |
74 //(1 << kDebugSlowInvokePath) |
75 //(1 << kDebugSlowStringPath) |
76 //(1 << kDebugSlowestFieldPath) |
77 //(1 << kDebugSlowestStringPath) |
78 //(1 << kDebugExerciseResolveMethod) |
79 //(1 << kDebugVerifyDataflow) |
80 //(1 << kDebugShowMemoryUsage) |
81 //(1 << kDebugShowNops) |
82 //(1 << kDebugCountOpcodes) |
buzbeed1643e42012-09-05 14:06:51 -070083 //(1 << kDebugDumpCheckStats) |
buzbeead8f15e2012-06-18 14:49:45 -070084#if defined(ART_USE_QUICK_COMPILER)
85 //(1 << kDebugDumpBitcodeFile) |
Bill Buzbeec9f40dd2012-08-15 11:35:25 -070086 //(1 << kDebugVerifyBitcode) |
buzbeead8f15e2012-06-18 14:49:45 -070087#endif
Bill Buzbeea114add2012-05-03 15:00:40 -070088 0;
buzbeece302932011-10-04 14:32:18 -070089
buzbee31a4a6f2012-02-28 15:36:15 -080090inline bool contentIsInsn(const u2* codePtr) {
Bill Buzbeea114add2012-05-03 15:00:40 -070091 u2 instr = *codePtr;
92 Instruction::Code opcode = (Instruction::Code)(instr & 0xff);
buzbee67bf8852011-08-17 17:51:35 -070093
Bill Buzbeea114add2012-05-03 15:00:40 -070094 /*
95 * Since the low 8-bit in metadata may look like NOP, we need to check
96 * both the low and whole sub-word to determine whether it is code or data.
97 */
98 return (opcode != Instruction::NOP || instr == 0);
buzbee67bf8852011-08-17 17:51:35 -070099}
100
101/*
102 * Parse an instruction, return the length of the instruction
103 */
buzbee31a4a6f2012-02-28 15:36:15 -0800104inline int parseInsn(CompilationUnit* cUnit, const u2* codePtr,
Bill Buzbeea114add2012-05-03 15:00:40 -0700105 DecodedInstruction* decoded_instruction, bool printMe)
buzbee67bf8852011-08-17 17:51:35 -0700106{
Elliott Hughesadb8c672012-03-06 16:49:32 -0800107 // Don't parse instruction data
108 if (!contentIsInsn(codePtr)) {
109 return 0;
110 }
buzbee67bf8852011-08-17 17:51:35 -0700111
Elliott Hughesadb8c672012-03-06 16:49:32 -0800112 const Instruction* instruction = Instruction::At(codePtr);
113 *decoded_instruction = DecodedInstruction(instruction);
buzbee67bf8852011-08-17 17:51:35 -0700114
Elliott Hughesadb8c672012-03-06 16:49:32 -0800115 if (printMe) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700116 char* decodedString = oatGetDalvikDisassembly(cUnit, *decoded_instruction,
117 NULL);
118 LOG(INFO) << codePtr << ": 0x"
119 << std::hex << static_cast<int>(decoded_instruction->opcode)
Elliott Hughesadb8c672012-03-06 16:49:32 -0800120 << " " << decodedString;
121 }
122 return instruction->SizeInCodeUnits();
buzbee67bf8852011-08-17 17:51:35 -0700123}
124
125#define UNKNOWN_TARGET 0xffffffff
126
Elliott Hughesadb8c672012-03-06 16:49:32 -0800127inline bool isGoto(MIR* insn) {
128 switch (insn->dalvikInsn.opcode) {
129 case Instruction::GOTO:
130 case Instruction::GOTO_16:
131 case Instruction::GOTO_32:
132 return true;
133 default:
134 return false;
Bill Buzbeea114add2012-05-03 15:00:40 -0700135 }
buzbee67bf8852011-08-17 17:51:35 -0700136}
137
138/*
139 * Identify unconditional branch instructions
140 */
Elliott Hughesadb8c672012-03-06 16:49:32 -0800141inline bool isUnconditionalBranch(MIR* insn) {
142 switch (insn->dalvikInsn.opcode) {
143 case Instruction::RETURN_VOID:
144 case Instruction::RETURN:
145 case Instruction::RETURN_WIDE:
146 case Instruction::RETURN_OBJECT:
147 return true;
Bill Buzbeea114add2012-05-03 15:00:40 -0700148 default:
149 return isGoto(insn);
Elliott Hughesadb8c672012-03-06 16:49:32 -0800150 }
buzbee67bf8852011-08-17 17:51:35 -0700151}
152
153/* Split an existing block from the specified code offset into two */
buzbee31a4a6f2012-02-28 15:36:15 -0800154BasicBlock *splitBlock(CompilationUnit* cUnit, unsigned int codeOffset,
Bill Buzbeea114add2012-05-03 15:00:40 -0700155 BasicBlock* origBlock, BasicBlock** immedPredBlockP)
buzbee67bf8852011-08-17 17:51:35 -0700156{
Bill Buzbeea114add2012-05-03 15:00:40 -0700157 MIR* insn = origBlock->firstMIRInsn;
158 while (insn) {
159 if (insn->offset == codeOffset) break;
160 insn = insn->next;
161 }
162 if (insn == NULL) {
163 LOG(FATAL) << "Break split failed";
164 }
165 BasicBlock *bottomBlock = oatNewBB(cUnit, kDalvikByteCode,
166 cUnit->numBlocks++);
167 oatInsertGrowableList(cUnit, &cUnit->blockList, (intptr_t) bottomBlock);
buzbee67bf8852011-08-17 17:51:35 -0700168
Bill Buzbeea114add2012-05-03 15:00:40 -0700169 bottomBlock->startOffset = codeOffset;
170 bottomBlock->firstMIRInsn = insn;
171 bottomBlock->lastMIRInsn = origBlock->lastMIRInsn;
buzbee67bf8852011-08-17 17:51:35 -0700172
Bill Buzbeea114add2012-05-03 15:00:40 -0700173 /* Add it to the quick lookup cache */
174 cUnit->blockMap.Put(bottomBlock->startOffset, bottomBlock);
buzbee5b537102012-01-17 17:33:47 -0800175
Bill Buzbeea114add2012-05-03 15:00:40 -0700176 /* Handle the taken path */
177 bottomBlock->taken = origBlock->taken;
178 if (bottomBlock->taken) {
179 origBlock->taken = NULL;
180 oatDeleteGrowableList(bottomBlock->taken->predecessors,
buzbeeba938cb2012-02-03 14:47:55 -0800181 (intptr_t)origBlock);
Bill Buzbeea114add2012-05-03 15:00:40 -0700182 oatInsertGrowableList(cUnit, bottomBlock->taken->predecessors,
183 (intptr_t)bottomBlock);
184 }
185
186 /* Handle the fallthrough path */
Bill Buzbeea114add2012-05-03 15:00:40 -0700187 bottomBlock->fallThrough = origBlock->fallThrough;
188 origBlock->fallThrough = bottomBlock;
Bill Buzbeea114add2012-05-03 15:00:40 -0700189 oatInsertGrowableList(cUnit, bottomBlock->predecessors,
190 (intptr_t)origBlock);
191 if (bottomBlock->fallThrough) {
192 oatDeleteGrowableList(bottomBlock->fallThrough->predecessors,
193 (intptr_t)origBlock);
194 oatInsertGrowableList(cUnit, bottomBlock->fallThrough->predecessors,
195 (intptr_t)bottomBlock);
196 }
197
198 /* Handle the successor list */
199 if (origBlock->successorBlockList.blockListType != kNotUsed) {
200 bottomBlock->successorBlockList = origBlock->successorBlockList;
201 origBlock->successorBlockList.blockListType = kNotUsed;
202 GrowableListIterator iterator;
203
204 oatGrowableListIteratorInit(&bottomBlock->successorBlockList.blocks,
205 &iterator);
206 while (true) {
207 SuccessorBlockInfo *successorBlockInfo =
208 (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator);
209 if (successorBlockInfo == NULL) break;
210 BasicBlock *bb = successorBlockInfo->block;
211 oatDeleteGrowableList(bb->predecessors, (intptr_t)origBlock);
212 oatInsertGrowableList(cUnit, bb->predecessors, (intptr_t)bottomBlock);
buzbee67bf8852011-08-17 17:51:35 -0700213 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700214 }
buzbee67bf8852011-08-17 17:51:35 -0700215
Bill Buzbeea114add2012-05-03 15:00:40 -0700216 origBlock->lastMIRInsn = insn->prev;
buzbee67bf8852011-08-17 17:51:35 -0700217
Bill Buzbeea114add2012-05-03 15:00:40 -0700218 insn->prev->next = NULL;
219 insn->prev = NULL;
220 /*
221 * Update the immediate predecessor block pointer so that outgoing edges
222 * can be applied to the proper block.
223 */
224 if (immedPredBlockP) {
225 DCHECK_EQ(*immedPredBlockP, origBlock);
226 *immedPredBlockP = bottomBlock;
227 }
228 return bottomBlock;
buzbee67bf8852011-08-17 17:51:35 -0700229}
230
231/*
232 * Given a code offset, find out the block that starts with it. If the offset
buzbee9ab05de2012-01-18 15:43:48 -0800233 * is in the middle of an existing block, split it into two. If immedPredBlockP
234 * is not non-null and is the block being split, update *immedPredBlockP to
235 * point to the bottom block so that outgoing edges can be set up properly
236 * (by the caller)
buzbee5b537102012-01-17 17:33:47 -0800237 * Utilizes a map for fast lookup of the typical cases.
buzbee67bf8852011-08-17 17:51:35 -0700238 */
buzbee31a4a6f2012-02-28 15:36:15 -0800239BasicBlock *findBlock(CompilationUnit* cUnit, unsigned int codeOffset,
240 bool split, bool create, BasicBlock** immedPredBlockP)
buzbee67bf8852011-08-17 17:51:35 -0700241{
Bill Buzbeea114add2012-05-03 15:00:40 -0700242 GrowableList* blockList = &cUnit->blockList;
243 BasicBlock* bb;
244 unsigned int i;
245 SafeMap<unsigned int, BasicBlock*>::iterator it;
buzbee67bf8852011-08-17 17:51:35 -0700246
Bill Buzbeea114add2012-05-03 15:00:40 -0700247 it = cUnit->blockMap.find(codeOffset);
248 if (it != cUnit->blockMap.end()) {
249 return it->second;
250 } else if (!create) {
251 return NULL;
252 }
253
254 if (split) {
255 for (i = 0; i < blockList->numUsed; i++) {
256 bb = (BasicBlock *) blockList->elemList[i];
257 if (bb->blockType != kDalvikByteCode) continue;
258 /* Check if a branch jumps into the middle of an existing block */
259 if ((codeOffset > bb->startOffset) && (bb->lastMIRInsn != NULL) &&
260 (codeOffset <= bb->lastMIRInsn->offset)) {
261 BasicBlock *newBB = splitBlock(cUnit, codeOffset, bb,
262 bb == *immedPredBlockP ?
263 immedPredBlockP : NULL);
264 return newBB;
265 }
buzbee5b537102012-01-17 17:33:47 -0800266 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700267 }
buzbee5b537102012-01-17 17:33:47 -0800268
Bill Buzbeea114add2012-05-03 15:00:40 -0700269 /* Create a new one */
270 bb = oatNewBB(cUnit, kDalvikByteCode, cUnit->numBlocks++);
271 oatInsertGrowableList(cUnit, &cUnit->blockList, (intptr_t) bb);
272 bb->startOffset = codeOffset;
273 cUnit->blockMap.Put(bb->startOffset, bb);
274 return bb;
buzbee67bf8852011-08-17 17:51:35 -0700275}
276
buzbeef58c12c2012-07-03 15:06:29 -0700277/* Find existing block */
278BasicBlock* oatFindBlock(CompilationUnit* cUnit, unsigned int codeOffset)
279{
280 return findBlock(cUnit, codeOffset, false, false, NULL);
281}
282
buzbeead8f15e2012-06-18 14:49:45 -0700283/* Turn method name into a legal Linux file name */
284void oatReplaceSpecialChars(std::string& str)
285{
286 static const struct { const char before; const char after; } match[] =
287 {{'/','-'}, {';','#'}, {' ','#'}, {'$','+'},
288 {'(','@'}, {')','@'}, {'<','='}, {'>','='}};
289 for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) {
290 std::replace(str.begin(), str.end(), match[i].before, match[i].after);
291 }
292}
293
buzbee67bf8852011-08-17 17:51:35 -0700294/* Dump the CFG into a DOT graph */
295void oatDumpCFG(CompilationUnit* cUnit, const char* dirPrefix)
296{
Bill Buzbeea114add2012-05-03 15:00:40 -0700297 FILE* file;
buzbeead8f15e2012-06-18 14:49:45 -0700298 std::string fname(PrettyMethod(cUnit->method_idx, *cUnit->dex_file));
299 oatReplaceSpecialChars(fname);
300 fname = StringPrintf("%s%s%x.dot", dirPrefix, fname.c_str(),
301 cUnit->entryBlock->fallThrough->startOffset);
302 file = fopen(fname.c_str(), "w");
Bill Buzbeea114add2012-05-03 15:00:40 -0700303 if (file == NULL) {
304 return;
305 }
306 fprintf(file, "digraph G {\n");
307
308 fprintf(file, " rankdir=TB\n");
309
310 int numReachableBlocks = cUnit->numReachableBlocks;
311 int idx;
312 const GrowableList *blockList = &cUnit->blockList;
313
314 for (idx = 0; idx < numReachableBlocks; idx++) {
315 int blockIdx = cUnit->dfsOrder.elemList[idx];
316 BasicBlock *bb = (BasicBlock *) oatGrowableListGetElement(blockList,
317 blockIdx);
318 if (bb == NULL) break;
buzbeed1643e42012-09-05 14:06:51 -0700319 if (bb->blockType == kDead) continue;
Bill Buzbeea114add2012-05-03 15:00:40 -0700320 if (bb->blockType == kEntryBlock) {
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700321 fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700322 } else if (bb->blockType == kExitBlock) {
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700323 fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700324 } else if (bb->blockType == kDalvikByteCode) {
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700325 fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n",
326 bb->startOffset, bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700327 const MIR *mir;
328 fprintf(file, " {block id %d\\l}%s\\\n", bb->id,
329 bb->firstMIRInsn ? " | " : " ");
330 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
331 fprintf(file, " {%04x %s\\l}%s\\\n", mir->offset,
332 mir->ssaRep ? oatFullDisassembler(cUnit, mir) :
333 Instruction::Name(mir->dalvikInsn.opcode),
334 mir->next ? " | " : " ");
335 }
336 fprintf(file, " }\"];\n\n");
337 } else if (bb->blockType == kExceptionHandling) {
338 char blockName[BLOCK_NAME_LEN];
339
340 oatGetBlockName(bb, blockName);
341 fprintf(file, " %s [shape=invhouse];\n", blockName);
buzbee67bf8852011-08-17 17:51:35 -0700342 }
buzbee67bf8852011-08-17 17:51:35 -0700343
Bill Buzbeea114add2012-05-03 15:00:40 -0700344 char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
buzbee67bf8852011-08-17 17:51:35 -0700345
Bill Buzbeea114add2012-05-03 15:00:40 -0700346 if (bb->taken) {
347 oatGetBlockName(bb, blockName1);
348 oatGetBlockName(bb->taken, blockName2);
349 fprintf(file, " %s:s -> %s:n [style=dotted]\n",
350 blockName1, blockName2);
buzbee67bf8852011-08-17 17:51:35 -0700351 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700352 if (bb->fallThrough) {
353 oatGetBlockName(bb, blockName1);
354 oatGetBlockName(bb->fallThrough, blockName2);
355 fprintf(file, " %s:s -> %s:n\n", blockName1, blockName2);
356 }
357
358 if (bb->successorBlockList.blockListType != kNotUsed) {
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700359 fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n",
360 bb->startOffset, bb->id,
Bill Buzbeea114add2012-05-03 15:00:40 -0700361 (bb->successorBlockList.blockListType == kCatch) ?
362 "Mrecord" : "record");
363 GrowableListIterator iterator;
364 oatGrowableListIteratorInit(&bb->successorBlockList.blocks,
365 &iterator);
366 SuccessorBlockInfo *successorBlockInfo =
367 (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator);
368
369 int succId = 0;
370 while (true) {
371 if (successorBlockInfo == NULL) break;
372
373 BasicBlock *destBlock = successorBlockInfo->block;
374 SuccessorBlockInfo *nextSuccessorBlockInfo =
375 (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator);
376
377 fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n",
378 succId++,
379 successorBlockInfo->key,
380 destBlock->startOffset,
381 (nextSuccessorBlockInfo != NULL) ? " | " : " ");
382
383 successorBlockInfo = nextSuccessorBlockInfo;
384 }
385 fprintf(file, " }\"];\n\n");
386
387 oatGetBlockName(bb, blockName1);
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700388 fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n",
389 blockName1, bb->startOffset, bb->id);
Bill Buzbeea114add2012-05-03 15:00:40 -0700390
391 if (bb->successorBlockList.blockListType == kPackedSwitch ||
392 bb->successorBlockList.blockListType == kSparseSwitch) {
393
394 oatGrowableListIteratorInit(&bb->successorBlockList.blocks,
395 &iterator);
396
397 succId = 0;
398 while (true) {
399 SuccessorBlockInfo *successorBlockInfo = (SuccessorBlockInfo *)
400 oatGrowableListIteratorNext(&iterator);
401 if (successorBlockInfo == NULL) break;
402
403 BasicBlock *destBlock = successorBlockInfo->block;
404
405 oatGetBlockName(destBlock, blockName2);
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700406 fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->startOffset,
407 bb->id, succId++, blockName2);
Bill Buzbeea114add2012-05-03 15:00:40 -0700408 }
409 }
410 }
411 fprintf(file, "\n");
412
413 /* Display the dominator tree */
414 oatGetBlockName(bb, blockName1);
415 fprintf(file, " cfg%s [label=\"%s\", shape=none];\n",
416 blockName1, blockName1);
417 if (bb->iDom) {
418 oatGetBlockName(bb->iDom, blockName2);
419 fprintf(file, " cfg%s:s -> cfg%s:n\n\n", blockName2, blockName1);
420 }
421 }
422 fprintf(file, "}\n");
423 fclose(file);
buzbee67bf8852011-08-17 17:51:35 -0700424}
425
426/* Verify if all the successor is connected with all the claimed predecessors */
buzbee31a4a6f2012-02-28 15:36:15 -0800427bool verifyPredInfo(CompilationUnit* cUnit, BasicBlock* bb)
buzbee67bf8852011-08-17 17:51:35 -0700428{
Bill Buzbeea114add2012-05-03 15:00:40 -0700429 GrowableListIterator iter;
buzbee67bf8852011-08-17 17:51:35 -0700430
Bill Buzbeea114add2012-05-03 15:00:40 -0700431 oatGrowableListIteratorInit(bb->predecessors, &iter);
432 while (true) {
433 BasicBlock *predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter);
434 if (!predBB) break;
435 bool found = false;
436 if (predBB->taken == bb) {
437 found = true;
438 } else if (predBB->fallThrough == bb) {
439 found = true;
440 } else if (predBB->successorBlockList.blockListType != kNotUsed) {
441 GrowableListIterator iterator;
442 oatGrowableListIteratorInit(&predBB->successorBlockList.blocks,
443 &iterator);
444 while (true) {
445 SuccessorBlockInfo *successorBlockInfo = (SuccessorBlockInfo *)
446 oatGrowableListIteratorNext(&iterator);
447 if (successorBlockInfo == NULL) break;
448 BasicBlock *succBB = successorBlockInfo->block;
449 if (succBB == bb) {
buzbee67bf8852011-08-17 17:51:35 -0700450 found = true;
Bill Buzbeea114add2012-05-03 15:00:40 -0700451 break;
buzbee67bf8852011-08-17 17:51:35 -0700452 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700453 }
buzbee67bf8852011-08-17 17:51:35 -0700454 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700455 if (found == false) {
456 char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
457 oatGetBlockName(bb, blockName1);
458 oatGetBlockName(predBB, blockName2);
459 oatDumpCFG(cUnit, "/sdcard/cfg/");
460 LOG(FATAL) << "Successor " << blockName1 << "not found from "
461 << blockName2;
462 }
463 }
464 return true;
buzbee67bf8852011-08-17 17:51:35 -0700465}
466
467/* Identify code range in try blocks and set up the empty catch blocks */
buzbee31a4a6f2012-02-28 15:36:15 -0800468void processTryCatchBlocks(CompilationUnit* cUnit)
buzbee67bf8852011-08-17 17:51:35 -0700469{
Bill Buzbeea114add2012-05-03 15:00:40 -0700470 const DexFile::CodeItem* code_item = cUnit->code_item;
471 int triesSize = code_item->tries_size_;
472 int offset;
buzbee67bf8852011-08-17 17:51:35 -0700473
Bill Buzbeea114add2012-05-03 15:00:40 -0700474 if (triesSize == 0) {
475 return;
476 }
477
478 ArenaBitVector* tryBlockAddr = cUnit->tryBlockAddr;
479
480 for (int i = 0; i < triesSize; i++) {
481 const DexFile::TryItem* pTry =
482 DexFile::GetTryItems(*code_item, i);
483 int startOffset = pTry->start_addr_;
484 int endOffset = startOffset + pTry->insn_count_;
485 for (offset = startOffset; offset < endOffset; offset++) {
486 oatSetBit(cUnit, tryBlockAddr, offset);
buzbee67bf8852011-08-17 17:51:35 -0700487 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700488 }
buzbee67bf8852011-08-17 17:51:35 -0700489
Bill Buzbeea114add2012-05-03 15:00:40 -0700490 // Iterate over each of the handlers to enqueue the empty Catch blocks
491 const byte* handlers_ptr = DexFile::GetCatchHandlerData(*code_item, 0);
492 uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr);
493 for (uint32_t idx = 0; idx < handlers_size; idx++) {
494 CatchHandlerIterator iterator(handlers_ptr);
495 for (; iterator.HasNext(); iterator.Next()) {
496 uint32_t address = iterator.GetHandlerAddress();
497 findBlock(cUnit, address, false /* split */, true /*create*/,
498 /* immedPredBlockP */ NULL);
buzbee67bf8852011-08-17 17:51:35 -0700499 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700500 handlers_ptr = iterator.EndDataPointer();
501 }
buzbee67bf8852011-08-17 17:51:35 -0700502}
503
Elliott Hughesadb8c672012-03-06 16:49:32 -0800504/* Process instructions with the kBranch flag */
buzbee31a4a6f2012-02-28 15:36:15 -0800505BasicBlock* processCanBranch(CompilationUnit* cUnit, BasicBlock* curBlock,
Bill Buzbeea114add2012-05-03 15:00:40 -0700506 MIR* insn, int curOffset, int width, int flags,
507 const u2* codePtr, const u2* codeEnd)
buzbee67bf8852011-08-17 17:51:35 -0700508{
Bill Buzbeea114add2012-05-03 15:00:40 -0700509 int target = curOffset;
510 switch (insn->dalvikInsn.opcode) {
511 case Instruction::GOTO:
512 case Instruction::GOTO_16:
513 case Instruction::GOTO_32:
514 target += (int) insn->dalvikInsn.vA;
515 break;
516 case Instruction::IF_EQ:
517 case Instruction::IF_NE:
518 case Instruction::IF_LT:
519 case Instruction::IF_GE:
520 case Instruction::IF_GT:
521 case Instruction::IF_LE:
buzbee0967a252012-09-14 10:43:54 -0700522 curBlock->conditionalBranch = true;
Bill Buzbeea114add2012-05-03 15:00:40 -0700523 target += (int) insn->dalvikInsn.vC;
524 break;
525 case Instruction::IF_EQZ:
526 case Instruction::IF_NEZ:
527 case Instruction::IF_LTZ:
528 case Instruction::IF_GEZ:
529 case Instruction::IF_GTZ:
530 case Instruction::IF_LEZ:
buzbee0967a252012-09-14 10:43:54 -0700531 curBlock->conditionalBranch = true;
Bill Buzbeea114add2012-05-03 15:00:40 -0700532 target += (int) insn->dalvikInsn.vB;
533 break;
534 default:
535 LOG(FATAL) << "Unexpected opcode(" << (int)insn->dalvikInsn.opcode
536 << ") with kBranch set";
537 }
538 BasicBlock *takenBlock = findBlock(cUnit, target,
539 /* split */
540 true,
541 /* create */
542 true,
543 /* immedPredBlockP */
544 &curBlock);
545 curBlock->taken = takenBlock;
546 oatInsertGrowableList(cUnit, takenBlock->predecessors, (intptr_t)curBlock);
buzbee67bf8852011-08-17 17:51:35 -0700547
Bill Buzbeea114add2012-05-03 15:00:40 -0700548 /* Always terminate the current block for conditional branches */
549 if (flags & Instruction::kContinue) {
550 BasicBlock *fallthroughBlock = findBlock(cUnit,
551 curOffset + width,
552 /*
553 * If the method is processed
554 * in sequential order from the
555 * beginning, we don't need to
556 * specify split for continue
557 * blocks. However, this
558 * routine can be called by
559 * compileLoop, which starts
560 * parsing the method from an
561 * arbitrary address in the
562 * method body.
563 */
564 true,
565 /* create */
566 true,
567 /* immedPredBlockP */
568 &curBlock);
569 curBlock->fallThrough = fallthroughBlock;
570 oatInsertGrowableList(cUnit, fallthroughBlock->predecessors,
571 (intptr_t)curBlock);
572 } else if (codePtr < codeEnd) {
573 /* Create a fallthrough block for real instructions (incl. NOP) */
574 if (contentIsInsn(codePtr)) {
575 findBlock(cUnit, curOffset + width,
576 /* split */
577 false,
578 /* create */
579 true,
580 /* immedPredBlockP */
581 NULL);
buzbee67bf8852011-08-17 17:51:35 -0700582 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700583 }
584 return curBlock;
buzbee67bf8852011-08-17 17:51:35 -0700585}
586
Elliott Hughesadb8c672012-03-06 16:49:32 -0800587/* Process instructions with the kSwitch flag */
buzbee31a4a6f2012-02-28 15:36:15 -0800588void processCanSwitch(CompilationUnit* cUnit, BasicBlock* curBlock,
589 MIR* insn, int curOffset, int width, int flags)
buzbee67bf8852011-08-17 17:51:35 -0700590{
Bill Buzbeea114add2012-05-03 15:00:40 -0700591 u2* switchData= (u2 *) (cUnit->insns + curOffset + insn->dalvikInsn.vB);
592 int size;
593 int* keyTable;
594 int* targetTable;
595 int i;
596 int firstKey;
buzbee67bf8852011-08-17 17:51:35 -0700597
Bill Buzbeea114add2012-05-03 15:00:40 -0700598 /*
599 * Packed switch data format:
600 * ushort ident = 0x0100 magic value
601 * ushort size number of entries in the table
602 * int first_key first (and lowest) switch case value
603 * int targets[size] branch targets, relative to switch opcode
604 *
605 * Total size is (4+size*2) 16-bit code units.
606 */
607 if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) {
608 DCHECK_EQ(static_cast<int>(switchData[0]),
609 static_cast<int>(Instruction::kPackedSwitchSignature));
610 size = switchData[1];
611 firstKey = switchData[2] | (switchData[3] << 16);
612 targetTable = (int *) &switchData[4];
613 keyTable = NULL; // Make the compiler happy
614 /*
615 * Sparse switch data format:
616 * ushort ident = 0x0200 magic value
617 * ushort size number of entries in the table; > 0
618 * int keys[size] keys, sorted low-to-high; 32-bit aligned
619 * int targets[size] branch targets, relative to switch opcode
620 *
621 * Total size is (2+size*4) 16-bit code units.
622 */
623 } else {
624 DCHECK_EQ(static_cast<int>(switchData[0]),
625 static_cast<int>(Instruction::kSparseSwitchSignature));
626 size = switchData[1];
627 keyTable = (int *) &switchData[2];
628 targetTable = (int *) &switchData[2 + size*2];
629 firstKey = 0; // To make the compiler happy
630 }
buzbee67bf8852011-08-17 17:51:35 -0700631
Bill Buzbeea114add2012-05-03 15:00:40 -0700632 if (curBlock->successorBlockList.blockListType != kNotUsed) {
633 LOG(FATAL) << "Successor block list already in use: "
634 << (int)curBlock->successorBlockList.blockListType;
635 }
636 curBlock->successorBlockList.blockListType =
637 (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ?
638 kPackedSwitch : kSparseSwitch;
639 oatInitGrowableList(cUnit, &curBlock->successorBlockList.blocks, size,
640 kListSuccessorBlocks);
641
642 for (i = 0; i < size; i++) {
643 BasicBlock *caseBlock = findBlock(cUnit, curOffset + targetTable[i],
644 /* split */
645 true,
646 /* create */
647 true,
648 /* immedPredBlockP */
649 &curBlock);
650 SuccessorBlockInfo *successorBlockInfo =
651 (SuccessorBlockInfo *) oatNew(cUnit, sizeof(SuccessorBlockInfo),
652 false, kAllocSuccessor);
653 successorBlockInfo->block = caseBlock;
654 successorBlockInfo->key =
Elliott Hughesadb8c672012-03-06 16:49:32 -0800655 (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ?
Bill Buzbeea114add2012-05-03 15:00:40 -0700656 firstKey + i : keyTable[i];
657 oatInsertGrowableList(cUnit, &curBlock->successorBlockList.blocks,
658 (intptr_t) successorBlockInfo);
659 oatInsertGrowableList(cUnit, caseBlock->predecessors,
buzbeeba938cb2012-02-03 14:47:55 -0800660 (intptr_t)curBlock);
Bill Buzbeea114add2012-05-03 15:00:40 -0700661 }
662
663 /* Fall-through case */
664 BasicBlock* fallthroughBlock = findBlock(cUnit,
665 curOffset + width,
666 /* split */
667 false,
668 /* create */
669 true,
670 /* immedPredBlockP */
671 NULL);
672 curBlock->fallThrough = fallthroughBlock;
673 oatInsertGrowableList(cUnit, fallthroughBlock->predecessors,
674 (intptr_t)curBlock);
buzbee67bf8852011-08-17 17:51:35 -0700675}
676
Elliott Hughesadb8c672012-03-06 16:49:32 -0800677/* Process instructions with the kThrow flag */
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700678BasicBlock* processCanThrow(CompilationUnit* cUnit, BasicBlock* curBlock,
679 MIR* insn, int curOffset, int width, int flags,
680 ArenaBitVector* tryBlockAddr, const u2* codePtr,
681 const u2* codeEnd)
buzbee67bf8852011-08-17 17:51:35 -0700682{
Bill Buzbeea114add2012-05-03 15:00:40 -0700683 const DexFile::CodeItem* code_item = cUnit->code_item;
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700684 bool inTryBlock = oatIsBitSet(tryBlockAddr, curOffset);
buzbee67bf8852011-08-17 17:51:35 -0700685
Bill Buzbeea114add2012-05-03 15:00:40 -0700686 /* In try block */
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700687 if (inTryBlock) {
Bill Buzbeea114add2012-05-03 15:00:40 -0700688 CatchHandlerIterator iterator(*code_item, curOffset);
buzbee67bf8852011-08-17 17:51:35 -0700689
Bill Buzbeea114add2012-05-03 15:00:40 -0700690 if (curBlock->successorBlockList.blockListType != kNotUsed) {
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700691 LOG(INFO) << PrettyMethod(cUnit->method_idx, *cUnit->dex_file);
Bill Buzbeea114add2012-05-03 15:00:40 -0700692 LOG(FATAL) << "Successor block list already in use: "
693 << (int)curBlock->successorBlockList.blockListType;
buzbee67bf8852011-08-17 17:51:35 -0700694 }
695
Bill Buzbeea114add2012-05-03 15:00:40 -0700696 curBlock->successorBlockList.blockListType = kCatch;
697 oatInitGrowableList(cUnit, &curBlock->successorBlockList.blocks, 2,
698 kListSuccessorBlocks);
699
700 for (;iterator.HasNext(); iterator.Next()) {
701 BasicBlock *catchBlock = findBlock(cUnit, iterator.GetHandlerAddress(),
702 false /* split*/,
703 false /* creat */,
704 NULL /* immedPredBlockP */);
705 catchBlock->catchEntry = true;
706 SuccessorBlockInfo *successorBlockInfo = (SuccessorBlockInfo *)
707 oatNew(cUnit, sizeof(SuccessorBlockInfo), false, kAllocSuccessor);
708 successorBlockInfo->block = catchBlock;
709 successorBlockInfo->key = iterator.GetHandlerTypeIndex();
710 oatInsertGrowableList(cUnit, &curBlock->successorBlockList.blocks,
711 (intptr_t) successorBlockInfo);
712 oatInsertGrowableList(cUnit, catchBlock->predecessors,
713 (intptr_t)curBlock);
buzbee67bf8852011-08-17 17:51:35 -0700714 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700715 } else {
716 BasicBlock *ehBlock = oatNewBB(cUnit, kExceptionHandling,
717 cUnit->numBlocks++);
718 curBlock->taken = ehBlock;
719 oatInsertGrowableList(cUnit, &cUnit->blockList, (intptr_t) ehBlock);
720 ehBlock->startOffset = curOffset;
721 oatInsertGrowableList(cUnit, ehBlock->predecessors, (intptr_t)curBlock);
722 }
723
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700724 if (insn->dalvikInsn.opcode == Instruction::THROW){
buzbee0967a252012-09-14 10:43:54 -0700725 curBlock->explicitThrow = true;
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700726 if ((codePtr < codeEnd) && contentIsInsn(codePtr)) {
727 // Force creation of new block following THROW via side-effect
728 findBlock(cUnit, curOffset + width, /* split */ false,
729 /* create */ true, /* immedPredBlockP */ NULL);
730 }
731 if (!inTryBlock) {
732 // Don't split a THROW that can't rethrow - we're done.
733 return curBlock;
Bill Buzbeea114add2012-05-03 15:00:40 -0700734 }
735 }
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700736
737 /*
738 * Split the potentially-throwing instruction into two parts.
739 * The first half will be a pseudo-op that captures the exception
740 * edges and terminates the basic block. It always falls through.
741 * Then, create a new basic block that begins with the throwing instruction
742 * (minus exceptions). Note: this new basic block must NOT be entered into
743 * the blockMap. If the potentially-throwing instruction is the target of a
744 * future branch, we need to find the check psuedo half. The new
745 * basic block containing the work portion of the instruction should
746 * only be entered via fallthrough from the block containing the
747 * pseudo exception edge MIR. Note also that this new block is
748 * not automatically terminated after the work portion, and may
749 * contain following instructions.
750 */
751 BasicBlock *newBlock = oatNewBB(cUnit, kDalvikByteCode, cUnit->numBlocks++);
752 oatInsertGrowableList(cUnit, &cUnit->blockList, (intptr_t)newBlock);
753 newBlock->startOffset = insn->offset;
754 curBlock->fallThrough = newBlock;
755 oatInsertGrowableList(cUnit, newBlock->predecessors, (intptr_t)curBlock);
756 MIR* newInsn = (MIR*)oatNew(cUnit, sizeof(MIR), true, kAllocMIR);
757 *newInsn = *insn;
758 insn->dalvikInsn.opcode =
759 static_cast<Instruction::Code>(kMirOpCheck);
760 // Associate the two halves
761 insn->meta.throwInsn = newInsn;
762 newInsn->meta.throwInsn = insn;
763 oatAppendMIR(newBlock, newInsn);
764 return newBlock;
buzbee67bf8852011-08-17 17:51:35 -0700765}
766
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800767void oatInit(CompilationUnit* cUnit, const Compiler& compiler) {
768 if (!oatArchInit()) {
769 LOG(FATAL) << "Failed to initialize oat";
770 }
771 if (!oatHeapInit(cUnit)) {
772 LOG(FATAL) << "Failed to initialize oat heap";
773 }
774}
775
buzbeeabc4c6b2012-08-23 08:17:15 -0700776CompiledMethod* compileMethod(Compiler& compiler,
777 const DexFile::CodeItem* code_item,
778 uint32_t access_flags, InvokeType invoke_type,
779 uint32_t method_idx, jobject class_loader,
780 const DexFile& dex_file
781#if defined(ART_USE_QUICK_COMPILER)
782 , llvm::Module* module,
783 llvm::LLVMContext* context,
784 greenland::IntrinsicHelper* intrinsic_helper,
785 greenland::IRBuilder* irb,
786 bool gbcOnly
787#endif
788 )
buzbee67bf8852011-08-17 17:51:35 -0700789{
Bill Buzbeea114add2012-05-03 15:00:40 -0700790 VLOG(compiler) << "Compiling " << PrettyMethod(method_idx, dex_file) << "...";
Brian Carlstrom94496d32011-08-22 09:22:47 -0700791
Bill Buzbeea114add2012-05-03 15:00:40 -0700792 const u2* codePtr = code_item->insns_;
793 const u2* codeEnd = code_item->insns_ + code_item->insns_size_in_code_units_;
794 int numBlocks = 0;
795 unsigned int curOffset = 0;
buzbee67bf8852011-08-17 17:51:35 -0700796
Bill Buzbeea114add2012-05-03 15:00:40 -0700797 ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
798 UniquePtr<CompilationUnit> cUnit(new CompilationUnit);
buzbeeba938cb2012-02-03 14:47:55 -0800799
Bill Buzbeea114add2012-05-03 15:00:40 -0700800 oatInit(cUnit.get(), compiler);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -0800801
Bill Buzbeea114add2012-05-03 15:00:40 -0700802 cUnit->compiler = &compiler;
803 cUnit->class_linker = class_linker;
804 cUnit->dex_file = &dex_file;
Bill Buzbeea114add2012-05-03 15:00:40 -0700805 cUnit->method_idx = method_idx;
806 cUnit->code_item = code_item;
807 cUnit->access_flags = access_flags;
Ian Rogers08f753d2012-08-24 14:35:25 -0700808 cUnit->invoke_type = invoke_type;
Bill Buzbeea114add2012-05-03 15:00:40 -0700809 cUnit->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx));
810 cUnit->instructionSet = compiler.GetInstructionSet();
811 cUnit->insns = code_item->insns_;
812 cUnit->insnsSize = code_item->insns_size_in_code_units_;
813 cUnit->numIns = code_item->ins_size_;
814 cUnit->numRegs = code_item->registers_size_ - cUnit->numIns;
815 cUnit->numOuts = code_item->outs_size_;
buzbee2cfc6392012-05-07 14:51:40 -0700816#if defined(ART_USE_QUICK_COMPILER)
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700817 DCHECK((cUnit->instructionSet == kThumb2) ||
818 (cUnit->instructionSet == kX86) ||
819 (cUnit->instructionSet == kMips));
buzbeeabc4c6b2012-08-23 08:17:15 -0700820 cUnit->module = module;
821 cUnit->context = context;
822 cUnit->intrinsic_helper = intrinsic_helper;
823 cUnit->irb = irb;
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700824 if (cUnit->instructionSet == kThumb2) {
825 // TODO: remove this once x86 is tested
buzbee85eee022012-07-16 22:12:38 -0700826 cUnit->genBitcode = true;
827 }
buzbee2a83e8f2012-07-13 16:42:30 -0700828#endif
Bill Buzbeea114add2012-05-03 15:00:40 -0700829 /* Adjust this value accordingly once inlining is performed */
830 cUnit->numDalvikRegisters = code_item->registers_size_;
831 // TODO: set this from command line
832 cUnit->compilerFlipMatch = false;
833 bool useMatch = !cUnit->compilerMethodMatch.empty();
834 bool match = useMatch && (cUnit->compilerFlipMatch ^
835 (PrettyMethod(method_idx, dex_file).find(cUnit->compilerMethodMatch) !=
836 std::string::npos));
837 if (!useMatch || match) {
838 cUnit->disableOpt = kCompilerOptimizerDisableFlags;
839 cUnit->enableDebug = kCompilerDebugFlags;
840 cUnit->printMe = VLOG_IS_ON(compiler) ||
841 (cUnit->enableDebug & (1 << kDebugVerbose));
842 }
buzbee2cfc6392012-05-07 14:51:40 -0700843#if defined(ART_USE_QUICK_COMPILER)
buzbee6969d502012-06-15 16:40:31 -0700844 if (cUnit->genBitcode) {
Bill Buzbeec9f40dd2012-08-15 11:35:25 -0700845 //cUnit->enableDebug |= (1 << kDebugVerifyBitcode);
buzbee2a83e8f2012-07-13 16:42:30 -0700846 //cUnit->printMe = true;
847 //cUnit->enableDebug |= (1 << kDebugDumpBitcodeFile);
buzbee6969d502012-06-15 16:40:31 -0700848 }
buzbee2cfc6392012-05-07 14:51:40 -0700849#endif
jeffhao7fbee072012-08-24 17:56:54 -0700850 if (cUnit->instructionSet == kMips) {
851 // Disable some optimizations for mips for now
852 cUnit->disableOpt |= (
853 (1 << kLoadStoreElimination) |
854 (1 << kLoadHoisting) |
855 (1 << kSuppressLoads) |
856 (1 << kNullCheckElimination) |
857 (1 << kPromoteRegs) |
858 (1 << kTrackLiveTemps) |
859 (1 << kSkipLargeMethodOptimization) |
860 (1 << kSafeOptimizations) |
861 (1 << kBBOpt) |
862 (1 << kMatch) |
863 (1 << kPromoteCompilerTemps));
864 }
Bill Buzbeea114add2012-05-03 15:00:40 -0700865 /* Are we generating code for the debugger? */
866 if (compiler.IsDebuggingSupported()) {
867 cUnit->genDebugger = true;
868 // Yes, disable most optimizations
869 cUnit->disableOpt |= (
870 (1 << kLoadStoreElimination) |
871 (1 << kLoadHoisting) |
872 (1 << kSuppressLoads) |
873 (1 << kPromoteRegs) |
874 (1 << kBBOpt) |
875 (1 << kMatch) |
876 (1 << kTrackLiveTemps));
877 }
878
879 /* Gathering opcode stats? */
880 if (kCompilerDebugFlags & (1 << kDebugCountOpcodes)) {
881 cUnit->opcodeCount = (int*)oatNew(cUnit.get(),
882 kNumPackedOpcodes * sizeof(int), true, kAllocMisc);
883 }
884
885 /* Assume non-throwing leaf */
886 cUnit->attrs = (METHOD_IS_LEAF | METHOD_IS_THROW_FREE);
887
888 /* Initialize the block list, estimate size based on insnsSize */
889 oatInitGrowableList(cUnit.get(), &cUnit->blockList, cUnit->insnsSize,
890 kListBlockList);
891
892 /* Initialize the switchTables list */
893 oatInitGrowableList(cUnit.get(), &cUnit->switchTables, 4,
894 kListSwitchTables);
895
896 /* Intialize the fillArrayData list */
897 oatInitGrowableList(cUnit.get(), &cUnit->fillArrayData, 4,
898 kListFillArrayData);
899
900 /* Intialize the throwLaunchpads list, estimate size based on insnsSize */
901 oatInitGrowableList(cUnit.get(), &cUnit->throwLaunchpads, cUnit->insnsSize,
902 kListThrowLaunchPads);
903
904 /* Intialize the instrinsicLaunchpads list */
905 oatInitGrowableList(cUnit.get(), &cUnit->intrinsicLaunchpads, 4,
906 kListMisc);
907
908
909 /* Intialize the suspendLaunchpads list */
910 oatInitGrowableList(cUnit.get(), &cUnit->suspendLaunchpads, 2048,
911 kListSuspendLaunchPads);
912
913 /* Allocate the bit-vector to track the beginning of basic blocks */
914 ArenaBitVector *tryBlockAddr = oatAllocBitVector(cUnit.get(),
915 cUnit->insnsSize,
916 true /* expandable */);
917 cUnit->tryBlockAddr = tryBlockAddr;
918
919 /* Create the default entry and exit blocks and enter them to the list */
920 BasicBlock *entryBlock = oatNewBB(cUnit.get(), kEntryBlock, numBlocks++);
921 BasicBlock *exitBlock = oatNewBB(cUnit.get(), kExitBlock, numBlocks++);
922
923 cUnit->entryBlock = entryBlock;
924 cUnit->exitBlock = exitBlock;
925
926 oatInsertGrowableList(cUnit.get(), &cUnit->blockList, (intptr_t) entryBlock);
927 oatInsertGrowableList(cUnit.get(), &cUnit->blockList, (intptr_t) exitBlock);
928
929 /* Current block to record parsed instructions */
930 BasicBlock *curBlock = oatNewBB(cUnit.get(), kDalvikByteCode, numBlocks++);
931 curBlock->startOffset = 0;
932 oatInsertGrowableList(cUnit.get(), &cUnit->blockList, (intptr_t) curBlock);
933 /* Add first block to the fast lookup cache */
934 cUnit->blockMap.Put(curBlock->startOffset, curBlock);
935 entryBlock->fallThrough = curBlock;
936 oatInsertGrowableList(cUnit.get(), curBlock->predecessors,
937 (intptr_t)entryBlock);
938
939 /*
940 * Store back the number of blocks since new blocks may be created of
941 * accessing cUnit.
942 */
943 cUnit->numBlocks = numBlocks;
944
945 /* Identify code range in try blocks and set up the empty catch blocks */
946 processTryCatchBlocks(cUnit.get());
947
948 /* Set up for simple method detection */
949 int numPatterns = sizeof(specialPatterns)/sizeof(specialPatterns[0]);
950 bool livePattern = (numPatterns > 0) && !(cUnit->disableOpt & (1 << kMatch));
Elliott Hughesabe64aa2012-05-30 17:34:45 -0700951 bool* deadPattern = (bool*)oatNew(cUnit.get(), sizeof(bool) * numPatterns, true,
Bill Buzbeea114add2012-05-03 15:00:40 -0700952 kAllocMisc);
953 SpecialCaseHandler specialCase = kNoHandler;
954 int patternPos = 0;
955
956 /* Parse all instructions and put them into containing basic blocks */
957 while (codePtr < codeEnd) {
958 MIR *insn = (MIR *) oatNew(cUnit.get(), sizeof(MIR), true, kAllocMIR);
959 insn->offset = curOffset;
960 int width = parseInsn(cUnit.get(), codePtr, &insn->dalvikInsn, false);
961 insn->width = width;
962 Instruction::Code opcode = insn->dalvikInsn.opcode;
963 if (cUnit->opcodeCount != NULL) {
964 cUnit->opcodeCount[static_cast<int>(opcode)]++;
buzbee44b412b2012-02-04 08:50:53 -0800965 }
966
Bill Buzbeea114add2012-05-03 15:00:40 -0700967 /* Terminate when the data section is seen */
968 if (width == 0)
969 break;
970
971 /* Possible simple method? */
972 if (livePattern) {
973 livePattern = false;
974 specialCase = kNoHandler;
975 for (int i = 0; i < numPatterns; i++) {
976 if (!deadPattern[i]) {
977 if (specialPatterns[i].opcodes[patternPos] == opcode) {
978 livePattern = true;
979 specialCase = specialPatterns[i].handlerCode;
980 } else {
981 deadPattern[i] = true;
982 }
983 }
984 }
985 patternPos++;
buzbeea7c12682012-03-19 13:13:53 -0700986 }
987
Bill Buzbeea114add2012-05-03 15:00:40 -0700988 oatAppendMIR(curBlock, insn);
buzbeecefd1872011-09-09 09:59:52 -0700989
Bill Buzbeea114add2012-05-03 15:00:40 -0700990 codePtr += width;
991 int flags = Instruction::Flags(insn->dalvikInsn.opcode);
buzbee67bf8852011-08-17 17:51:35 -0700992
Bill Buzbeea114add2012-05-03 15:00:40 -0700993 int dfFlags = oatDataFlowAttributes[insn->dalvikInsn.opcode];
buzbee67bf8852011-08-17 17:51:35 -0700994
Bill Buzbeea114add2012-05-03 15:00:40 -0700995 if (dfFlags & DF_HAS_DEFS) {
buzbeebff24652012-05-06 16:22:05 -0700996 cUnit->defCount += (dfFlags & DF_A_WIDE) ? 2 : 1;
Bill Buzbeea114add2012-05-03 15:00:40 -0700997 }
buzbee67bf8852011-08-17 17:51:35 -0700998
Bill Buzbeea114add2012-05-03 15:00:40 -0700999 if (flags & Instruction::kBranch) {
1000 curBlock = processCanBranch(cUnit.get(), curBlock, insn, curOffset,
1001 width, flags, codePtr, codeEnd);
1002 } else if (flags & Instruction::kReturn) {
1003 curBlock->fallThrough = exitBlock;
1004 oatInsertGrowableList(cUnit.get(), exitBlock->predecessors,
1005 (intptr_t)curBlock);
1006 /*
1007 * Terminate the current block if there are instructions
1008 * afterwards.
1009 */
1010 if (codePtr < codeEnd) {
1011 /*
1012 * Create a fallthrough block for real instructions
1013 * (incl. NOP).
1014 */
1015 if (contentIsInsn(codePtr)) {
1016 findBlock(cUnit.get(), curOffset + width,
1017 /* split */
1018 false,
1019 /* create */
1020 true,
1021 /* immedPredBlockP */
1022 NULL);
1023 }
1024 }
1025 } else if (flags & Instruction::kThrow) {
Bill Buzbeec9f40dd2012-08-15 11:35:25 -07001026 curBlock = processCanThrow(cUnit.get(), curBlock, insn, curOffset,
1027 width, flags, tryBlockAddr, codePtr, codeEnd);
Bill Buzbeea114add2012-05-03 15:00:40 -07001028 } else if (flags & Instruction::kSwitch) {
1029 processCanSwitch(cUnit.get(), curBlock, insn, curOffset, width, flags);
1030 }
1031 curOffset += width;
1032 BasicBlock *nextBlock = findBlock(cUnit.get(), curOffset,
1033 /* split */
1034 false,
1035 /* create */
1036 false,
1037 /* immedPredBlockP */
1038 NULL);
1039 if (nextBlock) {
1040 /*
1041 * The next instruction could be the target of a previously parsed
1042 * forward branch so a block is already created. If the current
1043 * instruction is not an unconditional branch, connect them through
1044 * the fall-through link.
1045 */
1046 DCHECK(curBlock->fallThrough == NULL ||
1047 curBlock->fallThrough == nextBlock ||
1048 curBlock->fallThrough == exitBlock);
buzbee5ade1d22011-09-09 14:44:52 -07001049
Bill Buzbeea114add2012-05-03 15:00:40 -07001050 if ((curBlock->fallThrough == NULL) && (flags & Instruction::kContinue)) {
1051 curBlock->fallThrough = nextBlock;
1052 oatInsertGrowableList(cUnit.get(), nextBlock->predecessors,
1053 (intptr_t)curBlock);
1054 }
1055 curBlock = nextBlock;
1056 }
1057 }
buzbeefc9e6fa2012-03-23 15:14:29 -07001058
Bill Buzbeea114add2012-05-03 15:00:40 -07001059 if (!(cUnit->disableOpt & (1 << kSkipLargeMethodOptimization))) {
1060 if ((cUnit->numBlocks > MANY_BLOCKS) ||
1061 ((cUnit->numBlocks > MANY_BLOCKS_INITIALIZER) &&
1062 PrettyMethod(method_idx, dex_file, false).find("init>") !=
1063 std::string::npos)) {
1064 cUnit->qdMode = true;
1065 }
1066 }
buzbeefc9e6fa2012-03-23 15:14:29 -07001067
Bill Buzbeea114add2012-05-03 15:00:40 -07001068 if (cUnit->qdMode) {
buzbeed1643e42012-09-05 14:06:51 -07001069#if !defined(ART_USE_QUICK_COMPILER)
1070 // Bitcode generation requires full dataflow analysis
Bill Buzbeea114add2012-05-03 15:00:40 -07001071 cUnit->disableDataflow = true;
buzbeed1643e42012-09-05 14:06:51 -07001072#endif
Bill Buzbeea114add2012-05-03 15:00:40 -07001073 // Disable optimization which require dataflow/ssa
1074 cUnit->disableOpt |=
buzbeed1643e42012-09-05 14:06:51 -07001075#if !defined(ART_USE_QUICK_COMPILER)
Bill Buzbeea114add2012-05-03 15:00:40 -07001076 (1 << kNullCheckElimination) |
buzbeed1643e42012-09-05 14:06:51 -07001077#endif
Bill Buzbeea114add2012-05-03 15:00:40 -07001078 (1 << kBBOpt) |
1079 (1 << kPromoteRegs);
1080 if (cUnit->printMe) {
1081 LOG(INFO) << "QD mode enabled: "
1082 << PrettyMethod(method_idx, dex_file)
1083 << " too big: " << cUnit->numBlocks;
1084 }
1085 }
buzbeec1f45042011-09-21 16:03:19 -07001086
Bill Buzbeea114add2012-05-03 15:00:40 -07001087 if (cUnit->printMe) {
1088 oatDumpCompilationUnit(cUnit.get());
1089 }
buzbee67bf8852011-08-17 17:51:35 -07001090
buzbee0967a252012-09-14 10:43:54 -07001091 /* Do a code layout pass */
1092 oatMethodCodeLayout(cUnit.get());
1093
Bill Buzbeea114add2012-05-03 15:00:40 -07001094 if (cUnit->enableDebug & (1 << kDebugVerifyDataflow)) {
1095 /* Verify if all blocks are connected as claimed */
1096 oatDataFlowAnalysisDispatcher(cUnit.get(), verifyPredInfo, kAllNodes,
1097 false /* isIterative */);
1098 }
buzbee67bf8852011-08-17 17:51:35 -07001099
Bill Buzbeea114add2012-05-03 15:00:40 -07001100 /* Perform SSA transformation for the whole method */
1101 oatMethodSSATransformation(cUnit.get());
buzbee67bf8852011-08-17 17:51:35 -07001102
buzbee2cfc6392012-05-07 14:51:40 -07001103 /* Do constant propagation */
1104 // TODO: Probably need to make these expandable to support new ssa names
1105 // introducted during MIR optimization passes
1106 cUnit->isConstantV = oatAllocBitVector(cUnit.get(), cUnit->numSSARegs,
1107 false /* not expandable */);
1108 cUnit->constantValues =
1109 (int*)oatNew(cUnit.get(), sizeof(int) * cUnit->numSSARegs, true,
1110 kAllocDFInfo);
1111 oatDataFlowAnalysisDispatcher(cUnit.get(), oatDoConstantPropagation,
1112 kAllNodes,
1113 false /* isIterative */);
1114
Bill Buzbeea114add2012-05-03 15:00:40 -07001115 /* Detect loops */
1116 oatMethodLoopDetection(cUnit.get());
buzbee67bf8852011-08-17 17:51:35 -07001117
Bill Buzbeea114add2012-05-03 15:00:40 -07001118 /* Count uses */
1119 oatMethodUseCount(cUnit.get());
buzbee67bf8852011-08-17 17:51:35 -07001120
Bill Buzbeea114add2012-05-03 15:00:40 -07001121 /* Perform null check elimination */
1122 oatMethodNullCheckElimination(cUnit.get());
1123
buzbeed1643e42012-09-05 14:06:51 -07001124 /* Combine basic blocks where possible */
1125 oatMethodBasicBlockCombine(cUnit.get());
1126
Bill Buzbeea114add2012-05-03 15:00:40 -07001127 /* Do some basic block optimizations */
1128 oatMethodBasicBlockOptimization(cUnit.get());
1129
buzbeed1643e42012-09-05 14:06:51 -07001130 if (cUnit->enableDebug & (1 << kDebugDumpCheckStats)) {
1131 oatDumpCheckStats(cUnit.get());
1132 }
1133
Bill Buzbeea114add2012-05-03 15:00:40 -07001134 oatInitializeRegAlloc(cUnit.get()); // Needs to happen after SSA naming
1135
1136 /* Allocate Registers using simple local allocation scheme */
1137 oatSimpleRegAlloc(cUnit.get());
1138
buzbee2cfc6392012-05-07 14:51:40 -07001139#if defined(ART_USE_QUICK_COMPILER)
1140 /* Go the LLVM path? */
1141 if (cUnit->genBitcode) {
1142 // MIR->Bitcode
1143 oatMethodMIR2Bitcode(cUnit.get());
buzbeeabc4c6b2012-08-23 08:17:15 -07001144 if (cUnit->gbcOnly) {
1145 // all done
1146 oatArenaReset(cUnit.get());
1147 return NULL;
1148 }
buzbee2cfc6392012-05-07 14:51:40 -07001149 // Bitcode->LIR
1150 oatMethodBitcode2LIR(cUnit.get());
1151 } else {
1152#endif
1153 if (specialCase != kNoHandler) {
1154 /*
1155 * Custom codegen for special cases. If for any reason the
1156 * special codegen doesn't succeed, cUnit->firstLIRInsn will
1157 * set to NULL;
1158 */
1159 oatSpecialMIR2LIR(cUnit.get(), specialCase);
1160 }
buzbee67bf8852011-08-17 17:51:35 -07001161
buzbee2cfc6392012-05-07 14:51:40 -07001162 /* Convert MIR to LIR, etc. */
1163 if (cUnit->firstLIRInsn == NULL) {
1164 oatMethodMIR2LIR(cUnit.get());
1165 }
1166#if defined(ART_USE_QUICK_COMPILER)
Bill Buzbeea114add2012-05-03 15:00:40 -07001167 }
buzbee2cfc6392012-05-07 14:51:40 -07001168#endif
buzbee67bf8852011-08-17 17:51:35 -07001169
Bill Buzbeea114add2012-05-03 15:00:40 -07001170 // Debugging only
1171 if (cUnit->enableDebug & (1 << kDebugDumpCFG)) {
1172 oatDumpCFG(cUnit.get(), "/sdcard/cfg/");
1173 }
buzbee16da88c2012-03-20 10:38:17 -07001174
Bill Buzbeea114add2012-05-03 15:00:40 -07001175 /* Method is not empty */
1176 if (cUnit->firstLIRInsn) {
buzbee67bf8852011-08-17 17:51:35 -07001177
Bill Buzbeea114add2012-05-03 15:00:40 -07001178 // mark the targets of switch statement case labels
1179 oatProcessSwitchTables(cUnit.get());
buzbee67bf8852011-08-17 17:51:35 -07001180
Bill Buzbeea114add2012-05-03 15:00:40 -07001181 /* Convert LIR into machine code. */
1182 oatAssembleLIR(cUnit.get());
buzbee99ba9642012-01-25 14:23:14 -08001183
Elliott Hughes3b6baaa2011-10-14 19:13:56 -07001184 if (cUnit->printMe) {
Bill Buzbeea114add2012-05-03 15:00:40 -07001185 oatCodegenDump(cUnit.get());
buzbee67bf8852011-08-17 17:51:35 -07001186 }
1187
Bill Buzbeea114add2012-05-03 15:00:40 -07001188 if (cUnit->opcodeCount != NULL) {
1189 LOG(INFO) << "Opcode Count";
1190 for (int i = 0; i < kNumPackedOpcodes; i++) {
1191 if (cUnit->opcodeCount[i] != 0) {
1192 LOG(INFO) << "-C- "
1193 << Instruction::Name(static_cast<Instruction::Code>(i))
1194 << " " << cUnit->opcodeCount[i];
buzbee67bf8852011-08-17 17:51:35 -07001195 }
Bill Buzbeea114add2012-05-03 15:00:40 -07001196 }
1197 }
1198 }
buzbeea7c12682012-03-19 13:13:53 -07001199
Bill Buzbeea114add2012-05-03 15:00:40 -07001200 // Combine vmap tables - core regs, then fp regs - into vmapTable
1201 std::vector<uint16_t> vmapTable;
buzbeeca7a5e42012-08-20 11:12:18 -07001202 // Core regs may have been inserted out of order - sort first
1203 std::sort(cUnit->coreVmapTable.begin(), cUnit->coreVmapTable.end());
Bill Buzbeea114add2012-05-03 15:00:40 -07001204 for (size_t i = 0 ; i < cUnit->coreVmapTable.size(); i++) {
buzbeeca7a5e42012-08-20 11:12:18 -07001205 // Copy, stripping out the phys register sort key
1206 vmapTable.push_back(~(-1 << VREG_NUM_WIDTH) & cUnit->coreVmapTable[i]);
Bill Buzbeea114add2012-05-03 15:00:40 -07001207 }
1208 // If we have a frame, push a marker to take place of lr
1209 if (cUnit->frameSize > 0) {
1210 vmapTable.push_back(INVALID_VREG);
1211 } else {
1212 DCHECK_EQ(__builtin_popcount(cUnit->coreSpillMask), 0);
1213 DCHECK_EQ(__builtin_popcount(cUnit->fpSpillMask), 0);
1214 }
buzbeeca7a5e42012-08-20 11:12:18 -07001215 // Combine vmap tables - core regs, then fp regs. fp regs already sorted
Bill Buzbeea114add2012-05-03 15:00:40 -07001216 for (uint32_t i = 0; i < cUnit->fpVmapTable.size(); i++) {
1217 vmapTable.push_back(cUnit->fpVmapTable[i]);
1218 }
1219 CompiledMethod* result =
1220 new CompiledMethod(cUnit->instructionSet, cUnit->codeBuffer,
1221 cUnit->frameSize, cUnit->coreSpillMask,
1222 cUnit->fpSpillMask, cUnit->mappingTable, vmapTable);
buzbee67bf8852011-08-17 17:51:35 -07001223
Bill Buzbeea114add2012-05-03 15:00:40 -07001224 VLOG(compiler) << "Compiled " << PrettyMethod(method_idx, dex_file)
1225 << " (" << (cUnit->codeBuffer.size() * sizeof(cUnit->codeBuffer[0]))
1226 << " bytes)";
buzbee5abfa3e2012-01-31 17:01:43 -08001227
1228#ifdef WITH_MEMSTATS
Bill Buzbeea114add2012-05-03 15:00:40 -07001229 if (cUnit->enableDebug & (1 << kDebugShowMemoryUsage)) {
1230 oatDumpMemStats(cUnit.get());
1231 }
buzbee5abfa3e2012-01-31 17:01:43 -08001232#endif
buzbee67bf8852011-08-17 17:51:35 -07001233
Bill Buzbeea114add2012-05-03 15:00:40 -07001234 oatArenaReset(cUnit.get());
buzbeeba938cb2012-02-03 14:47:55 -08001235
Bill Buzbeea114add2012-05-03 15:00:40 -07001236 return result;
buzbee67bf8852011-08-17 17:51:35 -07001237}
1238
buzbeeabc4c6b2012-08-23 08:17:15 -07001239#if defined(ART_USE_QUICK_COMPILER)
1240CompiledMethod* oatCompileMethod(Compiler& compiler,
1241 const DexFile::CodeItem* code_item,
1242 uint32_t access_flags, InvokeType invoke_type,
1243 uint32_t method_idx, jobject class_loader,
1244 const DexFile& dex_file)
1245{
1246 return compileMethod(compiler, code_item, access_flags, invoke_type, method_idx, class_loader,
1247 dex_file, NULL, NULL, NULL, NULL, false);
1248}
1249
1250/*
1251 * Given existing llvm module, context, intrinsic_helper and IRBuilder,
1252 * add the bitcode for the method described by code_item to the module.
1253 */
1254void oatCompileMethodToGBC(Compiler& compiler,
1255 const DexFile::CodeItem* code_item,
1256 uint32_t access_flags, InvokeType invoke_type,
1257 uint32_t method_idx, jobject class_loader,
1258 const DexFile& dex_file,
1259 llvm::Module* module,
1260 llvm::LLVMContext* context,
1261 greenland::IntrinsicHelper* intrinsic_helper,
1262 greenland::IRBuilder* irb)
1263{
1264 compileMethod(compiler, code_item, access_flags, invoke_type, method_idx, class_loader,
1265 dex_file, module, context, intrinsic_helper, irb, true);
1266}
1267#else
1268CompiledMethod* oatCompileMethod(Compiler& compiler,
1269 const DexFile::CodeItem* code_item,
1270 uint32_t access_flags, InvokeType invoke_type,
1271 uint32_t method_idx, jobject class_loader,
1272 const DexFile& dex_file)
1273{
1274 return compileMethod(compiler, code_item, access_flags, invoke_type, method_idx, class_loader,
1275 dex_file);
1276}
1277#endif
1278
Elliott Hughes11d1b0c2012-01-23 16:57:47 -08001279} // namespace art
Elliott Hughesb3bd5f02012-03-08 21:05:27 -08001280
Bill Buzbeea114add2012-05-03 15:00:40 -07001281extern "C" art::CompiledMethod*
1282 ArtCompileMethod(art::Compiler& compiler,
1283 const art::DexFile::CodeItem* code_item,
Ian Rogers08f753d2012-08-24 14:35:25 -07001284 uint32_t access_flags, art::InvokeType invoke_type,
1285 uint32_t method_idx, jobject class_loader,
Bill Buzbeea114add2012-05-03 15:00:40 -07001286 const art::DexFile& dex_file)
Elliott Hughesb3bd5f02012-03-08 21:05:27 -08001287{
1288 CHECK_EQ(compiler.GetInstructionSet(), art::oatInstructionSet());
Ian Rogers08f753d2012-08-24 14:35:25 -07001289 return art::oatCompileMethod(compiler, code_item, access_flags, invoke_type,
1290 method_idx, class_loader, dex_file);
Elliott Hughesb3bd5f02012-03-08 21:05:27 -08001291}