mir_graph.cc revision a262f7707330dccfb50af6345813083182b61043
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#include <queue> 21 22#include "base/bit_vector-inl.h" 23#include "base/stl_util.h" 24#include "compiler_internals.h" 25#include "dex_file-inl.h" 26#include "dex_instruction-inl.h" 27#include "dex/global_value_numbering.h" 28#include "dex/quick/dex_file_to_method_inliner_map.h" 29#include "dex/quick/dex_file_method_inliner.h" 30#include "leb128.h" 31#include "pass_driver_me_post_opt.h" 32#include "stack.h" 33#include "utils/scoped_arena_containers.h" 34 35namespace art { 36 37#define MAX_PATTERN_LEN 5 38 39const char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { 40 "Phi", 41 "Copy", 42 "FusedCmplFloat", 43 "FusedCmpgFloat", 44 "FusedCmplDouble", 45 "FusedCmpgDouble", 46 "FusedCmpLong", 47 "Nop", 48 "OpNullCheck", 49 "OpRangeCheck", 50 "OpDivZeroCheck", 51 "Check1", 52 "Check2", 53 "Select", 54 "ConstVector", 55 "MoveVector", 56 "PackedMultiply", 57 "PackedAddition", 58 "PackedSubtract", 59 "PackedShiftLeft", 60 "PackedSignedShiftRight", 61 "PackedUnsignedShiftRight", 62 "PackedAnd", 63 "PackedOr", 64 "PackedXor", 65 "PackedAddReduce", 66 "PackedReduce", 67 "PackedSet", 68 "ReserveVectorRegisters", 69 "ReturnVectorRegisters", 70 "MemBarrier", 71 "PackedArrayGet", 72 "PackedArrayPut", 73 "MaddInt", 74 "MsubInt", 75 "MaddLong", 76 "MsubLong", 77}; 78 79MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 80 : reg_location_(NULL), 81 block_id_map_(std::less<unsigned int>(), arena->Adapter()), 82 cu_(cu), 83 ssa_base_vregs_(arena->Adapter(kArenaAllocSSAToDalvikMap)), 84 ssa_subscripts_(arena->Adapter(kArenaAllocSSAToDalvikMap)), 85 vreg_to_ssa_map_(NULL), 86 ssa_last_defs_(NULL), 87 is_constant_v_(NULL), 88 constant_values_(NULL), 89 use_counts_(arena->Adapter()), 90 raw_use_counts_(arena->Adapter()), 91 num_reachable_blocks_(0), 92 max_num_reachable_blocks_(0), 93 dfs_orders_up_to_date_(false), 94 dfs_order_(arena->Adapter(kArenaAllocDfsPreOrder)), 95 dfs_post_order_(arena->Adapter(kArenaAllocDfsPostOrder)), 96 dom_post_order_traversal_(arena->Adapter(kArenaAllocDomPostOrder)), 97 topological_order_(arena->Adapter(kArenaAllocTopologicalSortOrder)), 98 topological_order_loop_ends_(arena->Adapter(kArenaAllocTopologicalSortOrder)), 99 topological_order_indexes_(arena->Adapter(kArenaAllocTopologicalSortOrder)), 100 topological_order_loop_head_stack_(arena->Adapter(kArenaAllocTopologicalSortOrder)), 101 max_nested_loops_(0u), 102 i_dom_list_(NULL), 103 temp_scoped_alloc_(), 104 block_list_(arena->Adapter(kArenaAllocBBList)), 105 try_block_addr_(NULL), 106 entry_block_(NULL), 107 exit_block_(NULL), 108 num_blocks_(0), 109 current_code_item_(NULL), 110 dex_pc_to_block_map_(arena->Adapter()), 111 m_units_(arena->Adapter()), 112 method_stack_(arena->Adapter()), 113 current_method_(kInvalidEntry), 114 current_offset_(kInvalidEntry), 115 def_count_(0), 116 opcode_count_(NULL), 117 num_ssa_regs_(0), 118 extended_basic_blocks_(arena->Adapter()), 119 method_sreg_(0), 120 attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. 121 checkstats_(NULL), 122 arena_(arena), 123 backward_branches_(0), 124 forward_branches_(0), 125 num_non_special_compiler_temps_(0), 126 max_available_special_compiler_temps_(1), // We only need the method ptr as a special temp for now. 127 requested_backend_temp_(false), 128 compiler_temps_committed_(false), 129 punt_to_interpreter_(false), 130 merged_df_flags_(0u), 131 ifield_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)), 132 sfield_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)), 133 method_lowering_infos_(arena->Adapter(kArenaAllocLoweringInfo)), 134 suspend_checks_in_loops_(nullptr) { 135 memset(&temp_, 0, sizeof(temp_)); 136 use_counts_.reserve(256); 137 raw_use_counts_.reserve(256); 138 block_list_.reserve(100); 139 try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); 140 141 142 if (cu_->instruction_set == kX86 || cu_->instruction_set == kX86_64) { 143 // X86 requires a temp to keep track of the method address. 144 // TODO For x86_64, addressing can be done with RIP. When that is implemented, 145 // this needs to be updated to reserve 0 temps for BE. 146 max_available_non_special_compiler_temps_ = cu_->target64 ? 2 : 1; 147 reserved_temps_for_backend_ = max_available_non_special_compiler_temps_; 148 } else { 149 // Other architectures do not have a known lower bound for non-special temps. 150 // We allow the update of the max to happen at BE initialization stage and simply set 0 for now. 151 max_available_non_special_compiler_temps_ = 0; 152 reserved_temps_for_backend_ = 0; 153 } 154} 155 156MIRGraph::~MIRGraph() { 157 STLDeleteElements(&block_list_); 158 STLDeleteElements(&m_units_); 159} 160 161/* 162 * Parse an instruction, return the length of the instruction 163 */ 164int MIRGraph::ParseInsn(const uint16_t* code_ptr, MIR::DecodedInstruction* decoded_instruction) { 165 const Instruction* inst = Instruction::At(code_ptr); 166 decoded_instruction->opcode = inst->Opcode(); 167 decoded_instruction->vA = inst->HasVRegA() ? inst->VRegA() : 0; 168 decoded_instruction->vB = inst->HasVRegB() ? inst->VRegB() : 0; 169 decoded_instruction->vB_wide = inst->HasWideVRegB() ? inst->WideVRegB() : 0; 170 decoded_instruction->vC = inst->HasVRegC() ? inst->VRegC() : 0; 171 if (inst->HasVarArgs()) { 172 inst->GetVarArgs(decoded_instruction->arg); 173 } 174 return inst->SizeInCodeUnits(); 175} 176 177 178/* Split an existing block from the specified code offset into two */ 179BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, 180 BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { 181 DCHECK_GT(code_offset, orig_block->start_offset); 182 MIR* insn = orig_block->first_mir_insn; 183 MIR* prev = NULL; // Will be set to instruction before split. 184 while (insn) { 185 if (insn->offset == code_offset) break; 186 prev = insn; 187 insn = insn->next; 188 } 189 if (insn == NULL) { 190 LOG(FATAL) << "Break split failed"; 191 } 192 // Now insn is at the instruction where we want to split, namely 193 // insn will be the first instruction of the "bottom" block. 194 // Similarly, prev will be the last instruction of the "top" block 195 196 BasicBlock* bottom_block = CreateNewBB(kDalvikByteCode); 197 198 bottom_block->start_offset = code_offset; 199 bottom_block->first_mir_insn = insn; 200 bottom_block->last_mir_insn = orig_block->last_mir_insn; 201 202 /* If this block was terminated by a return, conditional branch or throw, 203 * the flag needs to go with the bottom block 204 */ 205 bottom_block->terminated_by_return = orig_block->terminated_by_return; 206 orig_block->terminated_by_return = false; 207 208 bottom_block->conditional_branch = orig_block->conditional_branch; 209 orig_block->conditional_branch = false; 210 211 bottom_block->explicit_throw = orig_block->explicit_throw; 212 orig_block->explicit_throw = false; 213 214 /* Handle the taken path */ 215 bottom_block->taken = orig_block->taken; 216 if (bottom_block->taken != NullBasicBlockId) { 217 orig_block->taken = NullBasicBlockId; 218 BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); 219 bb_taken->ErasePredecessor(orig_block->id); 220 bb_taken->predecessors.push_back(bottom_block->id); 221 } 222 223 /* Handle the fallthrough path */ 224 bottom_block->fall_through = orig_block->fall_through; 225 orig_block->fall_through = bottom_block->id; 226 bottom_block->predecessors.push_back(orig_block->id); 227 if (bottom_block->fall_through != NullBasicBlockId) { 228 BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); 229 bb_fall_through->ErasePredecessor(orig_block->id); 230 bb_fall_through->predecessors.push_back(bottom_block->id); 231 } 232 233 /* Handle the successor list */ 234 if (orig_block->successor_block_list_type != kNotUsed) { 235 bottom_block->successor_block_list_type = orig_block->successor_block_list_type; 236 bottom_block->successor_blocks.swap(orig_block->successor_blocks); 237 orig_block->successor_block_list_type = kNotUsed; 238 DCHECK(orig_block->successor_blocks.empty()); // Empty after the swap() above. 239 for (SuccessorBlockInfo* successor_block_info : bottom_block->successor_blocks) { 240 BasicBlock* bb = GetBasicBlock(successor_block_info->block); 241 if (bb != nullptr) { 242 bb->ErasePredecessor(orig_block->id); 243 bb->predecessors.push_back(bottom_block->id); 244 } 245 } 246 } 247 248 orig_block->last_mir_insn = prev; 249 prev->next = nullptr; 250 251 /* 252 * Update the immediate predecessor block pointer so that outgoing edges 253 * can be applied to the proper block. 254 */ 255 if (immed_pred_block_p) { 256 DCHECK_EQ(*immed_pred_block_p, orig_block); 257 *immed_pred_block_p = bottom_block; 258 } 259 260 // Associate dex instructions in the bottom block with the new container. 261 DCHECK(insn != nullptr); 262 DCHECK(insn != orig_block->first_mir_insn); 263 DCHECK(insn == bottom_block->first_mir_insn); 264 DCHECK_EQ(insn->offset, bottom_block->start_offset); 265 DCHECK_EQ(dex_pc_to_block_map_[insn->offset], orig_block->id); 266 // Scan the "bottom" instructions, remapping them to the 267 // newly created "bottom" block. 268 MIR* p = insn; 269 p->bb = bottom_block->id; 270 dex_pc_to_block_map_[p->offset] = bottom_block->id; 271 while (p != bottom_block->last_mir_insn) { 272 p = p->next; 273 DCHECK(p != nullptr); 274 p->bb = bottom_block->id; 275 int opcode = p->dalvikInsn.opcode; 276 /* 277 * Some messiness here to ensure that we only enter real opcodes and only the 278 * first half of a potentially throwing instruction that has been split into 279 * CHECK and work portions. Since the 2nd half of a split operation is always 280 * the first in a BasicBlock, we can't hit it here. 281 */ 282 if ((opcode == kMirOpCheck) || !MIR::DecodedInstruction::IsPseudoMirOp(opcode)) { 283 BasicBlockId mapped_id = dex_pc_to_block_map_[p->offset]; 284 // At first glance the instructions should all be mapped to orig_block. 285 // However, multiple instructions may correspond to the same dex, hence an earlier 286 // instruction may have already moved the mapping for dex to bottom_block. 287 DCHECK((mapped_id == orig_block->id) || (mapped_id == bottom_block->id)); 288 dex_pc_to_block_map_[p->offset] = bottom_block->id; 289 } 290 } 291 292 return bottom_block; 293} 294 295/* 296 * Given a code offset, find out the block that starts with it. If the offset 297 * is in the middle of an existing block, split it into two. If immed_pred_block_p 298 * is not non-null and is the block being split, update *immed_pred_block_p to 299 * point to the bottom block so that outgoing edges can be set up properly 300 * (by the caller) 301 * Utilizes a map for fast lookup of the typical cases. 302 */ 303BasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool create, 304 BasicBlock** immed_pred_block_p) { 305 if (code_offset >= current_code_item_->insns_size_in_code_units_) { 306 return nullptr; 307 } 308 309 int block_id = dex_pc_to_block_map_[code_offset]; 310 BasicBlock* bb = GetBasicBlock(block_id); 311 312 if ((bb != nullptr) && (bb->start_offset == code_offset)) { 313 // Does this containing block start with the desired instruction? 314 return bb; 315 } 316 317 // No direct hit. 318 if (!create) { 319 return nullptr; 320 } 321 322 if (bb != nullptr) { 323 // The target exists somewhere in an existing block. 324 return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : nullptr); 325 } 326 327 // Create a new block. 328 bb = CreateNewBB(kDalvikByteCode); 329 bb->start_offset = code_offset; 330 dex_pc_to_block_map_[bb->start_offset] = bb->id; 331 return bb; 332} 333 334 335/* Identify code range in try blocks and set up the empty catch blocks */ 336void MIRGraph::ProcessTryCatchBlocks() { 337 int tries_size = current_code_item_->tries_size_; 338 DexOffset offset; 339 340 if (tries_size == 0) { 341 return; 342 } 343 344 for (int i = 0; i < tries_size; i++) { 345 const DexFile::TryItem* pTry = 346 DexFile::GetTryItems(*current_code_item_, i); 347 DexOffset start_offset = pTry->start_addr_; 348 DexOffset end_offset = start_offset + pTry->insn_count_; 349 for (offset = start_offset; offset < end_offset; offset++) { 350 try_block_addr_->SetBit(offset); 351 } 352 } 353 354 // Iterate over each of the handlers to enqueue the empty Catch blocks. 355 const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); 356 uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 357 for (uint32_t idx = 0; idx < handlers_size; idx++) { 358 CatchHandlerIterator iterator(handlers_ptr); 359 for (; iterator.HasNext(); iterator.Next()) { 360 uint32_t address = iterator.GetHandlerAddress(); 361 FindBlock(address, true /*create*/, /* immed_pred_block_p */ nullptr); 362 } 363 handlers_ptr = iterator.EndDataPointer(); 364 } 365} 366 367bool MIRGraph::IsBadMonitorExitCatch(NarrowDexOffset monitor_exit_offset, 368 NarrowDexOffset catch_offset) { 369 // Catches for monitor-exit during stack unwinding have the pattern 370 // move-exception (move)* (goto)? monitor-exit throw 371 // In the currently generated dex bytecode we see these catching a bytecode range including 372 // either its own or an identical monitor-exit, http://b/15745363 . This function checks if 373 // it's the case for a given monitor-exit and catch block so that we can ignore it. 374 // (We don't want to ignore all monitor-exit catches since one could enclose a synchronized 375 // block in a try-block and catch the NPE, Error or Throwable and we should let it through; 376 // even though a throwing monitor-exit certainly indicates a bytecode error.) 377 const Instruction* monitor_exit = Instruction::At(current_code_item_->insns_ + monitor_exit_offset); 378 DCHECK(monitor_exit->Opcode() == Instruction::MONITOR_EXIT); 379 int monitor_reg = monitor_exit->VRegA_11x(); 380 const Instruction* check_insn = Instruction::At(current_code_item_->insns_ + catch_offset); 381 DCHECK(check_insn->Opcode() == Instruction::MOVE_EXCEPTION); 382 if (check_insn->VRegA_11x() == monitor_reg) { 383 // Unexpected move-exception to the same register. Probably not the pattern we're looking for. 384 return false; 385 } 386 check_insn = check_insn->Next(); 387 while (true) { 388 int dest = -1; 389 bool wide = false; 390 switch (check_insn->Opcode()) { 391 case Instruction::MOVE_WIDE: 392 wide = true; 393 FALLTHROUGH_INTENDED; 394 case Instruction::MOVE_OBJECT: 395 case Instruction::MOVE: 396 dest = check_insn->VRegA_12x(); 397 break; 398 399 case Instruction::MOVE_WIDE_FROM16: 400 wide = true; 401 FALLTHROUGH_INTENDED; 402 case Instruction::MOVE_OBJECT_FROM16: 403 case Instruction::MOVE_FROM16: 404 dest = check_insn->VRegA_22x(); 405 break; 406 407 case Instruction::MOVE_WIDE_16: 408 wide = true; 409 FALLTHROUGH_INTENDED; 410 case Instruction::MOVE_OBJECT_16: 411 case Instruction::MOVE_16: 412 dest = check_insn->VRegA_32x(); 413 break; 414 415 case Instruction::GOTO: 416 case Instruction::GOTO_16: 417 case Instruction::GOTO_32: 418 check_insn = check_insn->RelativeAt(check_insn->GetTargetOffset()); 419 FALLTHROUGH_INTENDED; 420 default: 421 return check_insn->Opcode() == Instruction::MONITOR_EXIT && 422 check_insn->VRegA_11x() == monitor_reg; 423 } 424 425 if (dest == monitor_reg || (wide && dest + 1 == monitor_reg)) { 426 return false; 427 } 428 429 check_insn = check_insn->Next(); 430 } 431} 432 433/* Process instructions with the kBranch flag */ 434BasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 435 int width, int flags, const uint16_t* code_ptr, 436 const uint16_t* code_end) { 437 DexOffset target = cur_offset; 438 switch (insn->dalvikInsn.opcode) { 439 case Instruction::GOTO: 440 case Instruction::GOTO_16: 441 case Instruction::GOTO_32: 442 target += insn->dalvikInsn.vA; 443 break; 444 case Instruction::IF_EQ: 445 case Instruction::IF_NE: 446 case Instruction::IF_LT: 447 case Instruction::IF_GE: 448 case Instruction::IF_GT: 449 case Instruction::IF_LE: 450 cur_block->conditional_branch = true; 451 target += insn->dalvikInsn.vC; 452 break; 453 case Instruction::IF_EQZ: 454 case Instruction::IF_NEZ: 455 case Instruction::IF_LTZ: 456 case Instruction::IF_GEZ: 457 case Instruction::IF_GTZ: 458 case Instruction::IF_LEZ: 459 cur_block->conditional_branch = true; 460 target += insn->dalvikInsn.vB; 461 break; 462 default: 463 LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; 464 } 465 CountBranch(target); 466 BasicBlock* taken_block = FindBlock(target, /* create */ true, 467 /* immed_pred_block_p */ &cur_block); 468 cur_block->taken = taken_block->id; 469 taken_block->predecessors.push_back(cur_block->id); 470 471 /* Always terminate the current block for conditional branches */ 472 if (flags & Instruction::kContinue) { 473 BasicBlock* fallthrough_block = FindBlock(cur_offset + width, 474 /* create */ 475 true, 476 /* immed_pred_block_p */ 477 &cur_block); 478 cur_block->fall_through = fallthrough_block->id; 479 fallthrough_block->predecessors.push_back(cur_block->id); 480 } else if (code_ptr < code_end) { 481 FindBlock(cur_offset + width, /* create */ true, /* immed_pred_block_p */ nullptr); 482 } 483 return cur_block; 484} 485 486/* Process instructions with the kSwitch flag */ 487BasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 488 int width, int flags) { 489 UNUSED(flags); 490 const uint16_t* switch_data = 491 reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); 492 int size; 493 const int* keyTable; 494 const int* target_table; 495 int i; 496 int first_key; 497 498 /* 499 * Packed switch data format: 500 * ushort ident = 0x0100 magic value 501 * ushort size number of entries in the table 502 * int first_key first (and lowest) switch case value 503 * int targets[size] branch targets, relative to switch opcode 504 * 505 * Total size is (4+size*2) 16-bit code units. 506 */ 507 if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { 508 DCHECK_EQ(static_cast<int>(switch_data[0]), 509 static_cast<int>(Instruction::kPackedSwitchSignature)); 510 size = switch_data[1]; 511 first_key = switch_data[2] | (switch_data[3] << 16); 512 target_table = reinterpret_cast<const int*>(&switch_data[4]); 513 keyTable = NULL; // Make the compiler happy. 514 /* 515 * Sparse switch data format: 516 * ushort ident = 0x0200 magic value 517 * ushort size number of entries in the table; > 0 518 * int keys[size] keys, sorted low-to-high; 32-bit aligned 519 * int targets[size] branch targets, relative to switch opcode 520 * 521 * Total size is (2+size*4) 16-bit code units. 522 */ 523 } else { 524 DCHECK_EQ(static_cast<int>(switch_data[0]), 525 static_cast<int>(Instruction::kSparseSwitchSignature)); 526 size = switch_data[1]; 527 keyTable = reinterpret_cast<const int*>(&switch_data[2]); 528 target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); 529 first_key = 0; // To make the compiler happy. 530 } 531 532 if (cur_block->successor_block_list_type != kNotUsed) { 533 LOG(FATAL) << "Successor block list already in use: " 534 << static_cast<int>(cur_block->successor_block_list_type); 535 } 536 cur_block->successor_block_list_type = 537 (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; 538 cur_block->successor_blocks.reserve(size); 539 540 for (i = 0; i < size; i++) { 541 BasicBlock* case_block = FindBlock(cur_offset + target_table[i], /* create */ true, 542 /* immed_pred_block_p */ &cur_block); 543 SuccessorBlockInfo* successor_block_info = 544 static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), 545 kArenaAllocSuccessor)); 546 successor_block_info->block = case_block->id; 547 successor_block_info->key = 548 (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 549 first_key + i : keyTable[i]; 550 cur_block->successor_blocks.push_back(successor_block_info); 551 case_block->predecessors.push_back(cur_block->id); 552 } 553 554 /* Fall-through case */ 555 BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* create */ true, 556 /* immed_pred_block_p */ nullptr); 557 cur_block->fall_through = fallthrough_block->id; 558 fallthrough_block->predecessors.push_back(cur_block->id); 559 return cur_block; 560} 561 562/* Process instructions with the kThrow flag */ 563BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 564 int width, int flags, ArenaBitVector* try_block_addr, 565 const uint16_t* code_ptr, const uint16_t* code_end) { 566 UNUSED(flags); 567 bool in_try_block = try_block_addr->IsBitSet(cur_offset); 568 bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); 569 570 /* In try block */ 571 if (in_try_block) { 572 CatchHandlerIterator iterator(*current_code_item_, cur_offset); 573 574 if (cur_block->successor_block_list_type != kNotUsed) { 575 LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 576 LOG(FATAL) << "Successor block list already in use: " 577 << static_cast<int>(cur_block->successor_block_list_type); 578 } 579 580 for (; iterator.HasNext(); iterator.Next()) { 581 BasicBlock* catch_block = FindBlock(iterator.GetHandlerAddress(), false /* create */, 582 nullptr /* immed_pred_block_p */); 583 if (insn->dalvikInsn.opcode == Instruction::MONITOR_EXIT && 584 IsBadMonitorExitCatch(insn->offset, catch_block->start_offset)) { 585 // Don't allow monitor-exit to catch its own exception, http://b/15745363 . 586 continue; 587 } 588 if (cur_block->successor_block_list_type == kNotUsed) { 589 cur_block->successor_block_list_type = kCatch; 590 } 591 catch_block->catch_entry = true; 592 if (kIsDebugBuild) { 593 catches_.insert(catch_block->start_offset); 594 } 595 SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 596 (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 597 successor_block_info->block = catch_block->id; 598 successor_block_info->key = iterator.GetHandlerTypeIndex(); 599 cur_block->successor_blocks.push_back(successor_block_info); 600 catch_block->predecessors.push_back(cur_block->id); 601 } 602 in_try_block = (cur_block->successor_block_list_type != kNotUsed); 603 } 604 bool build_all_edges = 605 (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; 606 if (!in_try_block && build_all_edges) { 607 BasicBlock* eh_block = CreateNewBB(kExceptionHandling); 608 cur_block->taken = eh_block->id; 609 eh_block->start_offset = cur_offset; 610 eh_block->predecessors.push_back(cur_block->id); 611 } 612 613 if (is_throw) { 614 cur_block->explicit_throw = true; 615 if (code_ptr < code_end) { 616 // Force creation of new block following THROW via side-effect. 617 FindBlock(cur_offset + width, /* create */ true, /* immed_pred_block_p */ nullptr); 618 } 619 if (!in_try_block) { 620 // Don't split a THROW that can't rethrow - we're done. 621 return cur_block; 622 } 623 } 624 625 if (!build_all_edges) { 626 /* 627 * Even though there is an exception edge here, control cannot return to this 628 * method. Thus, for the purposes of dataflow analysis and optimization, we can 629 * ignore the edge. Doing this reduces compile time, and increases the scope 630 * of the basic-block level optimization pass. 631 */ 632 return cur_block; 633 } 634 635 /* 636 * Split the potentially-throwing instruction into two parts. 637 * The first half will be a pseudo-op that captures the exception 638 * edges and terminates the basic block. It always falls through. 639 * Then, create a new basic block that begins with the throwing instruction 640 * (minus exceptions). Note: this new basic block must NOT be entered into 641 * the block_map. If the potentially-throwing instruction is the target of a 642 * future branch, we need to find the check psuedo half. The new 643 * basic block containing the work portion of the instruction should 644 * only be entered via fallthrough from the block containing the 645 * pseudo exception edge MIR. Note also that this new block is 646 * not automatically terminated after the work portion, and may 647 * contain following instructions. 648 * 649 * Note also that the dex_pc_to_block_map_ entry for the potentially 650 * throwing instruction will refer to the original basic block. 651 */ 652 BasicBlock* new_block = CreateNewBB(kDalvikByteCode); 653 new_block->start_offset = insn->offset; 654 cur_block->fall_through = new_block->id; 655 new_block->predecessors.push_back(cur_block->id); 656 MIR* new_insn = NewMIR(); 657 *new_insn = *insn; 658 insn->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpCheck); 659 // Associate the two halves. 660 insn->meta.throw_insn = new_insn; 661 new_block->AppendMIR(new_insn); 662 return new_block; 663} 664 665/* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ 666void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 667 InvokeType invoke_type, uint16_t class_def_idx, 668 uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { 669 current_code_item_ = code_item; 670 method_stack_.push_back(std::make_pair(current_method_, current_offset_)); 671 current_method_ = m_units_.size(); 672 current_offset_ = 0; 673 // TODO: will need to snapshot stack image and use that as the mir context identification. 674 m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), 675 dex_file, current_code_item_, class_def_idx, method_idx, access_flags, 676 cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); 677 const uint16_t* code_ptr = current_code_item_->insns_; 678 const uint16_t* code_end = 679 current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; 680 681 // TODO: need to rework expansion of block list & try_block_addr when inlining activated. 682 // TUNING: use better estimate of basic blocks for following resize. 683 block_list_.reserve(block_list_.size() + current_code_item_->insns_size_in_code_units_); 684 dex_pc_to_block_map_.resize(dex_pc_to_block_map_.size() + current_code_item_->insns_size_in_code_units_); 685 686 // TODO: replace with explicit resize routine. Using automatic extension side effect for now. 687 try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); 688 try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); 689 690 // If this is the first method, set up default entry and exit blocks. 691 if (current_method_ == 0) { 692 DCHECK(entry_block_ == NULL); 693 DCHECK(exit_block_ == NULL); 694 DCHECK_EQ(num_blocks_, 0U); 695 // Use id 0 to represent a null block. 696 BasicBlock* null_block = CreateNewBB(kNullBlock); 697 DCHECK_EQ(null_block->id, NullBasicBlockId); 698 null_block->hidden = true; 699 entry_block_ = CreateNewBB(kEntryBlock); 700 exit_block_ = CreateNewBB(kExitBlock); 701 // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. 702 cu_->dex_file = &dex_file; 703 cu_->class_def_idx = class_def_idx; 704 cu_->method_idx = method_idx; 705 cu_->access_flags = access_flags; 706 cu_->invoke_type = invoke_type; 707 cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); 708 } else { 709 UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; 710 /* 711 * Will need to manage storage for ins & outs, push prevous state and update 712 * insert point. 713 */ 714 } 715 716 /* Current block to record parsed instructions */ 717 BasicBlock* cur_block = CreateNewBB(kDalvikByteCode); 718 DCHECK_EQ(current_offset_, 0U); 719 cur_block->start_offset = current_offset_; 720 // TODO: for inlining support, insert at the insert point rather than entry block. 721 entry_block_->fall_through = cur_block->id; 722 cur_block->predecessors.push_back(entry_block_->id); 723 724 /* Identify code range in try blocks and set up the empty catch blocks */ 725 ProcessTryCatchBlocks(); 726 727 uint64_t merged_df_flags = 0u; 728 729 /* Parse all instructions and put them into containing basic blocks */ 730 while (code_ptr < code_end) { 731 MIR *insn = NewMIR(); 732 insn->offset = current_offset_; 733 insn->m_unit_index = current_method_; 734 int width = ParseInsn(code_ptr, &insn->dalvikInsn); 735 Instruction::Code opcode = insn->dalvikInsn.opcode; 736 if (opcode_count_ != NULL) { 737 opcode_count_[static_cast<int>(opcode)]++; 738 } 739 740 int flags = insn->dalvikInsn.FlagsOf(); 741 int verify_flags = Instruction::VerifyFlagsOf(insn->dalvikInsn.opcode); 742 743 uint64_t df_flags = GetDataFlowAttributes(insn); 744 merged_df_flags |= df_flags; 745 746 if (df_flags & DF_HAS_DEFS) { 747 def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; 748 } 749 750 if (df_flags & DF_LVN) { 751 cur_block->use_lvn = true; // Run local value numbering on this basic block. 752 } 753 754 // Check for inline data block signatures. 755 if (opcode == Instruction::NOP) { 756 // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. 757 if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { 758 // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. 759 uint16_t following_raw_instruction = code_ptr[1]; 760 if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || 761 (following_raw_instruction == Instruction::kPackedSwitchSignature) || 762 (following_raw_instruction == Instruction::kArrayDataSignature)) { 763 width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); 764 } 765 } 766 if (width == 1) { 767 // It is a simple nop - treat normally. 768 cur_block->AppendMIR(insn); 769 } else { 770 DCHECK(cur_block->fall_through == NullBasicBlockId); 771 DCHECK(cur_block->taken == NullBasicBlockId); 772 // Unreachable instruction, mark for no continuation and end basic block. 773 flags &= ~Instruction::kContinue; 774 FindBlock(current_offset_ + width, /* create */ true, /* immed_pred_block_p */ nullptr); 775 } 776 } else { 777 cur_block->AppendMIR(insn); 778 } 779 780 // Associate the starting dex_pc for this opcode with its containing basic block. 781 dex_pc_to_block_map_[insn->offset] = cur_block->id; 782 783 code_ptr += width; 784 785 if (flags & Instruction::kBranch) { 786 cur_block = ProcessCanBranch(cur_block, insn, current_offset_, 787 width, flags, code_ptr, code_end); 788 } else if (flags & Instruction::kReturn) { 789 cur_block->terminated_by_return = true; 790 cur_block->fall_through = exit_block_->id; 791 exit_block_->predecessors.push_back(cur_block->id); 792 /* 793 * Terminate the current block if there are instructions 794 * afterwards. 795 */ 796 if (code_ptr < code_end) { 797 /* 798 * Create a fallthrough block for real instructions 799 * (incl. NOP). 800 */ 801 FindBlock(current_offset_ + width, /* create */ true, /* immed_pred_block_p */ nullptr); 802 } 803 } else if (flags & Instruction::kThrow) { 804 cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, 805 code_ptr, code_end); 806 } else if (flags & Instruction::kSwitch) { 807 cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); 808 } 809 if (verify_flags & Instruction::kVerifyVarArgRange || 810 verify_flags & Instruction::kVerifyVarArgRangeNonZero) { 811 /* 812 * The Quick backend's runtime model includes a gap between a method's 813 * argument ("in") vregs and the rest of its vregs. Handling a range instruction 814 * which spans the gap is somewhat complicated, and should not happen 815 * in normal usage of dx. Punt to the interpreter. 816 */ 817 int first_reg_in_range = insn->dalvikInsn.vC; 818 int last_reg_in_range = first_reg_in_range + insn->dalvikInsn.vA - 1; 819 if (IsInVReg(first_reg_in_range) != IsInVReg(last_reg_in_range)) { 820 punt_to_interpreter_ = true; 821 } 822 } 823 current_offset_ += width; 824 BasicBlock* next_block = FindBlock(current_offset_, /* create */ false, 825 /* immed_pred_block_p */ nullptr); 826 if (next_block) { 827 /* 828 * The next instruction could be the target of a previously parsed 829 * forward branch so a block is already created. If the current 830 * instruction is not an unconditional branch, connect them through 831 * the fall-through link. 832 */ 833 DCHECK(cur_block->fall_through == NullBasicBlockId || 834 GetBasicBlock(cur_block->fall_through) == next_block || 835 GetBasicBlock(cur_block->fall_through) == exit_block_); 836 837 if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { 838 cur_block->fall_through = next_block->id; 839 next_block->predecessors.push_back(cur_block->id); 840 } 841 cur_block = next_block; 842 } 843 } 844 merged_df_flags_ = merged_df_flags; 845 846 if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 847 DumpCFG("/sdcard/1_post_parse_cfg/", true); 848 } 849 850 if (cu_->verbose) { 851 DumpMIRGraph(); 852 } 853} 854 855void MIRGraph::ShowOpcodeStats() { 856 DCHECK(opcode_count_ != NULL); 857 LOG(INFO) << "Opcode Count"; 858 for (int i = 0; i < kNumPackedOpcodes; i++) { 859 if (opcode_count_[i] != 0) { 860 LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) 861 << " " << opcode_count_[i]; 862 } 863 } 864} 865 866uint64_t MIRGraph::GetDataFlowAttributes(Instruction::Code opcode) { 867 DCHECK_LT((size_t) opcode, (sizeof(oat_data_flow_attributes_) / sizeof(oat_data_flow_attributes_[0]))); 868 return oat_data_flow_attributes_[opcode]; 869} 870 871uint64_t MIRGraph::GetDataFlowAttributes(MIR* mir) { 872 DCHECK(mir != nullptr); 873 Instruction::Code opcode = mir->dalvikInsn.opcode; 874 return GetDataFlowAttributes(opcode); 875} 876 877// TODO: use a configurable base prefix, and adjust callers to supply pass name. 878/* Dump the CFG into a DOT graph */ 879void MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { 880 FILE* file; 881 static AtomicInteger cnt(0); 882 883 // Increment counter to get a unique file number. 884 cnt++; 885 886 std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); 887 ReplaceSpecialChars(fname); 888 fname = StringPrintf("%s%s%x%s_%d.dot", dir_prefix, fname.c_str(), 889 GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, 890 suffix == nullptr ? "" : suffix, 891 cnt.LoadRelaxed()); 892 file = fopen(fname.c_str(), "w"); 893 if (file == NULL) { 894 return; 895 } 896 fprintf(file, "digraph G {\n"); 897 898 fprintf(file, " rankdir=TB\n"); 899 900 int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; 901 int idx; 902 903 for (idx = 0; idx < num_blocks; idx++) { 904 int block_idx = all_blocks ? idx : dfs_order_[idx]; 905 BasicBlock* bb = GetBasicBlock(block_idx); 906 if (bb == NULL) continue; 907 if (bb->block_type == kDead) continue; 908 if (bb->hidden) continue; 909 if (bb->block_type == kEntryBlock) { 910 fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); 911 } else if (bb->block_type == kExitBlock) { 912 fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); 913 } else if (bb->block_type == kDalvikByteCode) { 914 fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", 915 bb->start_offset, bb->id); 916 const MIR* mir; 917 fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 918 bb->first_mir_insn ? " | " : " "); 919 for (mir = bb->first_mir_insn; mir; mir = mir->next) { 920 int opcode = mir->dalvikInsn.opcode; 921 fprintf(file, " {%04x %s %s %s %s %s %s %s %s %s\\l}%s\\\n", mir->offset, 922 mir->ssa_rep ? GetDalvikDisassembly(mir) : 923 !MIR::DecodedInstruction::IsPseudoMirOp(opcode) ? 924 Instruction::Name(mir->dalvikInsn.opcode) : 925 extended_mir_op_names_[opcode - kMirOpFirst], 926 (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", 927 (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", 928 (mir->optimization_flags & MIR_IGNORE_SUSPEND_CHECK) != 0 ? " no_suspendcheck" : " ", 929 (mir->optimization_flags & MIR_STORE_NON_TEMPORAL) != 0 ? " non_temporal" : " ", 930 (mir->optimization_flags & MIR_CALLEE) != 0 ? " inlined" : " ", 931 (mir->optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0 ? " cl_inited" : " ", 932 (mir->optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0 ? " cl_in_cache" : " ", 933 (mir->optimization_flags & MIR_IGNORE_DIV_ZERO_CHECK) != 0 ? " no_div_check" : " ", 934 mir->next ? " | " : " "); 935 } 936 fprintf(file, " }\"];\n\n"); 937 } else if (bb->block_type == kExceptionHandling) { 938 char block_name[BLOCK_NAME_LEN]; 939 940 GetBlockName(bb, block_name); 941 fprintf(file, " %s [shape=invhouse];\n", block_name); 942 } 943 944 char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 945 946 if (bb->taken != NullBasicBlockId) { 947 GetBlockName(bb, block_name1); 948 GetBlockName(GetBasicBlock(bb->taken), block_name2); 949 fprintf(file, " %s:s -> %s:n [style=dotted]\n", 950 block_name1, block_name2); 951 } 952 if (bb->fall_through != NullBasicBlockId) { 953 GetBlockName(bb, block_name1); 954 GetBlockName(GetBasicBlock(bb->fall_through), block_name2); 955 fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); 956 } 957 958 if (bb->successor_block_list_type != kNotUsed) { 959 fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", 960 bb->start_offset, bb->id, 961 (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); 962 963 int last_succ_id = static_cast<int>(bb->successor_blocks.size() - 1u); 964 int succ_id = 0; 965 for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) { 966 BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 967 fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 968 succ_id, 969 successor_block_info->key, 970 dest_block->start_offset, 971 (succ_id != last_succ_id) ? " | " : " "); 972 ++succ_id; 973 } 974 fprintf(file, " }\"];\n\n"); 975 976 GetBlockName(bb, block_name1); 977 fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", 978 block_name1, bb->start_offset, bb->id); 979 980 // Link the successor pseudo-block with all of its potential targets. 981 succ_id = 0; 982 for (SuccessorBlockInfo* successor_block_info : bb->successor_blocks) { 983 BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 984 985 GetBlockName(dest_block, block_name2); 986 fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, 987 bb->id, succ_id++, block_name2); 988 } 989 } 990 fprintf(file, "\n"); 991 992 if (cu_->verbose) { 993 /* Display the dominator tree */ 994 GetBlockName(bb, block_name1); 995 fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 996 block_name1, block_name1); 997 if (bb->i_dom) { 998 GetBlockName(GetBasicBlock(bb->i_dom), block_name2); 999 fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); 1000 } 1001 } 1002 } 1003 fprintf(file, "}\n"); 1004 fclose(file); 1005} 1006 1007/* Insert an MIR instruction to the end of a basic block. */ 1008void BasicBlock::AppendMIR(MIR* mir) { 1009 // Insert it after the last MIR. 1010 InsertMIRListAfter(last_mir_insn, mir, mir); 1011} 1012 1013void BasicBlock::AppendMIRList(MIR* first_list_mir, MIR* last_list_mir) { 1014 // Insert it after the last MIR. 1015 InsertMIRListAfter(last_mir_insn, first_list_mir, last_list_mir); 1016} 1017 1018void BasicBlock::AppendMIRList(const std::vector<MIR*>& insns) { 1019 for (std::vector<MIR*>::const_iterator it = insns.begin(); it != insns.end(); it++) { 1020 MIR* new_mir = *it; 1021 1022 // Add a copy of each MIR. 1023 InsertMIRListAfter(last_mir_insn, new_mir, new_mir); 1024 } 1025} 1026 1027/* Insert a MIR instruction after the specified MIR. */ 1028void BasicBlock::InsertMIRAfter(MIR* current_mir, MIR* new_mir) { 1029 InsertMIRListAfter(current_mir, new_mir, new_mir); 1030} 1031 1032void BasicBlock::InsertMIRListAfter(MIR* insert_after, MIR* first_list_mir, MIR* last_list_mir) { 1033 // If no MIR, we are done. 1034 if (first_list_mir == nullptr || last_list_mir == nullptr) { 1035 return; 1036 } 1037 1038 // If insert_after is null, assume BB is empty. 1039 if (insert_after == nullptr) { 1040 first_mir_insn = first_list_mir; 1041 last_mir_insn = last_list_mir; 1042 last_list_mir->next = nullptr; 1043 } else { 1044 MIR* after_list = insert_after->next; 1045 insert_after->next = first_list_mir; 1046 last_list_mir->next = after_list; 1047 if (after_list == nullptr) { 1048 last_mir_insn = last_list_mir; 1049 } 1050 } 1051 1052 // Set this BB to be the basic block of the MIRs. 1053 MIR* last = last_list_mir->next; 1054 for (MIR* mir = first_list_mir; mir != last; mir = mir->next) { 1055 mir->bb = id; 1056 } 1057} 1058 1059/* Insert an MIR instruction to the head of a basic block. */ 1060void BasicBlock::PrependMIR(MIR* mir) { 1061 InsertMIRListBefore(first_mir_insn, mir, mir); 1062} 1063 1064void BasicBlock::PrependMIRList(MIR* first_list_mir, MIR* last_list_mir) { 1065 // Insert it before the first MIR. 1066 InsertMIRListBefore(first_mir_insn, first_list_mir, last_list_mir); 1067} 1068 1069void BasicBlock::PrependMIRList(const std::vector<MIR*>& to_add) { 1070 for (std::vector<MIR*>::const_iterator it = to_add.begin(); it != to_add.end(); it++) { 1071 MIR* mir = *it; 1072 1073 InsertMIRListBefore(first_mir_insn, mir, mir); 1074 } 1075} 1076 1077/* Insert a MIR instruction before the specified MIR. */ 1078void BasicBlock::InsertMIRBefore(MIR* current_mir, MIR* new_mir) { 1079 // Insert as a single element list. 1080 return InsertMIRListBefore(current_mir, new_mir, new_mir); 1081} 1082 1083MIR* BasicBlock::FindPreviousMIR(MIR* mir) { 1084 MIR* current = first_mir_insn; 1085 1086 while (current != nullptr) { 1087 MIR* next = current->next; 1088 1089 if (next == mir) { 1090 return current; 1091 } 1092 1093 current = next; 1094 } 1095 1096 return nullptr; 1097} 1098 1099void BasicBlock::InsertMIRListBefore(MIR* insert_before, MIR* first_list_mir, MIR* last_list_mir) { 1100 // If no MIR, we are done. 1101 if (first_list_mir == nullptr || last_list_mir == nullptr) { 1102 return; 1103 } 1104 1105 // If insert_before is null, assume BB is empty. 1106 if (insert_before == nullptr) { 1107 first_mir_insn = first_list_mir; 1108 last_mir_insn = last_list_mir; 1109 last_list_mir->next = nullptr; 1110 } else { 1111 if (first_mir_insn == insert_before) { 1112 last_list_mir->next = first_mir_insn; 1113 first_mir_insn = first_list_mir; 1114 } else { 1115 // Find the preceding MIR. 1116 MIR* before_list = FindPreviousMIR(insert_before); 1117 DCHECK(before_list != nullptr); 1118 before_list->next = first_list_mir; 1119 last_list_mir->next = insert_before; 1120 } 1121 } 1122 1123 // Set this BB to be the basic block of the MIRs. 1124 for (MIR* mir = first_list_mir; mir != last_list_mir->next; mir = mir->next) { 1125 mir->bb = id; 1126 } 1127} 1128 1129bool BasicBlock::RemoveMIR(MIR* mir) { 1130 // Remove as a single element list. 1131 return RemoveMIRList(mir, mir); 1132} 1133 1134bool BasicBlock::RemoveMIRList(MIR* first_list_mir, MIR* last_list_mir) { 1135 if (first_list_mir == nullptr) { 1136 return false; 1137 } 1138 1139 // Try to find the MIR. 1140 MIR* before_list = nullptr; 1141 MIR* after_list = nullptr; 1142 1143 // If we are removing from the beginning of the MIR list. 1144 if (first_mir_insn == first_list_mir) { 1145 before_list = nullptr; 1146 } else { 1147 before_list = FindPreviousMIR(first_list_mir); 1148 if (before_list == nullptr) { 1149 // We did not find the mir. 1150 return false; 1151 } 1152 } 1153 1154 // Remove the BB information and also find the after_list. 1155 for (MIR* mir = first_list_mir; mir != last_list_mir->next; mir = mir->next) { 1156 mir->bb = NullBasicBlockId; 1157 } 1158 1159 after_list = last_list_mir->next; 1160 1161 // If there is nothing before the list, after_list is the first_mir. 1162 if (before_list == nullptr) { 1163 first_mir_insn = after_list; 1164 } else { 1165 before_list->next = after_list; 1166 } 1167 1168 // If there is nothing after the list, before_list is last_mir. 1169 if (after_list == nullptr) { 1170 last_mir_insn = before_list; 1171 } 1172 1173 return true; 1174} 1175 1176MIR* BasicBlock::GetFirstNonPhiInsn() { 1177 MIR* mir = first_mir_insn; 1178 while (mir != nullptr && static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi) { 1179 mir = mir->next; 1180 } 1181 return mir; 1182} 1183 1184MIR* BasicBlock::GetNextUnconditionalMir(MIRGraph* mir_graph, MIR* current) { 1185 MIR* next_mir = nullptr; 1186 1187 if (current != nullptr) { 1188 next_mir = current->next; 1189 } 1190 1191 if (next_mir == nullptr) { 1192 // Only look for next MIR that follows unconditionally. 1193 if ((taken == NullBasicBlockId) && (fall_through != NullBasicBlockId)) { 1194 next_mir = mir_graph->GetBasicBlock(fall_through)->first_mir_insn; 1195 } 1196 } 1197 1198 return next_mir; 1199} 1200 1201static void FillTypeSizeString(uint32_t type_size, std::string* decoded_mir) { 1202 DCHECK(decoded_mir != nullptr); 1203 OpSize type = static_cast<OpSize>(type_size >> 16); 1204 uint16_t vect_size = (type_size & 0xFFFF); 1205 1206 // Now print the type and vector size. 1207 std::stringstream ss; 1208 ss << " (type:"; 1209 ss << type; 1210 ss << " vectsize:"; 1211 ss << vect_size; 1212 ss << ")"; 1213 1214 decoded_mir->append(ss.str()); 1215} 1216 1217void MIRGraph::DisassembleExtendedInstr(const MIR* mir, std::string* decoded_mir) { 1218 DCHECK(decoded_mir != nullptr); 1219 int opcode = mir->dalvikInsn.opcode; 1220 SSARepresentation* ssa_rep = mir->ssa_rep; 1221 int defs = (ssa_rep != nullptr) ? ssa_rep->num_defs : 0; 1222 int uses = (ssa_rep != nullptr) ? ssa_rep->num_uses : 0; 1223 1224 if (opcode < kMirOpFirst) { 1225 return; // It is not an extended instruction. 1226 } 1227 1228 decoded_mir->append(extended_mir_op_names_[opcode - kMirOpFirst]); 1229 1230 switch (opcode) { 1231 case kMirOpPhi: { 1232 if (defs > 0 && uses > 0) { 1233 BasicBlockId* incoming = mir->meta.phi_incoming; 1234 decoded_mir->append(StringPrintf(" %s = (%s", 1235 GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), 1236 GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); 1237 decoded_mir->append(StringPrintf(":%d", incoming[0])); 1238 for (int i = 1; i < uses; i++) { 1239 decoded_mir->append(StringPrintf(", %s:%d", GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), incoming[i])); 1240 } 1241 decoded_mir->append(")"); 1242 } 1243 break; 1244 } 1245 case kMirOpCopy: 1246 if (ssa_rep != nullptr) { 1247 decoded_mir->append(" "); 1248 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[0], false)); 1249 if (defs > 1) { 1250 decoded_mir->append(", "); 1251 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[1], false)); 1252 } 1253 decoded_mir->append(" = "); 1254 decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[0], false)); 1255 if (uses > 1) { 1256 decoded_mir->append(", "); 1257 decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[1], false)); 1258 } 1259 } else { 1260 decoded_mir->append(StringPrintf(" v%d = v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1261 } 1262 break; 1263 case kMirOpFusedCmplFloat: 1264 case kMirOpFusedCmpgFloat: 1265 case kMirOpFusedCmplDouble: 1266 case kMirOpFusedCmpgDouble: 1267 case kMirOpFusedCmpLong: 1268 if (ssa_rep != nullptr) { 1269 decoded_mir->append(" "); 1270 decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[0], false)); 1271 for (int i = 1; i < uses; i++) { 1272 decoded_mir->append(", "); 1273 decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[i], false)); 1274 } 1275 } else { 1276 decoded_mir->append(StringPrintf(" v%d, v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1277 } 1278 break; 1279 case kMirOpMoveVector: 1280 decoded_mir->append(StringPrintf(" vect%d = vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1281 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1282 break; 1283 case kMirOpPackedAddition: 1284 decoded_mir->append(StringPrintf(" vect%d = vect%d + vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1285 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1286 break; 1287 case kMirOpPackedMultiply: 1288 decoded_mir->append(StringPrintf(" vect%d = vect%d * vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1289 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1290 break; 1291 case kMirOpPackedSubtract: 1292 decoded_mir->append(StringPrintf(" vect%d = vect%d - vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1293 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1294 break; 1295 case kMirOpPackedAnd: 1296 decoded_mir->append(StringPrintf(" vect%d = vect%d & vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1297 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1298 break; 1299 case kMirOpPackedOr: 1300 decoded_mir->append(StringPrintf(" vect%d = vect%d \\| vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1301 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1302 break; 1303 case kMirOpPackedXor: 1304 decoded_mir->append(StringPrintf(" vect%d = vect%d ^ vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1305 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1306 break; 1307 case kMirOpPackedShiftLeft: 1308 decoded_mir->append(StringPrintf(" vect%d = vect%d \\<\\< %d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1309 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1310 break; 1311 case kMirOpPackedUnsignedShiftRight: 1312 decoded_mir->append(StringPrintf(" vect%d = vect%d \\>\\>\\> %d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1313 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1314 break; 1315 case kMirOpPackedSignedShiftRight: 1316 decoded_mir->append(StringPrintf(" vect%d = vect%d \\>\\> %d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1317 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1318 break; 1319 case kMirOpConstVector: 1320 decoded_mir->append(StringPrintf(" vect%d = %x, %x, %x, %x", mir->dalvikInsn.vA, mir->dalvikInsn.arg[0], 1321 mir->dalvikInsn.arg[1], mir->dalvikInsn.arg[2], mir->dalvikInsn.arg[3])); 1322 break; 1323 case kMirOpPackedSet: 1324 if (ssa_rep != nullptr) { 1325 decoded_mir->append(StringPrintf(" vect%d = %s", mir->dalvikInsn.vA, 1326 GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 1327 if (uses > 1) { 1328 decoded_mir->append(", "); 1329 decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[1], false)); 1330 } 1331 } else { 1332 decoded_mir->append(StringPrintf(" vect%d = v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1333 } 1334 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1335 break; 1336 case kMirOpPackedAddReduce: 1337 if (ssa_rep != nullptr) { 1338 decoded_mir->append(" "); 1339 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[0], false)); 1340 if (defs > 1) { 1341 decoded_mir->append(", "); 1342 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[1], false)); 1343 } 1344 decoded_mir->append(StringPrintf(" = vect%d + %s", mir->dalvikInsn.vB, 1345 GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 1346 if (uses > 1) { 1347 decoded_mir->append(", "); 1348 decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[1], false)); 1349 } 1350 } else { 1351 decoded_mir->append(StringPrintf("v%d = vect%d + v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB, mir->dalvikInsn.vA)); 1352 } 1353 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1354 break; 1355 case kMirOpPackedReduce: 1356 if (ssa_rep != nullptr) { 1357 decoded_mir->append(" "); 1358 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[0], false)); 1359 if (defs > 1) { 1360 decoded_mir->append(", "); 1361 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[1], false)); 1362 } 1363 decoded_mir->append(StringPrintf(" = vect%d (extr_idx:%d)", mir->dalvikInsn.vB, mir->dalvikInsn.arg[0])); 1364 } else { 1365 decoded_mir->append(StringPrintf(" v%d = vect%d (extr_idx:%d)", mir->dalvikInsn.vA, 1366 mir->dalvikInsn.vB, mir->dalvikInsn.arg[0])); 1367 } 1368 FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); 1369 break; 1370 case kMirOpReserveVectorRegisters: 1371 case kMirOpReturnVectorRegisters: 1372 decoded_mir->append(StringPrintf(" vect%d - vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); 1373 break; 1374 case kMirOpMemBarrier: { 1375 decoded_mir->append(" type:"); 1376 std::stringstream ss; 1377 ss << static_cast<MemBarrierKind>(mir->dalvikInsn.vA); 1378 decoded_mir->append(ss.str()); 1379 break; 1380 } 1381 case kMirOpPackedArrayGet: 1382 case kMirOpPackedArrayPut: 1383 decoded_mir->append(StringPrintf(" vect%d", mir->dalvikInsn.vA)); 1384 if (ssa_rep != nullptr) { 1385 decoded_mir->append(StringPrintf(", %s[%s]", 1386 GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), 1387 GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); 1388 } else { 1389 decoded_mir->append(StringPrintf(", v%d[v%d]", mir->dalvikInsn.vB, mir->dalvikInsn.vC)); 1390 } 1391 FillTypeSizeString(mir->dalvikInsn.arg[0], decoded_mir); 1392 break; 1393 case kMirOpMaddInt: 1394 case kMirOpMsubInt: 1395 case kMirOpMaddLong: 1396 case kMirOpMsubLong: 1397 if (ssa_rep != nullptr) { 1398 decoded_mir->append(" "); 1399 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[0], false)); 1400 if (defs > 1) { 1401 decoded_mir->append(", "); 1402 decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[1], false)); 1403 } 1404 for (int i = 0; i < uses; i++) { 1405 decoded_mir->append(", "); 1406 decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[i], false)); 1407 } 1408 } else { 1409 decoded_mir->append(StringPrintf(" v%d, v%d, v%d, v%d", 1410 mir->dalvikInsn.vA, mir->dalvikInsn.vB, 1411 mir->dalvikInsn.vC, mir->dalvikInsn.arg[0])); 1412 } 1413 break; 1414 default: 1415 break; 1416 } 1417} 1418 1419char* MIRGraph::GetDalvikDisassembly(const MIR* mir) { 1420 MIR::DecodedInstruction insn = mir->dalvikInsn; 1421 std::string str; 1422 int flags = 0; 1423 int opcode = insn.opcode; 1424 char* ret; 1425 bool nop = false; 1426 SSARepresentation* ssa_rep = mir->ssa_rep; 1427 Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format. 1428 1429 // Handle special cases that recover the original dalvik instruction. 1430 if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { 1431 str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 1432 str.append(": "); 1433 // Recover the original Dex instruction. 1434 insn = mir->meta.throw_insn->dalvikInsn; 1435 ssa_rep = mir->meta.throw_insn->ssa_rep; 1436 opcode = insn.opcode; 1437 } else if (opcode == kMirOpNop) { 1438 str.append("["); 1439 if (mir->offset < current_code_item_->insns_size_in_code_units_) { 1440 // Recover original opcode. 1441 insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); 1442 opcode = insn.opcode; 1443 } 1444 nop = true; 1445 } 1446 int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; 1447 int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; 1448 1449 if (MIR::DecodedInstruction::IsPseudoMirOp(opcode)) { 1450 // Note that this does not check the MIR's opcode in all cases. In cases where it 1451 // recovered dalvik instruction, it uses opcode of that instead of the extended one. 1452 DisassembleExtendedInstr(mir, &str); 1453 } else { 1454 dalvik_format = Instruction::FormatOf(insn.opcode); 1455 flags = insn.FlagsOf(); 1456 str.append(Instruction::Name(insn.opcode)); 1457 1458 // For invokes-style formats, treat wide regs as a pair of singles. 1459 bool show_singles = ((dalvik_format == Instruction::k35c) || 1460 (dalvik_format == Instruction::k3rc)); 1461 if (defs != 0) { 1462 str.append(" "); 1463 str.append(GetSSANameWithConst(ssa_rep->defs[0], false)); 1464 if (defs > 1) { 1465 str.append(", "); 1466 str.append(GetSSANameWithConst(ssa_rep->defs[1], false)); 1467 } 1468 if (uses != 0) { 1469 str.append(", "); 1470 } 1471 } 1472 for (int i = 0; i < uses; i++) { 1473 str.append(" "); 1474 str.append(GetSSANameWithConst(ssa_rep->uses[i], show_singles)); 1475 if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { 1476 // For the listing, skip the high sreg. 1477 i++; 1478 } 1479 if (i != (uses - 1)) { 1480 str.append(","); 1481 } 1482 } 1483 1484 switch (dalvik_format) { 1485 case Instruction::k11n: // Add one immediate from vB. 1486 case Instruction::k21s: 1487 case Instruction::k31i: 1488 case Instruction::k21h: 1489 str.append(StringPrintf(", #0x%x", insn.vB)); 1490 break; 1491 case Instruction::k51l: // Add one wide immediate. 1492 str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); 1493 break; 1494 case Instruction::k21c: // One register, one string/type/method index. 1495 case Instruction::k31c: 1496 str.append(StringPrintf(", index #0x%x", insn.vB)); 1497 break; 1498 case Instruction::k22c: // Two registers, one string/type/method index. 1499 str.append(StringPrintf(", index #0x%x", insn.vC)); 1500 break; 1501 case Instruction::k22s: // Add one immediate from vC. 1502 case Instruction::k22b: 1503 str.append(StringPrintf(", #0x%x", insn.vC)); 1504 break; 1505 default: 1506 // Nothing left to print. 1507 break; 1508 } 1509 1510 if ((flags & Instruction::kBranch) != 0) { 1511 // For branches, decode the instructions to print out the branch targets. 1512 int offset = 0; 1513 switch (dalvik_format) { 1514 case Instruction::k21t: 1515 offset = insn.vB; 1516 break; 1517 case Instruction::k22t: 1518 offset = insn.vC; 1519 break; 1520 case Instruction::k10t: 1521 case Instruction::k20t: 1522 case Instruction::k30t: 1523 offset = insn.vA; 1524 break; 1525 default: 1526 LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; 1527 break; 1528 } 1529 str.append(StringPrintf(", 0x%x (%c%x)", mir->offset + offset, 1530 offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); 1531 } 1532 1533 if (nop) { 1534 str.append("]--optimized away"); 1535 } 1536 } 1537 int length = str.length() + 1; 1538 ret = static_cast<char*>(arena_->Alloc(length, kArenaAllocDFInfo)); 1539 strncpy(ret, str.c_str(), length); 1540 return ret; 1541} 1542 1543/* Turn method name into a legal Linux file name */ 1544void MIRGraph::ReplaceSpecialChars(std::string& str) { 1545 static const struct { const char before; const char after; } match[] = { 1546 {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, 1547 {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} 1548 }; 1549 for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { 1550 std::replace(str.begin(), str.end(), match[i].before, match[i].after); 1551 } 1552} 1553 1554std::string MIRGraph::GetSSAName(int ssa_reg) { 1555 // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to 1556 // the arena. We should be smarter and just place straight into the arena, or compute the 1557 // value more lazily. 1558 int vreg = SRegToVReg(ssa_reg); 1559 if (vreg >= static_cast<int>(GetFirstTempVR())) { 1560 return StringPrintf("t%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 1561 } else { 1562 return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 1563 } 1564} 1565 1566// Similar to GetSSAName, but if ssa name represents an immediate show that as well. 1567std::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { 1568 if (reg_location_ == NULL) { 1569 // Pre-SSA - just use the standard name. 1570 return GetSSAName(ssa_reg); 1571 } 1572 if (IsConst(reg_location_[ssa_reg])) { 1573 if (!singles_only && reg_location_[ssa_reg].wide && 1574 !reg_location_[ssa_reg].high_word) { 1575 return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 1576 ConstantValueWide(reg_location_[ssa_reg])); 1577 } else { 1578 return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 1579 ConstantValue(reg_location_[ssa_reg])); 1580 } 1581 } else { 1582 int vreg = SRegToVReg(ssa_reg); 1583 if (vreg >= static_cast<int>(GetFirstTempVR())) { 1584 return StringPrintf("t%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 1585 } else { 1586 return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 1587 } 1588 } 1589} 1590 1591void MIRGraph::GetBlockName(BasicBlock* bb, char* name) { 1592 switch (bb->block_type) { 1593 case kEntryBlock: 1594 snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); 1595 break; 1596 case kExitBlock: 1597 snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); 1598 break; 1599 case kDalvikByteCode: 1600 snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); 1601 break; 1602 case kExceptionHandling: 1603 snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, 1604 bb->id); 1605 break; 1606 default: 1607 snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); 1608 break; 1609 } 1610} 1611 1612const char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { 1613 // TODO: for inlining support, use current code unit. 1614 const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); 1615 return cu_->dex_file->GetShorty(method_id.proto_idx_); 1616} 1617 1618const char* MIRGraph::GetShortyFromMethodReference(const MethodReference& target_method) { 1619 const DexFile::MethodId& method_id = 1620 target_method.dex_file->GetMethodId(target_method.dex_method_index); 1621 return target_method.dex_file->GetShorty(method_id.proto_idx_); 1622} 1623 1624/* Debug Utility - dump a compilation unit */ 1625void MIRGraph::DumpMIRGraph() { 1626 const char* block_type_names[] = { 1627 "Null Block", 1628 "Entry Block", 1629 "Code Block", 1630 "Exit Block", 1631 "Exception Handling", 1632 "Catch Block" 1633 }; 1634 1635 LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); 1636 LOG(INFO) << GetInsns(0) << " insns"; 1637 LOG(INFO) << GetNumBlocks() << " blocks in total"; 1638 1639 for (BasicBlock* bb : block_list_) { 1640 LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", 1641 bb->id, 1642 block_type_names[bb->block_type], 1643 bb->start_offset, 1644 bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, 1645 bb->last_mir_insn ? "" : " empty"); 1646 if (bb->taken != NullBasicBlockId) { 1647 LOG(INFO) << " Taken branch: block " << bb->taken 1648 << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; 1649 } 1650 if (bb->fall_through != NullBasicBlockId) { 1651 LOG(INFO) << " Fallthrough : block " << bb->fall_through 1652 << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; 1653 } 1654 } 1655} 1656 1657/* 1658 * Build an array of location records for the incoming arguments. 1659 * Note: one location record per word of arguments, with dummy 1660 * high-word loc for wide arguments. Also pull up any following 1661 * MOVE_RESULT and incorporate it into the invoke. 1662 */ 1663CallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, 1664 bool is_range) { 1665 CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), 1666 kArenaAllocMisc)); 1667 MIR* move_result_mir = FindMoveResult(bb, mir); 1668 if (move_result_mir == NULL) { 1669 info->result.location = kLocInvalid; 1670 } else { 1671 info->result = GetRawDest(move_result_mir); 1672 move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); 1673 } 1674 info->num_arg_words = mir->ssa_rep->num_uses; 1675 info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> 1676 (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, kArenaAllocMisc)); 1677 for (int i = 0; i < info->num_arg_words; i++) { 1678 info->args[i] = GetRawSrc(mir, i); 1679 } 1680 info->opt_flags = mir->optimization_flags; 1681 info->type = type; 1682 info->is_range = is_range; 1683 info->index = mir->dalvikInsn.vB; 1684 info->offset = mir->offset; 1685 info->mir = mir; 1686 return info; 1687} 1688 1689// Allocate a new MIR. 1690MIR* MIRGraph::NewMIR() { 1691 MIR* mir = new (arena_) MIR(); 1692 return mir; 1693} 1694 1695// Allocate a new basic block. 1696BasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { 1697 BasicBlock* bb = new (arena_) BasicBlock(block_id, block_type, arena_); 1698 1699 // TUNING: better estimate of the exit block predecessors? 1700 bb->predecessors.reserve((block_type == kExitBlock) ? 2048 : 2); 1701 block_id_map_.Put(block_id, block_id); 1702 return bb; 1703} 1704 1705void MIRGraph::InitializeConstantPropagation() { 1706 is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); 1707 constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), kArenaAllocDFInfo)); 1708} 1709 1710void MIRGraph::InitializeMethodUses() { 1711 // The gate starts by initializing the use counts. 1712 int num_ssa_regs = GetNumSSARegs(); 1713 use_counts_.clear(); 1714 use_counts_.reserve(num_ssa_regs + 32); 1715 use_counts_.resize(num_ssa_regs, 0u); 1716 raw_use_counts_.clear(); 1717 raw_use_counts_.reserve(num_ssa_regs + 32); 1718 raw_use_counts_.resize(num_ssa_regs, 0u); 1719} 1720 1721void MIRGraph::SSATransformationStart() { 1722 DCHECK(temp_scoped_alloc_.get() == nullptr); 1723 temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack)); 1724 temp_.ssa.num_vregs = GetNumOfCodeAndTempVRs(); 1725 temp_.ssa.work_live_vregs = new (temp_scoped_alloc_.get()) ArenaBitVector( 1726 temp_scoped_alloc_.get(), temp_.ssa.num_vregs, false, kBitMapRegisterV); 1727} 1728 1729void MIRGraph::SSATransformationEnd() { 1730 // Verify the dataflow information after the pass. 1731 if (cu_->enable_debug & (1 << kDebugVerifyDataflow)) { 1732 VerifyDataflow(); 1733 } 1734 1735 temp_.ssa.num_vregs = 0u; 1736 temp_.ssa.work_live_vregs = nullptr; 1737 temp_.ssa.def_block_matrix = nullptr; 1738 DCHECK(temp_scoped_alloc_.get() != nullptr); 1739 temp_scoped_alloc_.reset(); 1740 1741 // Update the maximum number of reachable blocks. 1742 max_num_reachable_blocks_ = num_reachable_blocks_; 1743} 1744 1745size_t MIRGraph::GetNumDalvikInsns() const { 1746 size_t cumulative_size = 0u; 1747 bool counted_current_item = false; 1748 const uint8_t size_for_null_code_item = 2u; 1749 1750 for (auto it : m_units_) { 1751 const DexFile::CodeItem* code_item = it->GetCodeItem(); 1752 // Even if the code item is null, we still count non-zero value so that 1753 // each m_unit is counted as having impact. 1754 cumulative_size += (code_item == nullptr ? 1755 size_for_null_code_item : code_item->insns_size_in_code_units_); 1756 if (code_item == current_code_item_) { 1757 counted_current_item = true; 1758 } 1759 } 1760 1761 // If the current code item was not counted yet, count it now. 1762 // This can happen for example in unit tests where some fields like m_units_ 1763 // are not initialized. 1764 if (counted_current_item == false) { 1765 cumulative_size += (current_code_item_ == nullptr ? 1766 size_for_null_code_item : current_code_item_->insns_size_in_code_units_); 1767 } 1768 1769 return cumulative_size; 1770} 1771 1772static BasicBlock* SelectTopologicalSortOrderFallBack( 1773 MIRGraph* mir_graph, const ArenaBitVector* current_loop, 1774 const ScopedArenaVector<size_t>* visited_cnt_values, ScopedArenaAllocator* allocator, 1775 ScopedArenaVector<BasicBlockId>* tmp_stack) { 1776 // No true loop head has been found but there may be true loop heads after the mess we need 1777 // to resolve. To avoid taking one of those, pick the candidate with the highest number of 1778 // reachable unvisited nodes. That candidate will surely be a part of a loop. 1779 BasicBlock* fall_back = nullptr; 1780 size_t fall_back_num_reachable = 0u; 1781 // Reuse the same bit vector for each candidate to mark reachable unvisited blocks. 1782 ArenaBitVector candidate_reachable(allocator, mir_graph->GetNumBlocks(), false, kBitMapMisc); 1783 AllNodesIterator iter(mir_graph); 1784 for (BasicBlock* candidate = iter.Next(); candidate != nullptr; candidate = iter.Next()) { 1785 if (candidate->hidden || // Hidden, or 1786 candidate->visited || // already processed, or 1787 (*visited_cnt_values)[candidate->id] == 0u || // no processed predecessors, or 1788 (current_loop != nullptr && // outside current loop. 1789 !current_loop->IsBitSet(candidate->id))) { 1790 continue; 1791 } 1792 DCHECK(tmp_stack->empty()); 1793 tmp_stack->push_back(candidate->id); 1794 candidate_reachable.ClearAllBits(); 1795 size_t num_reachable = 0u; 1796 while (!tmp_stack->empty()) { 1797 BasicBlockId current_id = tmp_stack->back(); 1798 tmp_stack->pop_back(); 1799 BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id); 1800 DCHECK(current_bb != nullptr); 1801 ChildBlockIterator child_iter(current_bb, mir_graph); 1802 BasicBlock* child_bb = child_iter.Next(); 1803 for ( ; child_bb != nullptr; child_bb = child_iter.Next()) { 1804 DCHECK(!child_bb->hidden); 1805 if (child_bb->visited || // Already processed, or 1806 (current_loop != nullptr && // outside current loop. 1807 !current_loop->IsBitSet(child_bb->id))) { 1808 continue; 1809 } 1810 if (!candidate_reachable.IsBitSet(child_bb->id)) { 1811 candidate_reachable.SetBit(child_bb->id); 1812 tmp_stack->push_back(child_bb->id); 1813 num_reachable += 1u; 1814 } 1815 } 1816 } 1817 if (fall_back_num_reachable < num_reachable) { 1818 fall_back_num_reachable = num_reachable; 1819 fall_back = candidate; 1820 } 1821 } 1822 return fall_back; 1823} 1824 1825// Compute from which unvisited blocks is bb_id reachable through unvisited blocks. 1826static void ComputeUnvisitedReachableFrom(MIRGraph* mir_graph, BasicBlockId bb_id, 1827 ArenaBitVector* reachable, 1828 ScopedArenaVector<BasicBlockId>* tmp_stack) { 1829 // NOTE: Loop heads indicated by the "visited" flag. 1830 DCHECK(tmp_stack->empty()); 1831 reachable->ClearAllBits(); 1832 tmp_stack->push_back(bb_id); 1833 while (!tmp_stack->empty()) { 1834 BasicBlockId current_id = tmp_stack->back(); 1835 tmp_stack->pop_back(); 1836 BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id); 1837 DCHECK(current_bb != nullptr); 1838 for (BasicBlockId pred_id : current_bb->predecessors) { 1839 BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id); 1840 DCHECK(pred_bb != nullptr); 1841 if (!pred_bb->visited && !reachable->IsBitSet(pred_bb->id)) { 1842 reachable->SetBit(pred_bb->id); 1843 tmp_stack->push_back(pred_bb->id); 1844 } 1845 } 1846 } 1847} 1848 1849void MIRGraph::ComputeTopologicalSortOrder() { 1850 ScopedArenaAllocator allocator(&cu_->arena_stack); 1851 unsigned int num_blocks = GetNumBlocks(); 1852 1853 ScopedArenaQueue<BasicBlock*> q(allocator.Adapter()); 1854 ScopedArenaVector<size_t> visited_cnt_values(num_blocks, 0u, allocator.Adapter()); 1855 ScopedArenaVector<BasicBlockId> loop_head_stack(allocator.Adapter()); 1856 size_t max_nested_loops = 0u; 1857 ArenaBitVector loop_exit_blocks(&allocator, num_blocks, false, kBitMapMisc); 1858 loop_exit_blocks.ClearAllBits(); 1859 1860 // Count the number of blocks to process and add the entry block(s). 1861 unsigned int num_blocks_to_process = 0u; 1862 for (BasicBlock* bb : block_list_) { 1863 if (bb->hidden == true) { 1864 continue; 1865 } 1866 1867 num_blocks_to_process += 1u; 1868 1869 if (bb->predecessors.size() == 0u) { 1870 // Add entry block to the queue. 1871 q.push(bb); 1872 } 1873 } 1874 1875 // Clear the topological order arrays. 1876 topological_order_.clear(); 1877 topological_order_.reserve(num_blocks); 1878 topological_order_loop_ends_.clear(); 1879 topological_order_loop_ends_.resize(num_blocks, 0u); 1880 topological_order_indexes_.clear(); 1881 topological_order_indexes_.resize(num_blocks, static_cast<uint16_t>(-1)); 1882 1883 // Mark all blocks as unvisited. 1884 ClearAllVisitedFlags(); 1885 1886 // For loop heads, keep track from which blocks they are reachable not going through other 1887 // loop heads. Other loop heads are excluded to detect the heads of nested loops. The children 1888 // in this set go into the loop body, the other children are jumping over the loop. 1889 ScopedArenaVector<ArenaBitVector*> loop_head_reachable_from(allocator.Adapter()); 1890 loop_head_reachable_from.resize(num_blocks, nullptr); 1891 // Reuse the same temp stack whenever calculating a loop_head_reachable_from[loop_head_id]. 1892 ScopedArenaVector<BasicBlockId> tmp_stack(allocator.Adapter()); 1893 1894 while (num_blocks_to_process != 0u) { 1895 BasicBlock* bb = nullptr; 1896 if (!q.empty()) { 1897 num_blocks_to_process -= 1u; 1898 // Get top. 1899 bb = q.front(); 1900 q.pop(); 1901 if (bb->visited) { 1902 // Loop head: it was already processed, mark end and copy exit blocks to the queue. 1903 DCHECK(q.empty()) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 1904 uint16_t idx = static_cast<uint16_t>(topological_order_.size()); 1905 topological_order_loop_ends_[topological_order_indexes_[bb->id]] = idx; 1906 DCHECK_EQ(loop_head_stack.back(), bb->id); 1907 loop_head_stack.pop_back(); 1908 ArenaBitVector* reachable = 1909 loop_head_stack.empty() ? nullptr : loop_head_reachable_from[loop_head_stack.back()]; 1910 for (BasicBlockId candidate_id : loop_exit_blocks.Indexes()) { 1911 if (reachable == nullptr || reachable->IsBitSet(candidate_id)) { 1912 q.push(GetBasicBlock(candidate_id)); 1913 // NOTE: The BitVectorSet::IndexIterator will not check the pointed-to bit again, 1914 // so clearing the bit has no effect on the iterator. 1915 loop_exit_blocks.ClearBit(candidate_id); 1916 } 1917 } 1918 continue; 1919 } 1920 } else { 1921 // Find the new loop head. 1922 AllNodesIterator iter(this); 1923 while (true) { 1924 BasicBlock* candidate = iter.Next(); 1925 if (candidate == nullptr) { 1926 // We did not find a true loop head, fall back to a reachable block in any loop. 1927 ArenaBitVector* current_loop = 1928 loop_head_stack.empty() ? nullptr : loop_head_reachable_from[loop_head_stack.back()]; 1929 bb = SelectTopologicalSortOrderFallBack(this, current_loop, &visited_cnt_values, 1930 &allocator, &tmp_stack); 1931 DCHECK(bb != nullptr) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 1932 if (kIsDebugBuild && cu_->dex_file != nullptr) { 1933 LOG(INFO) << "Topological sort order: Using fall-back in " 1934 << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " BB #" << bb->id 1935 << " @0x" << std::hex << bb->start_offset 1936 << ", num_blocks = " << std::dec << num_blocks; 1937 } 1938 break; 1939 } 1940 if (candidate->hidden || // Hidden, or 1941 candidate->visited || // already processed, or 1942 visited_cnt_values[candidate->id] == 0u || // no processed predecessors, or 1943 (!loop_head_stack.empty() && // outside current loop. 1944 !loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(candidate->id))) { 1945 continue; 1946 } 1947 1948 for (BasicBlockId pred_id : candidate->predecessors) { 1949 BasicBlock* pred_bb = GetBasicBlock(pred_id); 1950 DCHECK(pred_bb != nullptr); 1951 if (pred_bb != candidate && !pred_bb->visited && 1952 !pred_bb->dominators->IsBitSet(candidate->id)) { 1953 candidate = nullptr; // Set candidate to null to indicate failure. 1954 break; 1955 } 1956 } 1957 if (candidate != nullptr) { 1958 bb = candidate; 1959 break; 1960 } 1961 } 1962 // Compute blocks from which the loop head is reachable and process those blocks first. 1963 ArenaBitVector* reachable = 1964 new (&allocator) ArenaBitVector(&allocator, num_blocks, false, kBitMapMisc); 1965 loop_head_reachable_from[bb->id] = reachable; 1966 ComputeUnvisitedReachableFrom(this, bb->id, reachable, &tmp_stack); 1967 // Now mark as loop head. (Even if it's only a fall back when we don't find a true loop.) 1968 loop_head_stack.push_back(bb->id); 1969 max_nested_loops = std::max(max_nested_loops, loop_head_stack.size()); 1970 } 1971 1972 DCHECK_EQ(bb->hidden, false); 1973 DCHECK_EQ(bb->visited, false); 1974 bb->visited = true; 1975 bb->nesting_depth = loop_head_stack.size(); 1976 1977 // Now add the basic block. 1978 uint16_t idx = static_cast<uint16_t>(topological_order_.size()); 1979 topological_order_indexes_[bb->id] = idx; 1980 topological_order_.push_back(bb->id); 1981 1982 // Update visited_cnt_values for children. 1983 ChildBlockIterator succIter(bb, this); 1984 BasicBlock* successor = succIter.Next(); 1985 for ( ; successor != nullptr; successor = succIter.Next()) { 1986 if (successor->hidden) { 1987 continue; 1988 } 1989 1990 // One more predecessor was visited. 1991 visited_cnt_values[successor->id] += 1u; 1992 if (visited_cnt_values[successor->id] == successor->predecessors.size()) { 1993 if (loop_head_stack.empty() || 1994 loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(successor->id)) { 1995 q.push(successor); 1996 } else { 1997 DCHECK(!loop_exit_blocks.IsBitSet(successor->id)); 1998 loop_exit_blocks.SetBit(successor->id); 1999 } 2000 } 2001 } 2002 } 2003 2004 // Prepare the loop head stack for iteration. 2005 topological_order_loop_head_stack_.clear(); 2006 topological_order_loop_head_stack_.reserve(max_nested_loops); 2007 max_nested_loops_ = max_nested_loops; 2008} 2009 2010bool BasicBlock::IsExceptionBlock() const { 2011 if (block_type == kExceptionHandling) { 2012 return true; 2013 } 2014 return false; 2015} 2016 2017ChildBlockIterator::ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph) 2018 : basic_block_(bb), mir_graph_(mir_graph), visited_fallthrough_(false), 2019 visited_taken_(false), have_successors_(false) { 2020 // Check if we actually do have successors. 2021 if (basic_block_ != 0 && basic_block_->successor_block_list_type != kNotUsed) { 2022 have_successors_ = true; 2023 successor_iter_ = basic_block_->successor_blocks.cbegin(); 2024 } 2025} 2026 2027BasicBlock* ChildBlockIterator::Next() { 2028 // We check if we have a basic block. If we don't we cannot get next child. 2029 if (basic_block_ == nullptr) { 2030 return nullptr; 2031 } 2032 2033 // If we haven't visited fallthrough, return that. 2034 if (visited_fallthrough_ == false) { 2035 visited_fallthrough_ = true; 2036 2037 BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->fall_through); 2038 if (result != nullptr) { 2039 return result; 2040 } 2041 } 2042 2043 // If we haven't visited taken, return that. 2044 if (visited_taken_ == false) { 2045 visited_taken_ = true; 2046 2047 BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->taken); 2048 if (result != nullptr) { 2049 return result; 2050 } 2051 } 2052 2053 // We visited both taken and fallthrough. Now check if we have successors we need to visit. 2054 if (have_successors_ == true) { 2055 // Get information about next successor block. 2056 auto end = basic_block_->successor_blocks.cend(); 2057 while (successor_iter_ != end) { 2058 SuccessorBlockInfo* successor_block_info = *successor_iter_; 2059 ++successor_iter_; 2060 // If block was replaced by zero block, take next one. 2061 if (successor_block_info->block != NullBasicBlockId) { 2062 return mir_graph_->GetBasicBlock(successor_block_info->block); 2063 } 2064 } 2065 } 2066 2067 // We do not have anything. 2068 return nullptr; 2069} 2070 2071BasicBlock* BasicBlock::Copy(CompilationUnit* c_unit) { 2072 MIRGraph* mir_graph = c_unit->mir_graph.get(); 2073 return Copy(mir_graph); 2074} 2075 2076BasicBlock* BasicBlock::Copy(MIRGraph* mir_graph) { 2077 BasicBlock* result_bb = mir_graph->CreateNewBB(block_type); 2078 2079 // We don't do a memcpy style copy here because it would lead to a lot of things 2080 // to clean up. Let us do it by hand instead. 2081 // Copy in taken and fallthrough. 2082 result_bb->fall_through = fall_through; 2083 result_bb->taken = taken; 2084 2085 // Copy successor links if needed. 2086 ArenaAllocator* arena = mir_graph->GetArena(); 2087 2088 result_bb->successor_block_list_type = successor_block_list_type; 2089 if (result_bb->successor_block_list_type != kNotUsed) { 2090 result_bb->successor_blocks.reserve(successor_blocks.size()); 2091 for (SuccessorBlockInfo* sbi_old : successor_blocks) { 2092 SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>( 2093 arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 2094 memcpy(sbi_new, sbi_old, sizeof(SuccessorBlockInfo)); 2095 result_bb->successor_blocks.push_back(sbi_new); 2096 } 2097 } 2098 2099 // Copy offset, method. 2100 result_bb->start_offset = start_offset; 2101 2102 // Now copy instructions. 2103 for (MIR* mir = first_mir_insn; mir != 0; mir = mir->next) { 2104 // Get a copy first. 2105 MIR* copy = mir->Copy(mir_graph); 2106 2107 // Append it. 2108 result_bb->AppendMIR(copy); 2109 } 2110 2111 return result_bb; 2112} 2113 2114MIR* MIR::Copy(MIRGraph* mir_graph) { 2115 MIR* res = mir_graph->NewMIR(); 2116 *res = *this; 2117 2118 // Remove links 2119 res->next = nullptr; 2120 res->bb = NullBasicBlockId; 2121 res->ssa_rep = nullptr; 2122 2123 return res; 2124} 2125 2126MIR* MIR::Copy(CompilationUnit* c_unit) { 2127 return Copy(c_unit->mir_graph.get()); 2128} 2129 2130uint32_t SSARepresentation::GetStartUseIndex(Instruction::Code opcode) { 2131 // Default result. 2132 int res = 0; 2133 2134 // We are basically setting the iputs to their igets counterparts. 2135 switch (opcode) { 2136 case Instruction::IPUT: 2137 case Instruction::IPUT_OBJECT: 2138 case Instruction::IPUT_BOOLEAN: 2139 case Instruction::IPUT_BYTE: 2140 case Instruction::IPUT_CHAR: 2141 case Instruction::IPUT_SHORT: 2142 case Instruction::IPUT_QUICK: 2143 case Instruction::IPUT_OBJECT_QUICK: 2144 case Instruction::IPUT_BOOLEAN_QUICK: 2145 case Instruction::IPUT_BYTE_QUICK: 2146 case Instruction::IPUT_CHAR_QUICK: 2147 case Instruction::IPUT_SHORT_QUICK: 2148 case Instruction::APUT: 2149 case Instruction::APUT_OBJECT: 2150 case Instruction::APUT_BOOLEAN: 2151 case Instruction::APUT_BYTE: 2152 case Instruction::APUT_CHAR: 2153 case Instruction::APUT_SHORT: 2154 case Instruction::SPUT: 2155 case Instruction::SPUT_OBJECT: 2156 case Instruction::SPUT_BOOLEAN: 2157 case Instruction::SPUT_BYTE: 2158 case Instruction::SPUT_CHAR: 2159 case Instruction::SPUT_SHORT: 2160 // Skip the VR containing what to store. 2161 res = 1; 2162 break; 2163 case Instruction::IPUT_WIDE: 2164 case Instruction::IPUT_WIDE_QUICK: 2165 case Instruction::APUT_WIDE: 2166 case Instruction::SPUT_WIDE: 2167 // Skip the two VRs containing what to store. 2168 res = 2; 2169 break; 2170 default: 2171 // Do nothing in the general case. 2172 break; 2173 } 2174 2175 return res; 2176} 2177 2178/** 2179 * @brief Given a decoded instruction, it checks whether the instruction 2180 * sets a constant and if it does, more information is provided about the 2181 * constant being set. 2182 * @param ptr_value pointer to a 64-bit holder for the constant. 2183 * @param wide Updated by function whether a wide constant is being set by bytecode. 2184 * @return Returns false if the decoded instruction does not represent a constant bytecode. 2185 */ 2186bool MIR::DecodedInstruction::GetConstant(int64_t* ptr_value, bool* wide) const { 2187 bool sets_const = true; 2188 int64_t value = vB; 2189 2190 DCHECK(ptr_value != nullptr); 2191 DCHECK(wide != nullptr); 2192 2193 switch (opcode) { 2194 case Instruction::CONST_4: 2195 case Instruction::CONST_16: 2196 case Instruction::CONST: 2197 *wide = false; 2198 value <<= 32; // In order to get the sign extend. 2199 value >>= 32; 2200 break; 2201 case Instruction::CONST_HIGH16: 2202 *wide = false; 2203 value <<= 48; // In order to get the sign extend. 2204 value >>= 32; 2205 break; 2206 case Instruction::CONST_WIDE_16: 2207 case Instruction::CONST_WIDE_32: 2208 *wide = true; 2209 value <<= 32; // In order to get the sign extend. 2210 value >>= 32; 2211 break; 2212 case Instruction::CONST_WIDE: 2213 *wide = true; 2214 value = vB_wide; 2215 break; 2216 case Instruction::CONST_WIDE_HIGH16: 2217 *wide = true; 2218 value <<= 48; // In order to get the sign extend. 2219 break; 2220 default: 2221 sets_const = false; 2222 break; 2223 } 2224 2225 if (sets_const) { 2226 *ptr_value = value; 2227 } 2228 2229 return sets_const; 2230} 2231 2232void BasicBlock::ResetOptimizationFlags(uint16_t reset_flags) { 2233 // Reset flags for all MIRs in bb. 2234 for (MIR* mir = first_mir_insn; mir != NULL; mir = mir->next) { 2235 mir->optimization_flags &= (~reset_flags); 2236 } 2237} 2238 2239void BasicBlock::Kill(MIRGraph* mir_graph) { 2240 for (BasicBlockId pred_id : predecessors) { 2241 BasicBlock* pred_bb = mir_graph->GetBasicBlock(pred_id); 2242 DCHECK(pred_bb != nullptr); 2243 2244 // Sadly we have to go through the children by hand here. 2245 pred_bb->ReplaceChild(id, NullBasicBlockId); 2246 } 2247 predecessors.clear(); 2248 2249 KillUnreachable(mir_graph); 2250} 2251 2252void BasicBlock::KillUnreachable(MIRGraph* mir_graph) { 2253 DCHECK(predecessors.empty()); // Unreachable. 2254 2255 // Mark as dead and hidden. 2256 block_type = kDead; 2257 hidden = true; 2258 2259 // Detach it from its MIRs so we don't generate code for them. Also detached MIRs 2260 // are updated to know that they no longer have a parent. 2261 for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { 2262 mir->bb = NullBasicBlockId; 2263 } 2264 first_mir_insn = nullptr; 2265 last_mir_insn = nullptr; 2266 2267 data_flow_info = nullptr; 2268 2269 // Erase this bb from all children's predecessors and kill unreachable children. 2270 ChildBlockIterator iter(this, mir_graph); 2271 for (BasicBlock* succ_bb = iter.Next(); succ_bb != nullptr; succ_bb = iter.Next()) { 2272 succ_bb->ErasePredecessor(id); 2273 if (succ_bb->predecessors.empty()) { 2274 succ_bb->KillUnreachable(mir_graph); 2275 } 2276 } 2277 2278 // Remove links to children. 2279 fall_through = NullBasicBlockId; 2280 taken = NullBasicBlockId; 2281 successor_block_list_type = kNotUsed; 2282 2283 if (kIsDebugBuild) { 2284 if (catch_entry) { 2285 DCHECK_EQ(mir_graph->catches_.count(start_offset), 1u); 2286 mir_graph->catches_.erase(start_offset); 2287 } 2288 } 2289} 2290 2291bool BasicBlock::IsSSALiveOut(const CompilationUnit* c_unit, int ssa_reg) { 2292 // In order to determine if the ssa reg is live out, we scan all the MIRs. We remember 2293 // the last SSA number of the same dalvik register. At the end, if it is different than ssa_reg, 2294 // then it is not live out of this BB. 2295 int dalvik_reg = c_unit->mir_graph->SRegToVReg(ssa_reg); 2296 2297 int last_ssa_reg = -1; 2298 2299 // Walk through the MIRs backwards. 2300 for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { 2301 // Get ssa rep. 2302 SSARepresentation *ssa_rep = mir->ssa_rep; 2303 2304 // Go through the defines for this MIR. 2305 for (int i = 0; i < ssa_rep->num_defs; i++) { 2306 DCHECK(ssa_rep->defs != nullptr); 2307 2308 // Get the ssa reg. 2309 int def_ssa_reg = ssa_rep->defs[i]; 2310 2311 // Get dalvik reg. 2312 int def_dalvik_reg = c_unit->mir_graph->SRegToVReg(def_ssa_reg); 2313 2314 // Compare dalvik regs. 2315 if (dalvik_reg == def_dalvik_reg) { 2316 // We found a def of the register that we are being asked about. 2317 // Remember it. 2318 last_ssa_reg = def_ssa_reg; 2319 } 2320 } 2321 } 2322 2323 if (last_ssa_reg == -1) { 2324 // If we get to this point we couldn't find a define of register user asked about. 2325 // Let's assume the user knows what he's doing so we can be safe and say that if we 2326 // couldn't find a def, it is live out. 2327 return true; 2328 } 2329 2330 // If it is not -1, we found a match, is it ssa_reg? 2331 return (ssa_reg == last_ssa_reg); 2332} 2333 2334bool BasicBlock::ReplaceChild(BasicBlockId old_bb, BasicBlockId new_bb) { 2335 // We need to check taken, fall_through, and successor_blocks to replace. 2336 bool found = false; 2337 if (taken == old_bb) { 2338 taken = new_bb; 2339 found = true; 2340 } 2341 2342 if (fall_through == old_bb) { 2343 fall_through = new_bb; 2344 found = true; 2345 } 2346 2347 if (successor_block_list_type != kNotUsed) { 2348 for (SuccessorBlockInfo* successor_block_info : successor_blocks) { 2349 if (successor_block_info->block == old_bb) { 2350 successor_block_info->block = new_bb; 2351 found = true; 2352 } 2353 } 2354 } 2355 2356 return found; 2357} 2358 2359void BasicBlock::ErasePredecessor(BasicBlockId old_pred) { 2360 auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred); 2361 DCHECK(pos != predecessors.end()); 2362 // It's faster to move the back() to *pos than erase(pos). 2363 *pos = predecessors.back(); 2364 predecessors.pop_back(); 2365 size_t idx = std::distance(predecessors.begin(), pos); 2366 for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { 2367 if (static_cast<int>(mir->dalvikInsn.opcode) != kMirOpPhi) { 2368 break; 2369 } 2370 DCHECK_EQ(mir->ssa_rep->num_uses - 1u, predecessors.size()); 2371 DCHECK_EQ(mir->meta.phi_incoming[idx], old_pred); 2372 mir->meta.phi_incoming[idx] = mir->meta.phi_incoming[predecessors.size()]; 2373 mir->ssa_rep->uses[idx] = mir->ssa_rep->uses[predecessors.size()]; 2374 mir->ssa_rep->num_uses = predecessors.size(); 2375 } 2376} 2377 2378void BasicBlock::UpdatePredecessor(BasicBlockId old_pred, BasicBlockId new_pred) { 2379 DCHECK_NE(new_pred, NullBasicBlockId); 2380 auto pos = std::find(predecessors.begin(), predecessors.end(), old_pred); 2381 DCHECK(pos != predecessors.end()); 2382 *pos = new_pred; 2383 size_t idx = std::distance(predecessors.begin(), pos); 2384 for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { 2385 if (static_cast<int>(mir->dalvikInsn.opcode) != kMirOpPhi) { 2386 break; 2387 } 2388 DCHECK_EQ(mir->meta.phi_incoming[idx], old_pred); 2389 mir->meta.phi_incoming[idx] = new_pred; 2390 } 2391} 2392 2393// Create a new basic block with block_id as num_blocks_ that is 2394// post-incremented. 2395BasicBlock* MIRGraph::CreateNewBB(BBType block_type) { 2396 BasicBlock* res = NewMemBB(block_type, num_blocks_++); 2397 block_list_.push_back(res); 2398 return res; 2399} 2400 2401void MIRGraph::CalculateBasicBlockInformation() { 2402 PassDriverMEPostOpt driver(cu_); 2403 driver.Launch(); 2404} 2405 2406void MIRGraph::InitializeBasicBlockData() { 2407 num_blocks_ = block_list_.size(); 2408} 2409 2410int MIR::DecodedInstruction::FlagsOf() const { 2411 // Calculate new index. 2412 int idx = static_cast<int>(opcode) - kNumPackedOpcodes; 2413 2414 // Check if it is an extended or not. 2415 if (idx < 0) { 2416 return Instruction::FlagsOf(opcode); 2417 } 2418 2419 // For extended, we use a switch. 2420 switch (static_cast<int>(opcode)) { 2421 case kMirOpPhi: 2422 return Instruction::kContinue; 2423 case kMirOpCopy: 2424 return Instruction::kContinue; 2425 case kMirOpFusedCmplFloat: 2426 return Instruction::kContinue | Instruction::kBranch; 2427 case kMirOpFusedCmpgFloat: 2428 return Instruction::kContinue | Instruction::kBranch; 2429 case kMirOpFusedCmplDouble: 2430 return Instruction::kContinue | Instruction::kBranch; 2431 case kMirOpFusedCmpgDouble: 2432 return Instruction::kContinue | Instruction::kBranch; 2433 case kMirOpFusedCmpLong: 2434 return Instruction::kContinue | Instruction::kBranch; 2435 case kMirOpNop: 2436 return Instruction::kContinue; 2437 case kMirOpNullCheck: 2438 return Instruction::kContinue | Instruction::kThrow; 2439 case kMirOpRangeCheck: 2440 return Instruction::kContinue | Instruction::kThrow; 2441 case kMirOpDivZeroCheck: 2442 return Instruction::kContinue | Instruction::kThrow; 2443 case kMirOpCheck: 2444 return Instruction::kContinue | Instruction::kThrow; 2445 case kMirOpCheckPart2: 2446 return Instruction::kContinue; 2447 case kMirOpSelect: 2448 return Instruction::kContinue; 2449 case kMirOpConstVector: 2450 return Instruction::kContinue; 2451 case kMirOpMoveVector: 2452 return Instruction::kContinue; 2453 case kMirOpPackedMultiply: 2454 return Instruction::kContinue; 2455 case kMirOpPackedAddition: 2456 return Instruction::kContinue; 2457 case kMirOpPackedSubtract: 2458 return Instruction::kContinue; 2459 case kMirOpPackedShiftLeft: 2460 return Instruction::kContinue; 2461 case kMirOpPackedSignedShiftRight: 2462 return Instruction::kContinue; 2463 case kMirOpPackedUnsignedShiftRight: 2464 return Instruction::kContinue; 2465 case kMirOpPackedAnd: 2466 return Instruction::kContinue; 2467 case kMirOpPackedOr: 2468 return Instruction::kContinue; 2469 case kMirOpPackedXor: 2470 return Instruction::kContinue; 2471 case kMirOpPackedAddReduce: 2472 return Instruction::kContinue; 2473 case kMirOpPackedReduce: 2474 return Instruction::kContinue; 2475 case kMirOpPackedSet: 2476 return Instruction::kContinue; 2477 case kMirOpReserveVectorRegisters: 2478 return Instruction::kContinue; 2479 case kMirOpReturnVectorRegisters: 2480 return Instruction::kContinue; 2481 case kMirOpMemBarrier: 2482 return Instruction::kContinue; 2483 case kMirOpPackedArrayGet: 2484 return Instruction::kContinue | Instruction::kThrow; 2485 case kMirOpPackedArrayPut: 2486 return Instruction::kContinue | Instruction::kThrow; 2487 case kMirOpMaddInt: 2488 case kMirOpMsubInt: 2489 case kMirOpMaddLong: 2490 case kMirOpMsubLong: 2491 return Instruction::kContinue; 2492 default: 2493 LOG(WARNING) << "ExtendedFlagsOf: Unhandled case: " << static_cast<int> (opcode); 2494 return 0; 2495 } 2496} 2497} // namespace art 2498