mir_graph.cc revision cdacac4a8196bdc620185079ec9e886329606f3d
1/* 2 * Copyright (C) 2013 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 "mir_graph.h" 18 19#include <inttypes.h> 20 21#include "base/stl_util.h" 22#include "compiler_internals.h" 23#include "dex_file-inl.h" 24#include "dex/quick/dex_file_to_method_inliner_map.h" 25#include "dex/quick/dex_file_method_inliner.h" 26#include "leb128.h" 27 28namespace art { 29 30#define MAX_PATTERN_LEN 5 31 32const char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { 33 "Phi", 34 "Copy", 35 "FusedCmplFloat", 36 "FusedCmpgFloat", 37 "FusedCmplDouble", 38 "FusedCmpgDouble", 39 "FusedCmpLong", 40 "Nop", 41 "OpNullCheck", 42 "OpRangeCheck", 43 "OpDivZeroCheck", 44 "Check1", 45 "Check2", 46 "Select", 47}; 48 49MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 50 : reg_location_(NULL), 51 cu_(cu), 52 ssa_base_vregs_(NULL), 53 ssa_subscripts_(NULL), 54 vreg_to_ssa_map_(NULL), 55 ssa_last_defs_(NULL), 56 is_constant_v_(NULL), 57 constant_values_(NULL), 58 use_counts_(arena, 256, kGrowableArrayMisc), 59 raw_use_counts_(arena, 256, kGrowableArrayMisc), 60 num_reachable_blocks_(0), 61 dfs_order_(NULL), 62 dfs_post_order_(NULL), 63 dom_post_order_traversal_(NULL), 64 i_dom_list_(NULL), 65 def_block_matrix_(NULL), 66 temp_dalvik_register_v_(NULL), 67 temp_scoped_alloc_(), 68 temp_insn_data_(nullptr), 69 temp_bit_vector_size_(0u), 70 temp_bit_vector_(nullptr), 71 block_list_(arena, 100, kGrowableArrayBlockList), 72 try_block_addr_(NULL), 73 entry_block_(NULL), 74 exit_block_(NULL), 75 num_blocks_(0), 76 current_code_item_(NULL), 77 dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), 78 current_method_(kInvalidEntry), 79 current_offset_(kInvalidEntry), 80 def_count_(0), 81 opcode_count_(NULL), 82 num_ssa_regs_(0), 83 method_sreg_(0), 84 attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. 85 checkstats_(NULL), 86 arena_(arena), 87 backward_branches_(0), 88 forward_branches_(0), 89 compiler_temps_(arena, 6, kGrowableArrayMisc), 90 num_non_special_compiler_temps_(0), 91 max_available_non_special_compiler_temps_(0), 92 punt_to_interpreter_(false), 93 merged_df_flags_(0u), 94 ifield_lowering_infos_(arena, 0u), 95 sfield_lowering_infos_(arena, 0u), 96 method_lowering_infos_(arena, 0u) { 97 try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); 98 max_available_special_compiler_temps_ = std::abs(static_cast<int>(kVRegNonSpecialTempBaseReg)) 99 - std::abs(static_cast<int>(kVRegTempBaseReg)); 100} 101 102MIRGraph::~MIRGraph() { 103 STLDeleteElements(&m_units_); 104} 105 106/* 107 * Parse an instruction, return the length of the instruction 108 */ 109int MIRGraph::ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction) { 110 const Instruction* instruction = Instruction::At(code_ptr); 111 *decoded_instruction = DecodedInstruction(instruction); 112 113 return instruction->SizeInCodeUnits(); 114} 115 116 117/* Split an existing block from the specified code offset into two */ 118BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, 119 BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { 120 DCHECK_GT(code_offset, orig_block->start_offset); 121 MIR* insn = orig_block->first_mir_insn; 122 MIR* prev = NULL; 123 while (insn) { 124 if (insn->offset == code_offset) break; 125 prev = insn; 126 insn = insn->next; 127 } 128 if (insn == NULL) { 129 LOG(FATAL) << "Break split failed"; 130 } 131 BasicBlock *bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); 132 block_list_.Insert(bottom_block); 133 134 bottom_block->start_offset = code_offset; 135 bottom_block->first_mir_insn = insn; 136 bottom_block->last_mir_insn = orig_block->last_mir_insn; 137 138 /* If this block was terminated by a return, the flag needs to go with the bottom block */ 139 bottom_block->terminated_by_return = orig_block->terminated_by_return; 140 orig_block->terminated_by_return = false; 141 142 /* Handle the taken path */ 143 bottom_block->taken = orig_block->taken; 144 if (bottom_block->taken != NullBasicBlockId) { 145 orig_block->taken = NullBasicBlockId; 146 BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); 147 bb_taken->predecessors->Delete(orig_block->id); 148 bb_taken->predecessors->Insert(bottom_block->id); 149 } 150 151 /* Handle the fallthrough path */ 152 bottom_block->fall_through = orig_block->fall_through; 153 orig_block->fall_through = bottom_block->id; 154 bottom_block->predecessors->Insert(orig_block->id); 155 if (bottom_block->fall_through != NullBasicBlockId) { 156 BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); 157 bb_fall_through->predecessors->Delete(orig_block->id); 158 bb_fall_through->predecessors->Insert(bottom_block->id); 159 } 160 161 /* Handle the successor list */ 162 if (orig_block->successor_block_list_type != kNotUsed) { 163 bottom_block->successor_block_list_type = orig_block->successor_block_list_type; 164 bottom_block->successor_blocks = orig_block->successor_blocks; 165 orig_block->successor_block_list_type = kNotUsed; 166 orig_block->successor_blocks = NULL; 167 GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); 168 while (true) { 169 SuccessorBlockInfo *successor_block_info = iterator.Next(); 170 if (successor_block_info == NULL) break; 171 BasicBlock *bb = GetBasicBlock(successor_block_info->block); 172 bb->predecessors->Delete(orig_block->id); 173 bb->predecessors->Insert(bottom_block->id); 174 } 175 } 176 177 orig_block->last_mir_insn = prev; 178 prev->next = NULL; 179 180 /* 181 * Update the immediate predecessor block pointer so that outgoing edges 182 * can be applied to the proper block. 183 */ 184 if (immed_pred_block_p) { 185 DCHECK_EQ(*immed_pred_block_p, orig_block); 186 *immed_pred_block_p = bottom_block; 187 } 188 189 // Associate dex instructions in the bottom block with the new container. 190 DCHECK(insn != nullptr); 191 DCHECK(insn != orig_block->first_mir_insn); 192 DCHECK(insn == bottom_block->first_mir_insn); 193 DCHECK_EQ(insn->offset, bottom_block->start_offset); 194 DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || 195 !IsPseudoMirOp(insn->dalvikInsn.opcode)); 196 DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); 197 MIR* p = insn; 198 dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 199 while (p != bottom_block->last_mir_insn) { 200 p = p->next; 201 DCHECK(p != nullptr); 202 int opcode = p->dalvikInsn.opcode; 203 /* 204 * Some messiness here to ensure that we only enter real opcodes and only the 205 * first half of a potentially throwing instruction that has been split into 206 * CHECK and work portions. Since the 2nd half of a split operation is always 207 * the first in a BasicBlock, we can't hit it here. 208 */ 209 if ((opcode == kMirOpCheck) || !IsPseudoMirOp(opcode)) { 210 DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); 211 dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 212 } 213 } 214 215 return bottom_block; 216} 217 218/* 219 * Given a code offset, find out the block that starts with it. If the offset 220 * is in the middle of an existing block, split it into two. If immed_pred_block_p 221 * is not non-null and is the block being split, update *immed_pred_block_p to 222 * point to the bottom block so that outgoing edges can be set up properly 223 * (by the caller) 224 * Utilizes a map for fast lookup of the typical cases. 225 */ 226BasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, 227 BasicBlock** immed_pred_block_p) { 228 if (code_offset >= cu_->code_item->insns_size_in_code_units_) { 229 return NULL; 230 } 231 232 int block_id = dex_pc_to_block_map_.Get(code_offset); 233 BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); 234 235 if ((bb != NULL) && (bb->start_offset == code_offset)) { 236 // Does this containing block start with the desired instruction? 237 return bb; 238 } 239 240 // No direct hit. 241 if (!create) { 242 return NULL; 243 } 244 245 if (bb != NULL) { 246 // The target exists somewhere in an existing block. 247 return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : NULL); 248 } 249 250 // Create a new block. 251 bb = NewMemBB(kDalvikByteCode, num_blocks_++); 252 block_list_.Insert(bb); 253 bb->start_offset = code_offset; 254 dex_pc_to_block_map_.Put(bb->start_offset, bb->id); 255 return bb; 256} 257 258 259/* Identify code range in try blocks and set up the empty catch blocks */ 260void MIRGraph::ProcessTryCatchBlocks() { 261 int tries_size = current_code_item_->tries_size_; 262 DexOffset offset; 263 264 if (tries_size == 0) { 265 return; 266 } 267 268 for (int i = 0; i < tries_size; i++) { 269 const DexFile::TryItem* pTry = 270 DexFile::GetTryItems(*current_code_item_, i); 271 DexOffset start_offset = pTry->start_addr_; 272 DexOffset end_offset = start_offset + pTry->insn_count_; 273 for (offset = start_offset; offset < end_offset; offset++) { 274 try_block_addr_->SetBit(offset); 275 } 276 } 277 278 // Iterate over each of the handlers to enqueue the empty Catch blocks 279 const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); 280 uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 281 for (uint32_t idx = 0; idx < handlers_size; idx++) { 282 CatchHandlerIterator iterator(handlers_ptr); 283 for (; iterator.HasNext(); iterator.Next()) { 284 uint32_t address = iterator.GetHandlerAddress(); 285 FindBlock(address, false /* split */, true /*create*/, 286 /* immed_pred_block_p */ NULL); 287 } 288 handlers_ptr = iterator.EndDataPointer(); 289 } 290} 291 292/* Process instructions with the kBranch flag */ 293BasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 294 int width, int flags, const uint16_t* code_ptr, 295 const uint16_t* code_end) { 296 DexOffset target = cur_offset; 297 switch (insn->dalvikInsn.opcode) { 298 case Instruction::GOTO: 299 case Instruction::GOTO_16: 300 case Instruction::GOTO_32: 301 target += insn->dalvikInsn.vA; 302 break; 303 case Instruction::IF_EQ: 304 case Instruction::IF_NE: 305 case Instruction::IF_LT: 306 case Instruction::IF_GE: 307 case Instruction::IF_GT: 308 case Instruction::IF_LE: 309 cur_block->conditional_branch = true; 310 target += insn->dalvikInsn.vC; 311 break; 312 case Instruction::IF_EQZ: 313 case Instruction::IF_NEZ: 314 case Instruction::IF_LTZ: 315 case Instruction::IF_GEZ: 316 case Instruction::IF_GTZ: 317 case Instruction::IF_LEZ: 318 cur_block->conditional_branch = true; 319 target += insn->dalvikInsn.vB; 320 break; 321 default: 322 LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; 323 } 324 CountBranch(target); 325 BasicBlock *taken_block = FindBlock(target, /* split */ true, /* create */ true, 326 /* immed_pred_block_p */ &cur_block); 327 cur_block->taken = taken_block->id; 328 taken_block->predecessors->Insert(cur_block->id); 329 330 /* Always terminate the current block for conditional branches */ 331 if (flags & Instruction::kContinue) { 332 BasicBlock *fallthrough_block = FindBlock(cur_offset + width, 333 /* 334 * If the method is processed 335 * in sequential order from the 336 * beginning, we don't need to 337 * specify split for continue 338 * blocks. However, this 339 * routine can be called by 340 * compileLoop, which starts 341 * parsing the method from an 342 * arbitrary address in the 343 * method body. 344 */ 345 true, 346 /* create */ 347 true, 348 /* immed_pred_block_p */ 349 &cur_block); 350 cur_block->fall_through = fallthrough_block->id; 351 fallthrough_block->predecessors->Insert(cur_block->id); 352 } else if (code_ptr < code_end) { 353 FindBlock(cur_offset + width, /* split */ false, /* create */ true, 354 /* immed_pred_block_p */ NULL); 355 } 356 return cur_block; 357} 358 359/* Process instructions with the kSwitch flag */ 360BasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 361 int width, int flags) { 362 const uint16_t* switch_data = 363 reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); 364 int size; 365 const int* keyTable; 366 const int* target_table; 367 int i; 368 int first_key; 369 370 /* 371 * Packed switch data format: 372 * ushort ident = 0x0100 magic value 373 * ushort size number of entries in the table 374 * int first_key first (and lowest) switch case value 375 * int targets[size] branch targets, relative to switch opcode 376 * 377 * Total size is (4+size*2) 16-bit code units. 378 */ 379 if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { 380 DCHECK_EQ(static_cast<int>(switch_data[0]), 381 static_cast<int>(Instruction::kPackedSwitchSignature)); 382 size = switch_data[1]; 383 first_key = switch_data[2] | (switch_data[3] << 16); 384 target_table = reinterpret_cast<const int*>(&switch_data[4]); 385 keyTable = NULL; // Make the compiler happy 386 /* 387 * Sparse switch data format: 388 * ushort ident = 0x0200 magic value 389 * ushort size number of entries in the table; > 0 390 * int keys[size] keys, sorted low-to-high; 32-bit aligned 391 * int targets[size] branch targets, relative to switch opcode 392 * 393 * Total size is (2+size*4) 16-bit code units. 394 */ 395 } else { 396 DCHECK_EQ(static_cast<int>(switch_data[0]), 397 static_cast<int>(Instruction::kSparseSwitchSignature)); 398 size = switch_data[1]; 399 keyTable = reinterpret_cast<const int*>(&switch_data[2]); 400 target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); 401 first_key = 0; // To make the compiler happy 402 } 403 404 if (cur_block->successor_block_list_type != kNotUsed) { 405 LOG(FATAL) << "Successor block list already in use: " 406 << static_cast<int>(cur_block->successor_block_list_type); 407 } 408 cur_block->successor_block_list_type = 409 (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; 410 cur_block->successor_blocks = 411 new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); 412 413 for (i = 0; i < size; i++) { 414 BasicBlock *case_block = FindBlock(cur_offset + target_table[i], /* split */ true, 415 /* create */ true, /* immed_pred_block_p */ &cur_block); 416 SuccessorBlockInfo *successor_block_info = 417 static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), 418 kArenaAllocSuccessor)); 419 successor_block_info->block = case_block->id; 420 successor_block_info->key = 421 (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 422 first_key + i : keyTable[i]; 423 cur_block->successor_blocks->Insert(successor_block_info); 424 case_block->predecessors->Insert(cur_block->id); 425 } 426 427 /* Fall-through case */ 428 BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, 429 /* create */ true, /* immed_pred_block_p */ NULL); 430 cur_block->fall_through = fallthrough_block->id; 431 fallthrough_block->predecessors->Insert(cur_block->id); 432 return cur_block; 433} 434 435/* Process instructions with the kThrow flag */ 436BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 437 int width, int flags, ArenaBitVector* try_block_addr, 438 const uint16_t* code_ptr, const uint16_t* code_end) { 439 bool in_try_block = try_block_addr->IsBitSet(cur_offset); 440 bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); 441 bool build_all_edges = 442 (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; 443 444 /* In try block */ 445 if (in_try_block) { 446 CatchHandlerIterator iterator(*current_code_item_, cur_offset); 447 448 if (cur_block->successor_block_list_type != kNotUsed) { 449 LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 450 LOG(FATAL) << "Successor block list already in use: " 451 << static_cast<int>(cur_block->successor_block_list_type); 452 } 453 454 cur_block->successor_block_list_type = kCatch; 455 cur_block->successor_blocks = 456 new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, 2, kGrowableArraySuccessorBlocks); 457 458 for (; iterator.HasNext(); iterator.Next()) { 459 BasicBlock *catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, 460 false /* creat */, NULL /* immed_pred_block_p */); 461 catch_block->catch_entry = true; 462 if (kIsDebugBuild) { 463 catches_.insert(catch_block->start_offset); 464 } 465 SuccessorBlockInfo *successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 466 (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 467 successor_block_info->block = catch_block->id; 468 successor_block_info->key = iterator.GetHandlerTypeIndex(); 469 cur_block->successor_blocks->Insert(successor_block_info); 470 catch_block->predecessors->Insert(cur_block->id); 471 } 472 } else if (build_all_edges) { 473 BasicBlock *eh_block = NewMemBB(kExceptionHandling, num_blocks_++); 474 cur_block->taken = eh_block->id; 475 block_list_.Insert(eh_block); 476 eh_block->start_offset = cur_offset; 477 eh_block->predecessors->Insert(cur_block->id); 478 } 479 480 if (is_throw) { 481 cur_block->explicit_throw = true; 482 if (code_ptr < code_end) { 483 // Force creation of new block following THROW via side-effect 484 FindBlock(cur_offset + width, /* split */ false, /* create */ true, 485 /* immed_pred_block_p */ NULL); 486 } 487 if (!in_try_block) { 488 // Don't split a THROW that can't rethrow - we're done. 489 return cur_block; 490 } 491 } 492 493 if (!build_all_edges) { 494 /* 495 * Even though there is an exception edge here, control cannot return to this 496 * method. Thus, for the purposes of dataflow analysis and optimization, we can 497 * ignore the edge. Doing this reduces compile time, and increases the scope 498 * of the basic-block level optimization pass. 499 */ 500 return cur_block; 501 } 502 503 /* 504 * Split the potentially-throwing instruction into two parts. 505 * The first half will be a pseudo-op that captures the exception 506 * edges and terminates the basic block. It always falls through. 507 * Then, create a new basic block that begins with the throwing instruction 508 * (minus exceptions). Note: this new basic block must NOT be entered into 509 * the block_map. If the potentially-throwing instruction is the target of a 510 * future branch, we need to find the check psuedo half. The new 511 * basic block containing the work portion of the instruction should 512 * only be entered via fallthrough from the block containing the 513 * pseudo exception edge MIR. Note also that this new block is 514 * not automatically terminated after the work portion, and may 515 * contain following instructions. 516 * 517 * Note also that the dex_pc_to_block_map_ entry for the potentially 518 * throwing instruction will refer to the original basic block. 519 */ 520 BasicBlock *new_block = NewMemBB(kDalvikByteCode, num_blocks_++); 521 block_list_.Insert(new_block); 522 new_block->start_offset = insn->offset; 523 cur_block->fall_through = new_block->id; 524 new_block->predecessors->Insert(cur_block->id); 525 MIR* new_insn = static_cast<MIR*>(arena_->Alloc(sizeof(MIR), kArenaAllocMIR)); 526 *new_insn = *insn; 527 insn->dalvikInsn.opcode = 528 static_cast<Instruction::Code>(kMirOpCheck); 529 // Associate the two halves 530 insn->meta.throw_insn = new_insn; 531 new_block->AppendMIR(new_insn); 532 return new_block; 533} 534 535/* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ 536void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 537 InvokeType invoke_type, uint16_t class_def_idx, 538 uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { 539 current_code_item_ = code_item; 540 method_stack_.push_back(std::make_pair(current_method_, current_offset_)); 541 current_method_ = m_units_.size(); 542 current_offset_ = 0; 543 // TODO: will need to snapshot stack image and use that as the mir context identification. 544 m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), 545 dex_file, current_code_item_, class_def_idx, method_idx, access_flags, 546 cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); 547 const uint16_t* code_ptr = current_code_item_->insns_; 548 const uint16_t* code_end = 549 current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; 550 551 // TODO: need to rework expansion of block list & try_block_addr when inlining activated. 552 // TUNING: use better estimate of basic blocks for following resize. 553 block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); 554 dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_); 555 556 // TODO: replace with explicit resize routine. Using automatic extension side effect for now. 557 try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); 558 try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); 559 560 // If this is the first method, set up default entry and exit blocks. 561 if (current_method_ == 0) { 562 DCHECK(entry_block_ == NULL); 563 DCHECK(exit_block_ == NULL); 564 DCHECK_EQ(num_blocks_, 0); 565 // Use id 0 to represent a null block. 566 BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); 567 DCHECK_EQ(null_block->id, NullBasicBlockId); 568 null_block->hidden = true; 569 block_list_.Insert(null_block); 570 entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); 571 block_list_.Insert(entry_block_); 572 exit_block_ = NewMemBB(kExitBlock, num_blocks_++); 573 block_list_.Insert(exit_block_); 574 // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. 575 cu_->dex_file = &dex_file; 576 cu_->class_def_idx = class_def_idx; 577 cu_->method_idx = method_idx; 578 cu_->access_flags = access_flags; 579 cu_->invoke_type = invoke_type; 580 cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); 581 cu_->num_ins = current_code_item_->ins_size_; 582 cu_->num_regs = current_code_item_->registers_size_ - cu_->num_ins; 583 cu_->num_outs = current_code_item_->outs_size_; 584 cu_->num_dalvik_registers = current_code_item_->registers_size_; 585 cu_->insns = current_code_item_->insns_; 586 cu_->code_item = current_code_item_; 587 } else { 588 UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; 589 /* 590 * Will need to manage storage for ins & outs, push prevous state and update 591 * insert point. 592 */ 593 } 594 595 /* Current block to record parsed instructions */ 596 BasicBlock *cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); 597 DCHECK_EQ(current_offset_, 0U); 598 cur_block->start_offset = current_offset_; 599 block_list_.Insert(cur_block); 600 // TODO: for inlining support, insert at the insert point rather than entry block. 601 entry_block_->fall_through = cur_block->id; 602 cur_block->predecessors->Insert(entry_block_->id); 603 604 /* Identify code range in try blocks and set up the empty catch blocks */ 605 ProcessTryCatchBlocks(); 606 607 uint64_t merged_df_flags = 0u; 608 609 /* Parse all instructions and put them into containing basic blocks */ 610 while (code_ptr < code_end) { 611 MIR *insn = static_cast<MIR *>(arena_->Alloc(sizeof(MIR), kArenaAllocMIR)); 612 insn->offset = current_offset_; 613 insn->m_unit_index = current_method_; 614 int width = ParseInsn(code_ptr, &insn->dalvikInsn); 615 insn->width = width; 616 Instruction::Code opcode = insn->dalvikInsn.opcode; 617 if (opcode_count_ != NULL) { 618 opcode_count_[static_cast<int>(opcode)]++; 619 } 620 621 int flags = Instruction::FlagsOf(insn->dalvikInsn.opcode); 622 int verify_flags = Instruction::VerifyFlagsOf(insn->dalvikInsn.opcode); 623 624 uint64_t df_flags = oat_data_flow_attributes_[insn->dalvikInsn.opcode]; 625 merged_df_flags |= df_flags; 626 627 if (df_flags & DF_HAS_DEFS) { 628 def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; 629 } 630 631 if (df_flags & DF_LVN) { 632 cur_block->use_lvn = true; // Run local value numbering on this basic block. 633 } 634 635 // Check for inline data block signatures 636 if (opcode == Instruction::NOP) { 637 // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. 638 if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { 639 // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. 640 uint16_t following_raw_instruction = code_ptr[1]; 641 if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || 642 (following_raw_instruction == Instruction::kPackedSwitchSignature) || 643 (following_raw_instruction == Instruction::kArrayDataSignature)) { 644 width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); 645 } 646 } 647 if (width == 1) { 648 // It is a simple nop - treat normally. 649 cur_block->AppendMIR(insn); 650 } else { 651 DCHECK(cur_block->fall_through == NullBasicBlockId); 652 DCHECK(cur_block->taken == NullBasicBlockId); 653 // Unreachable instruction, mark for no continuation. 654 flags &= ~Instruction::kContinue; 655 } 656 } else { 657 cur_block->AppendMIR(insn); 658 } 659 660 // Associate the starting dex_pc for this opcode with its containing basic block. 661 dex_pc_to_block_map_.Put(insn->offset, cur_block->id); 662 663 code_ptr += width; 664 665 if (flags & Instruction::kBranch) { 666 cur_block = ProcessCanBranch(cur_block, insn, current_offset_, 667 width, flags, code_ptr, code_end); 668 } else if (flags & Instruction::kReturn) { 669 cur_block->terminated_by_return = true; 670 cur_block->fall_through = exit_block_->id; 671 exit_block_->predecessors->Insert(cur_block->id); 672 /* 673 * Terminate the current block if there are instructions 674 * afterwards. 675 */ 676 if (code_ptr < code_end) { 677 /* 678 * Create a fallthrough block for real instructions 679 * (incl. NOP). 680 */ 681 FindBlock(current_offset_ + width, /* split */ false, /* create */ true, 682 /* immed_pred_block_p */ NULL); 683 } 684 } else if (flags & Instruction::kThrow) { 685 cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, 686 code_ptr, code_end); 687 } else if (flags & Instruction::kSwitch) { 688 cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); 689 } 690 if (verify_flags & Instruction::kVerifyVarArgRange) { 691 /* 692 * The Quick backend's runtime model includes a gap between a method's 693 * argument ("in") vregs and the rest of its vregs. Handling a range instruction 694 * which spans the gap is somewhat complicated, and should not happen 695 * in normal usage of dx. Punt to the interpreter. 696 */ 697 int first_reg_in_range = insn->dalvikInsn.vC; 698 int last_reg_in_range = first_reg_in_range + insn->dalvikInsn.vA - 1; 699 if (IsInVReg(first_reg_in_range) != IsInVReg(last_reg_in_range)) { 700 punt_to_interpreter_ = true; 701 } 702 } 703 current_offset_ += width; 704 BasicBlock *next_block = FindBlock(current_offset_, /* split */ false, /* create */ 705 false, /* immed_pred_block_p */ NULL); 706 if (next_block) { 707 /* 708 * The next instruction could be the target of a previously parsed 709 * forward branch so a block is already created. If the current 710 * instruction is not an unconditional branch, connect them through 711 * the fall-through link. 712 */ 713 DCHECK(cur_block->fall_through == NullBasicBlockId || 714 GetBasicBlock(cur_block->fall_through) == next_block || 715 GetBasicBlock(cur_block->fall_through) == exit_block_); 716 717 if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { 718 cur_block->fall_through = next_block->id; 719 next_block->predecessors->Insert(cur_block->id); 720 } 721 cur_block = next_block; 722 } 723 } 724 merged_df_flags_ = merged_df_flags; 725 726 if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 727 DumpCFG("/sdcard/1_post_parse_cfg/", true); 728 } 729 730 if (cu_->verbose) { 731 DumpMIRGraph(); 732 } 733} 734 735void MIRGraph::ShowOpcodeStats() { 736 DCHECK(opcode_count_ != NULL); 737 LOG(INFO) << "Opcode Count"; 738 for (int i = 0; i < kNumPackedOpcodes; i++) { 739 if (opcode_count_[i] != 0) { 740 LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) 741 << " " << opcode_count_[i]; 742 } 743 } 744} 745 746// TODO: use a configurable base prefix, and adjust callers to supply pass name. 747/* Dump the CFG into a DOT graph */ 748void MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { 749 FILE* file; 750 std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); 751 ReplaceSpecialChars(fname); 752 fname = StringPrintf("%s%s%x%s.dot", dir_prefix, fname.c_str(), 753 GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, 754 suffix == nullptr ? "" : suffix); 755 file = fopen(fname.c_str(), "w"); 756 if (file == NULL) { 757 return; 758 } 759 fprintf(file, "digraph G {\n"); 760 761 fprintf(file, " rankdir=TB\n"); 762 763 int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; 764 int idx; 765 766 for (idx = 0; idx < num_blocks; idx++) { 767 int block_idx = all_blocks ? idx : dfs_order_->Get(idx); 768 BasicBlock *bb = GetBasicBlock(block_idx); 769 if (bb == NULL) break; 770 if (bb->block_type == kDead) continue; 771 if (bb->block_type == kEntryBlock) { 772 fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); 773 } else if (bb->block_type == kExitBlock) { 774 fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); 775 } else if (bb->block_type == kDalvikByteCode) { 776 fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", 777 bb->start_offset, bb->id); 778 const MIR *mir; 779 fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 780 bb->first_mir_insn ? " | " : " "); 781 for (mir = bb->first_mir_insn; mir; mir = mir->next) { 782 int opcode = mir->dalvikInsn.opcode; 783 fprintf(file, " {%04x %s %s %s\\l}%s\\\n", mir->offset, 784 mir->ssa_rep ? GetDalvikDisassembly(mir) : 785 (opcode < kMirOpFirst) ? Instruction::Name(mir->dalvikInsn.opcode) : 786 extended_mir_op_names_[opcode - kMirOpFirst], 787 (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", 788 (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", 789 mir->next ? " | " : " "); 790 } 791 fprintf(file, " }\"];\n\n"); 792 } else if (bb->block_type == kExceptionHandling) { 793 char block_name[BLOCK_NAME_LEN]; 794 795 GetBlockName(bb, block_name); 796 fprintf(file, " %s [shape=invhouse];\n", block_name); 797 } 798 799 char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 800 801 if (bb->taken != NullBasicBlockId) { 802 GetBlockName(bb, block_name1); 803 GetBlockName(GetBasicBlock(bb->taken), block_name2); 804 fprintf(file, " %s:s -> %s:n [style=dotted]\n", 805 block_name1, block_name2); 806 } 807 if (bb->fall_through != NullBasicBlockId) { 808 GetBlockName(bb, block_name1); 809 GetBlockName(GetBasicBlock(bb->fall_through), block_name2); 810 fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); 811 } 812 813 if (bb->successor_block_list_type != kNotUsed) { 814 fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", 815 bb->start_offset, bb->id, 816 (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); 817 GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 818 SuccessorBlockInfo *successor_block_info = iterator.Next(); 819 820 int succ_id = 0; 821 while (true) { 822 if (successor_block_info == NULL) break; 823 824 BasicBlock *dest_block = GetBasicBlock(successor_block_info->block); 825 SuccessorBlockInfo *next_successor_block_info = iterator.Next(); 826 827 fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 828 succ_id++, 829 successor_block_info->key, 830 dest_block->start_offset, 831 (next_successor_block_info != NULL) ? " | " : " "); 832 833 successor_block_info = next_successor_block_info; 834 } 835 fprintf(file, " }\"];\n\n"); 836 837 GetBlockName(bb, block_name1); 838 fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", 839 block_name1, bb->start_offset, bb->id); 840 841 if (bb->successor_block_list_type == kPackedSwitch || 842 bb->successor_block_list_type == kSparseSwitch) { 843 GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); 844 845 succ_id = 0; 846 while (true) { 847 SuccessorBlockInfo *successor_block_info = iter.Next(); 848 if (successor_block_info == NULL) break; 849 850 BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 851 852 GetBlockName(dest_block, block_name2); 853 fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, 854 bb->id, succ_id++, block_name2); 855 } 856 } 857 } 858 fprintf(file, "\n"); 859 860 if (cu_->verbose) { 861 /* Display the dominator tree */ 862 GetBlockName(bb, block_name1); 863 fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 864 block_name1, block_name1); 865 if (bb->i_dom) { 866 GetBlockName(GetBasicBlock(bb->i_dom), block_name2); 867 fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); 868 } 869 } 870 } 871 fprintf(file, "}\n"); 872 fclose(file); 873} 874 875/* Insert an MIR instruction to the end of a basic block */ 876void BasicBlock::AppendMIR(MIR* mir) { 877 if (first_mir_insn == nullptr) { 878 DCHECK(last_mir_insn == nullptr); 879 last_mir_insn = first_mir_insn = mir; 880 mir->next = nullptr; 881 } else { 882 last_mir_insn->next = mir; 883 mir->next = nullptr; 884 last_mir_insn = mir; 885 } 886} 887 888/* Insert an MIR instruction to the head of a basic block */ 889void BasicBlock::PrependMIR(MIR* mir) { 890 if (first_mir_insn == nullptr) { 891 DCHECK(last_mir_insn == nullptr); 892 last_mir_insn = first_mir_insn = mir; 893 mir->next = nullptr; 894 } else { 895 mir->next = first_mir_insn; 896 first_mir_insn = mir; 897 } 898} 899 900/* Insert a MIR instruction after the specified MIR */ 901void BasicBlock::InsertMIRAfter(MIR* current_mir, MIR* new_mir) { 902 new_mir->next = current_mir->next; 903 current_mir->next = new_mir; 904 905 if (last_mir_insn == current_mir) { 906 /* Is the last MIR in the block */ 907 last_mir_insn = new_mir; 908 } 909} 910 911MIR* BasicBlock::GetNextUnconditionalMir(MIRGraph* mir_graph, MIR* current) { 912 MIR* next_mir = nullptr; 913 914 if (current != nullptr) { 915 next_mir = current->next; 916 } 917 918 if (next_mir == nullptr) { 919 // Only look for next MIR that follows unconditionally. 920 if ((taken == NullBasicBlockId) && (fall_through != NullBasicBlockId)) { 921 next_mir = mir_graph->GetBasicBlock(fall_through)->first_mir_insn; 922 } 923 } 924 925 return next_mir; 926} 927 928char* MIRGraph::GetDalvikDisassembly(const MIR* mir) { 929 DecodedInstruction insn = mir->dalvikInsn; 930 std::string str; 931 int flags = 0; 932 int opcode = insn.opcode; 933 char* ret; 934 bool nop = false; 935 SSARepresentation* ssa_rep = mir->ssa_rep; 936 Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format 937 int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; 938 int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; 939 940 // Handle special cases. 941 if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { 942 str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 943 str.append(": "); 944 // Recover the original Dex instruction 945 insn = mir->meta.throw_insn->dalvikInsn; 946 ssa_rep = mir->meta.throw_insn->ssa_rep; 947 defs = ssa_rep->num_defs; 948 uses = ssa_rep->num_uses; 949 opcode = insn.opcode; 950 } else if (opcode == kMirOpNop) { 951 str.append("["); 952 // Recover original opcode. 953 insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); 954 opcode = insn.opcode; 955 nop = true; 956 } 957 958 if (opcode >= kMirOpFirst) { 959 str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 960 } else { 961 dalvik_format = Instruction::FormatOf(insn.opcode); 962 flags = Instruction::FlagsOf(insn.opcode); 963 str.append(Instruction::Name(insn.opcode)); 964 } 965 966 if (opcode == kMirOpPhi) { 967 BasicBlockId* incoming = mir->meta.phi_incoming; 968 str.append(StringPrintf(" %s = (%s", 969 GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), 970 GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); 971 str.append(StringPrintf(":%d", incoming[0])); 972 int i; 973 for (i = 1; i < uses; i++) { 974 str.append(StringPrintf(", %s:%d", 975 GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), 976 incoming[i])); 977 } 978 str.append(")"); 979 } else if ((flags & Instruction::kBranch) != 0) { 980 // For branches, decode the instructions to print out the branch targets. 981 int offset = 0; 982 switch (dalvik_format) { 983 case Instruction::k21t: 984 str.append(StringPrintf(" %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 985 offset = insn.vB; 986 break; 987 case Instruction::k22t: 988 str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), 989 GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); 990 offset = insn.vC; 991 break; 992 case Instruction::k10t: 993 case Instruction::k20t: 994 case Instruction::k30t: 995 offset = insn.vA; 996 break; 997 default: 998 LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; 999 } 1000 str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset, 1001 offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); 1002 } else { 1003 // For invokes-style formats, treat wide regs as a pair of singles 1004 bool show_singles = ((dalvik_format == Instruction::k35c) || 1005 (dalvik_format == Instruction::k3rc)); 1006 if (defs != 0) { 1007 str.append(StringPrintf(" %s", GetSSANameWithConst(ssa_rep->defs[0], false).c_str())); 1008 if (uses != 0) { 1009 str.append(", "); 1010 } 1011 } 1012 for (int i = 0; i < uses; i++) { 1013 str.append( 1014 StringPrintf(" %s", GetSSANameWithConst(ssa_rep->uses[i], show_singles).c_str())); 1015 if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { 1016 // For the listing, skip the high sreg. 1017 i++; 1018 } 1019 if (i != (uses -1)) { 1020 str.append(","); 1021 } 1022 } 1023 switch (dalvik_format) { 1024 case Instruction::k11n: // Add one immediate from vB 1025 case Instruction::k21s: 1026 case Instruction::k31i: 1027 case Instruction::k21h: 1028 str.append(StringPrintf(", #%d", insn.vB)); 1029 break; 1030 case Instruction::k51l: // Add one wide immediate 1031 str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); 1032 break; 1033 case Instruction::k21c: // One register, one string/type/method index 1034 case Instruction::k31c: 1035 str.append(StringPrintf(", index #%d", insn.vB)); 1036 break; 1037 case Instruction::k22c: // Two registers, one string/type/method index 1038 str.append(StringPrintf(", index #%d", insn.vC)); 1039 break; 1040 case Instruction::k22s: // Add one immediate from vC 1041 case Instruction::k22b: 1042 str.append(StringPrintf(", #%d", insn.vC)); 1043 break; 1044 default: { 1045 // Nothing left to print 1046 } 1047 } 1048 } 1049 if (nop) { 1050 str.append("]--optimized away"); 1051 } 1052 int length = str.length() + 1; 1053 ret = static_cast<char*>(arena_->Alloc(length, kArenaAllocDFInfo)); 1054 strncpy(ret, str.c_str(), length); 1055 return ret; 1056} 1057 1058/* Turn method name into a legal Linux file name */ 1059void MIRGraph::ReplaceSpecialChars(std::string& str) { 1060 static const struct { const char before; const char after; } match[] = { 1061 {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, 1062 {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} 1063 }; 1064 for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { 1065 std::replace(str.begin(), str.end(), match[i].before, match[i].after); 1066 } 1067} 1068 1069std::string MIRGraph::GetSSAName(int ssa_reg) { 1070 // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to 1071 // the arena. We should be smarter and just place straight into the arena, or compute the 1072 // value more lazily. 1073 return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 1074} 1075 1076// Similar to GetSSAName, but if ssa name represents an immediate show that as well. 1077std::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { 1078 if (reg_location_ == NULL) { 1079 // Pre-SSA - just use the standard name 1080 return GetSSAName(ssa_reg); 1081 } 1082 if (IsConst(reg_location_[ssa_reg])) { 1083 if (!singles_only && reg_location_[ssa_reg].wide) { 1084 return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 1085 ConstantValueWide(reg_location_[ssa_reg])); 1086 } else { 1087 return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 1088 ConstantValue(reg_location_[ssa_reg])); 1089 } 1090 } else { 1091 return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 1092 } 1093} 1094 1095void MIRGraph::GetBlockName(BasicBlock* bb, char* name) { 1096 switch (bb->block_type) { 1097 case kEntryBlock: 1098 snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); 1099 break; 1100 case kExitBlock: 1101 snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); 1102 break; 1103 case kDalvikByteCode: 1104 snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); 1105 break; 1106 case kExceptionHandling: 1107 snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, 1108 bb->id); 1109 break; 1110 default: 1111 snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); 1112 break; 1113 } 1114} 1115 1116const char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { 1117 // TODO: for inlining support, use current code unit. 1118 const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); 1119 return cu_->dex_file->GetShorty(method_id.proto_idx_); 1120} 1121 1122/* Debug Utility - dump a compilation unit */ 1123void MIRGraph::DumpMIRGraph() { 1124 BasicBlock* bb; 1125 const char* block_type_names[] = { 1126 "Null Block", 1127 "Entry Block", 1128 "Code Block", 1129 "Exit Block", 1130 "Exception Handling", 1131 "Catch Block" 1132 }; 1133 1134 LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); 1135 LOG(INFO) << cu_->insns << " insns"; 1136 LOG(INFO) << GetNumBlocks() << " blocks in total"; 1137 GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 1138 1139 while (true) { 1140 bb = iterator.Next(); 1141 if (bb == NULL) break; 1142 LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", 1143 bb->id, 1144 block_type_names[bb->block_type], 1145 bb->start_offset, 1146 bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, 1147 bb->last_mir_insn ? "" : " empty"); 1148 if (bb->taken != NullBasicBlockId) { 1149 LOG(INFO) << " Taken branch: block " << bb->taken 1150 << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; 1151 } 1152 if (bb->fall_through != NullBasicBlockId) { 1153 LOG(INFO) << " Fallthrough : block " << bb->fall_through 1154 << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; 1155 } 1156 } 1157} 1158 1159/* 1160 * Build an array of location records for the incoming arguments. 1161 * Note: one location record per word of arguments, with dummy 1162 * high-word loc for wide arguments. Also pull up any following 1163 * MOVE_RESULT and incorporate it into the invoke. 1164 */ 1165CallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, 1166 bool is_range) { 1167 CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), 1168 kArenaAllocMisc)); 1169 MIR* move_result_mir = FindMoveResult(bb, mir); 1170 if (move_result_mir == NULL) { 1171 info->result.location = kLocInvalid; 1172 } else { 1173 info->result = GetRawDest(move_result_mir); 1174 move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); 1175 } 1176 info->num_arg_words = mir->ssa_rep->num_uses; 1177 info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> 1178 (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, kArenaAllocMisc)); 1179 for (int i = 0; i < info->num_arg_words; i++) { 1180 info->args[i] = GetRawSrc(mir, i); 1181 } 1182 info->opt_flags = mir->optimization_flags; 1183 info->type = type; 1184 info->is_range = is_range; 1185 info->index = mir->dalvikInsn.vB; 1186 info->offset = mir->offset; 1187 info->mir = mir; 1188 return info; 1189} 1190 1191// Allocate a new basic block. 1192BasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { 1193 BasicBlock* bb = static_cast<BasicBlock*>(arena_->Alloc(sizeof(BasicBlock), 1194 kArenaAllocBB)); 1195 bb->block_type = block_type; 1196 bb->id = block_id; 1197 // TUNING: better estimate of the exit block predecessors? 1198 bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, 1199 (block_type == kExitBlock) ? 2048 : 2, 1200 kGrowableArrayPredecessors); 1201 bb->successor_block_list_type = kNotUsed; 1202 block_id_map_.Put(block_id, block_id); 1203 return bb; 1204} 1205 1206void MIRGraph::InitializeConstantPropagation() { 1207 is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); 1208 constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), kArenaAllocDFInfo)); 1209} 1210 1211void MIRGraph::InitializeMethodUses() { 1212 // The gate starts by initializing the use counts 1213 int num_ssa_regs = GetNumSSARegs(); 1214 use_counts_.Resize(num_ssa_regs + 32); 1215 raw_use_counts_.Resize(num_ssa_regs + 32); 1216 // Initialize list 1217 for (int i = 0; i < num_ssa_regs; i++) { 1218 use_counts_.Insert(0); 1219 raw_use_counts_.Insert(0); 1220 } 1221} 1222 1223void MIRGraph::InitializeSSATransformation() { 1224 /* Compute the DFS order */ 1225 ComputeDFSOrders(); 1226 1227 /* Compute the dominator info */ 1228 ComputeDominators(); 1229 1230 /* Allocate data structures in preparation for SSA conversion */ 1231 CompilerInitializeSSAConversion(); 1232 1233 /* Find out the "Dalvik reg def x block" relation */ 1234 ComputeDefBlockMatrix(); 1235 1236 /* Insert phi nodes to dominance frontiers for all variables */ 1237 InsertPhiNodes(); 1238 1239 /* Rename register names by local defs and phi nodes */ 1240 ClearAllVisitedFlags(); 1241 DoDFSPreOrderSSARename(GetEntryBlock()); 1242} 1243 1244} // namespace art 1245