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