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