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