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