mir_graph.cc revision b1f1d642093418612c0a27ce4203b421bb6eb767
1311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 2311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Copyright (C) 2013 The Android Open Source Project 3311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 4311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 5311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * you may not use this file except in compliance with the License. 6311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * You may obtain a copy of the License at 7311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 8311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * http://www.apache.org/licenses/LICENSE-2.0 9311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 10311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Unless required by applicable law or agreed to in writing, software 11311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * distributed under the License is distributed on an "AS IS" BASIS, 12311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * See the License for the specific language governing permissions and 14311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * limitations under the License. 15311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 16311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 17f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray#include "mir_graph.h" 18f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray 19f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray#include <inttypes.h> 20f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray 216282dc12440a2072dc06a616160027ff21bd895eIan Rogers#include "base/stl_util.h" 22311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "compiler_internals.h" 23311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "dex_file-inl.h" 245816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_to_method_inliner_map.h" 255816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_method_inliner.h" 26f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray#include "leb128.h" 275816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 28311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeenamespace art { 29311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 30311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#define MAX_PATTERN_LEN 5 31311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 321fd3346740dfb7f47be9922312b68a4227fada96buzbeeconst char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { 331fd3346740dfb7f47be9922312b68a4227fada96buzbee "Phi", 341fd3346740dfb7f47be9922312b68a4227fada96buzbee "Copy", 351fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplFloat", 361fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgFloat", 371fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplDouble", 381fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgDouble", 391fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpLong", 401fd3346740dfb7f47be9922312b68a4227fada96buzbee "Nop", 411fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpNullCheck", 421fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpRangeCheck", 431fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpDivZeroCheck", 441fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check1", 451fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check2", 461fd3346740dfb7f47be9922312b68a4227fada96buzbee "Select", 471fd3346740dfb7f47be9922312b68a4227fada96buzbee}; 481fd3346740dfb7f47be9922312b68a4227fada96buzbee 49862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeMIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 501fd3346740dfb7f47be9922312b68a4227fada96buzbee : reg_location_(NULL), 511fd3346740dfb7f47be9922312b68a4227fada96buzbee cu_(cu), 52311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_base_vregs_(NULL), 53311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_subscripts_(NULL), 54311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee vreg_to_ssa_map_(NULL), 55311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_last_defs_(NULL), 56311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee is_constant_v_(NULL), 57311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee constant_values_(NULL), 58862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee use_counts_(arena, 256, kGrowableArrayMisc), 59862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee raw_use_counts_(arena, 256, kGrowableArrayMisc), 60311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_reachable_blocks_(0), 61862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_(NULL), 62862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_(NULL), 63862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dom_post_order_traversal_(NULL), 64311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_(NULL), 65311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_block_matrix_(NULL), 66311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_block_v_(NULL), 67311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_dalvik_register_v_(NULL), 68311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_ssa_register_v_(NULL), 69862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_(arena, 100, kGrowableArrayBlockList), 70311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee try_block_addr_(NULL), 71311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee entry_block_(NULL), 72311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee exit_block_(NULL), 73311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_blocks_(0), 74311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_(NULL), 75b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), 76311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_(kInvalidEntry), 77311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_(kInvalidEntry), 78311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_(0), 79311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_(NULL), 801fd3346740dfb7f47be9922312b68a4227fada96buzbee num_ssa_regs_(0), 811fd3346740dfb7f47be9922312b68a4227fada96buzbee method_sreg_(0), 82862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. 83862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee checkstats_(NULL), 84b48819db07f9a0992a72173380c24249d7fc648abuzbee arena_(arena), 85b48819db07f9a0992a72173380c24249d7fc648abuzbee backward_branches_(0), 86da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru forward_branches_(0), 87da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru compiler_temps_(arena, 6, kGrowableArrayMisc), 88da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru num_non_special_compiler_temps_(0), 89b1f1d642093418612c0a27ce4203b421bb6eb767buzbee max_available_non_special_compiler_temps_(0), 90b1f1d642093418612c0a27ce4203b421bb6eb767buzbee punt_to_interpreter_(false) { 91862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); 92da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru max_available_special_compiler_temps_ = std::abs(static_cast<int>(kVRegNonSpecialTempBaseReg)) 93da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru - std::abs(static_cast<int>(kVRegTempBaseReg)); 94311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 95311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 966282dc12440a2072dc06a616160027ff21bd895eIan RogersMIRGraph::~MIRGraph() { 976282dc12440a2072dc06a616160027ff21bd895eIan Rogers STLDeleteElements(&m_units_); 986282dc12440a2072dc06a616160027ff21bd895eIan Rogers} 996282dc12440a2072dc06a616160027ff21bd895eIan Rogers 100311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 101311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Parse an instruction, return the length of the instruction 102311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 1032ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromint MIRGraph::ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction) { 104311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const Instruction* instruction = Instruction::At(code_ptr); 105311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *decoded_instruction = DecodedInstruction(instruction); 106311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 107311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return instruction->SizeInCodeUnits(); 108311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 109311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 110311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 111311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Split an existing block from the specified code offset into two */ 1120d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, 1132ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { 1140d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_GT(code_offset, orig_block->start_offset); 115311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MIR* insn = orig_block->first_mir_insn; 1160d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee MIR* prev = NULL; 117311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (insn) { 118311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->offset == code_offset) break; 1190d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee prev = insn; 120311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn = insn->next; 121311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 122311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn == NULL) { 123311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Break split failed"; 124311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 125862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); 126862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bottom_block); 127311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 128311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->start_offset = code_offset; 129311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->first_mir_insn = insn; 130311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->last_mir_insn = orig_block->last_mir_insn; 131311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 132311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* If this block was terminated by a return, the flag needs to go with the bottom block */ 133311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->terminated_by_return = orig_block->terminated_by_return; 134311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->terminated_by_return = false; 135311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 136311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the taken path */ 137311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->taken = orig_block->taken; 1380d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->taken != NullBasicBlockId) { 1390d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->taken = NullBasicBlockId; 1400d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); 1410d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Delete(orig_block->id); 1420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Insert(bottom_block->id); 143311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 144311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 145311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the fallthrough path */ 146311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->fall_through = orig_block->fall_through; 1470d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->fall_through = bottom_block->id; 1480d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->predecessors->Insert(orig_block->id); 1490d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->fall_through != NullBasicBlockId) { 1500d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); 1510d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Delete(orig_block->id); 1520d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Insert(bottom_block->id); 153311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 154311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 155311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the successor list */ 1560d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (orig_block->successor_block_list_type != kNotUsed) { 1570d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_block_list_type = orig_block->successor_block_list_type; 1580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_blocks = orig_block->successor_blocks; 1590d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->successor_block_list_type = kNotUsed; 1600d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->successor_blocks = NULL; 1610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); 162311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 163862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 164311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 1650d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock *bb = GetBasicBlock(successor_block_info->block); 1660d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors->Delete(orig_block->id); 1670d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors->Insert(bottom_block->id); 168311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 169311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 170311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 1710d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->last_mir_insn = prev; 1720d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee prev->next = NULL; 173311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 174311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 175311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Update the immediate predecessor block pointer so that outgoing edges 176311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * can be applied to the proper block. 177311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 178311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (immed_pred_block_p) { 179311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(*immed_pred_block_p, orig_block); 180311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *immed_pred_block_p = bottom_block; 181311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 182b48819db07f9a0992a72173380c24249d7fc648abuzbee 183b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate dex instructions in the bottom block with the new container. 1844376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != nullptr); 1854376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != orig_block->first_mir_insn); 1864376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn == bottom_block->first_mir_insn); 1874376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(insn->offset, bottom_block->start_offset); 1884376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || 1894376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko !IsPseudoMirOp(insn->dalvikInsn.opcode)); 1904376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); 1914376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko MIR* p = insn; 1924376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 1934376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko while (p != bottom_block->last_mir_insn) { 1944376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko p = p->next; 1954376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(p != nullptr); 196b48819db07f9a0992a72173380c24249d7fc648abuzbee int opcode = p->dalvikInsn.opcode; 197b48819db07f9a0992a72173380c24249d7fc648abuzbee /* 198b48819db07f9a0992a72173380c24249d7fc648abuzbee * Some messiness here to ensure that we only enter real opcodes and only the 199b48819db07f9a0992a72173380c24249d7fc648abuzbee * first half of a potentially throwing instruction that has been split into 2004376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * CHECK and work portions. Since the 2nd half of a split operation is always 2014376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * the first in a BasicBlock, we can't hit it here. 202b48819db07f9a0992a72173380c24249d7fc648abuzbee */ 2034376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko if ((opcode == kMirOpCheck) || !IsPseudoMirOp(opcode)) { 2044376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); 205b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 206b48819db07f9a0992a72173380c24249d7fc648abuzbee } 207b48819db07f9a0992a72173380c24249d7fc648abuzbee } 208b48819db07f9a0992a72173380c24249d7fc648abuzbee 209311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bottom_block; 210311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 211311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 212311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 213311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Given a code offset, find out the block that starts with it. If the offset 214311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is in the middle of an existing block, split it into two. If immed_pred_block_p 215311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is not non-null and is the block being split, update *immed_pred_block_p to 216311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * point to the bottom block so that outgoing edges can be set up properly 217311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (by the caller) 218311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Utilizes a map for fast lookup of the typical cases. 219311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 2200d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, 2212ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock** immed_pred_block_p) { 222bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee if (code_offset >= cu_->code_item->insns_size_in_code_units_) { 223311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return NULL; 224311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 225b48819db07f9a0992a72173380c24249d7fc648abuzbee 226b48819db07f9a0992a72173380c24249d7fc648abuzbee int block_id = dex_pc_to_block_map_.Get(code_offset); 227b48819db07f9a0992a72173380c24249d7fc648abuzbee BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); 228b48819db07f9a0992a72173380c24249d7fc648abuzbee 229b48819db07f9a0992a72173380c24249d7fc648abuzbee if ((bb != NULL) && (bb->start_offset == code_offset)) { 230b48819db07f9a0992a72173380c24249d7fc648abuzbee // Does this containing block start with the desired instruction? 231bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee return bb; 232bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee } 233311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 234b48819db07f9a0992a72173380c24249d7fc648abuzbee // No direct hit. 235b48819db07f9a0992a72173380c24249d7fc648abuzbee if (!create) { 236b48819db07f9a0992a72173380c24249d7fc648abuzbee return NULL; 237b48819db07f9a0992a72173380c24249d7fc648abuzbee } 238b48819db07f9a0992a72173380c24249d7fc648abuzbee 239b48819db07f9a0992a72173380c24249d7fc648abuzbee if (bb != NULL) { 240b48819db07f9a0992a72173380c24249d7fc648abuzbee // The target exists somewhere in an existing block. 241b48819db07f9a0992a72173380c24249d7fc648abuzbee return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : NULL); 242311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 243311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 244b48819db07f9a0992a72173380c24249d7fc648abuzbee // Create a new block. 245862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = NewMemBB(kDalvikByteCode, num_blocks_++); 246862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bb); 247311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset = code_offset; 248b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(bb->start_offset, bb->id); 249311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bb; 250311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 251311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 252b48819db07f9a0992a72173380c24249d7fc648abuzbee 253311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Identify code range in try blocks and set up the empty catch blocks */ 2542ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ProcessTryCatchBlocks() { 255311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int tries_size = current_code_item_->tries_size_; 2560d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset offset; 257311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 258311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (tries_size == 0) { 259311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 260311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 261311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 262311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < tries_size; i++) { 263311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const DexFile::TryItem* pTry = 264311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DexFile::GetTryItems(*current_code_item_, i); 2650d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset start_offset = pTry->start_addr_; 2660d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset end_offset = start_offset + pTry->insn_count_; 267311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (offset = start_offset; offset < end_offset; offset++) { 268862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(offset); 269311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 270311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 271311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 272311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Iterate over each of the handlers to enqueue the empty Catch blocks 273311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); 274311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 275311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (uint32_t idx = 0; idx < handlers_size; idx++) { 276311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(handlers_ptr); 277311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (; iterator.HasNext(); iterator.Next()) { 278311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t address = iterator.GetHandlerAddress(); 279311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(address, false /* split */, true /*create*/, 280311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 281311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 282311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee handlers_ptr = iterator.EndDataPointer(); 283311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 284311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 285311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 286311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kBranch flag */ 2870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 2880d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, const uint16_t* code_ptr, 2892ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_end) { 2900d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset target = cur_offset; 291311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee switch (insn->dalvikInsn.opcode) { 292311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO: 293311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_16: 294311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_32: 295311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vA; 296311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 297311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQ: 298311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NE: 299311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LT: 300311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GE: 301311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GT: 302311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LE: 303311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 304311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vC; 305311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 306311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQZ: 307311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NEZ: 308311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LTZ: 309311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GEZ: 310311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GTZ: 311311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LEZ: 312311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 313311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vB; 314311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 315311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee default: 316311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; 317311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 318b48819db07f9a0992a72173380c24249d7fc648abuzbee CountBranch(target); 319311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *taken_block = FindBlock(target, /* split */ true, /* create */ true, 320311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ &cur_block); 3210d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = taken_block->id; 3220d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee taken_block->predecessors->Insert(cur_block->id); 323311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 324311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Always terminate the current block for conditional branches */ 325311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kContinue) { 326311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *fallthrough_block = FindBlock(cur_offset + width, 327311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 328311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * If the method is processed 329311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * in sequential order from the 330311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * beginning, we don't need to 331311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * specify split for continue 332311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * blocks. However, this 333311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * routine can be called by 334311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * compileLoop, which starts 335311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * parsing the method from an 336311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * arbitrary address in the 337311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * method body. 338311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 339311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 340311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ 341311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 342311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ 343311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee &cur_block); 3440d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 3450d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 346311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (code_ptr < code_end) { 3472724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 348311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 349311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 350311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 351311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 352311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 353311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kSwitch flag */ 35417189ac098b2f156713db1821b49db7b2f018bbebuzbeeBasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 35517189ac098b2f156713db1821b49db7b2f018bbebuzbee int width, int flags) { 356311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* switch_data = 357311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); 358311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int size; 359311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* keyTable; 360311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* target_table; 361311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int i; 362311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int first_key; 363311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 364311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 365311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Packed switch data format: 366311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0100 magic value 367311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table 368311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int first_key first (and lowest) switch case value 369311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 370311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 371311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (4+size*2) 16-bit code units. 372311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 373311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { 374311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 375311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kPackedSwitchSignature)); 376311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 377311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = switch_data[2] | (switch_data[3] << 16); 378311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[4]); 379311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = NULL; // Make the compiler happy 380311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 381311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Sparse switch data format: 382311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0200 magic value 383311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table; > 0 384311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int keys[size] keys, sorted low-to-high; 32-bit aligned 385311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 386311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 387311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (2+size*4) 16-bit code units. 388311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 389311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 390311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 391311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kSparseSwitchSignature)); 392311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 393311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = reinterpret_cast<const int*>(&switch_data[2]); 394311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); 395311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = 0; // To make the compiler happy 396311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 397311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 3980d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 399311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 4000d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 401311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 4020d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_block_list_type = 4030d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; 4040d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks = 405df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); 406311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 407311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (i = 0; i < size; i++) { 408311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *case_block = FindBlock(cur_offset + target_table[i], /* split */ true, 409311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ true, /* immed_pred_block_p */ &cur_block); 410311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = 411f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), 412f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocSuccessor)); 4130d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = case_block->id; 414311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = 415311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 416311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key + i : keyTable[i]; 4170d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 4180d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee case_block->predecessors->Insert(cur_block->id); 419311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 420311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 421311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Fall-through case */ 422df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, 423df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom /* create */ true, /* immed_pred_block_p */ NULL); 4240d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 4250d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 42617189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 427311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 428311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 429311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kThrow flag */ 4300d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 4310d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, ArenaBitVector* try_block_addr, 4322ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_ptr, const uint16_t* code_end) { 433862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool in_try_block = try_block_addr->IsBitSet(cur_offset); 43417189ac098b2f156713db1821b49db7b2f018bbebuzbee bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); 43517189ac098b2f156713db1821b49db7b2f018bbebuzbee bool build_all_edges = 43617189ac098b2f156713db1821b49db7b2f018bbebuzbee (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; 437311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 438311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* In try block */ 439311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (in_try_block) { 440311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(*current_code_item_, cur_offset); 441311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 443311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 444311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 4450d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 446311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 447311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4480d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_block_list_type = kCatch; 4490d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks = 450862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, 2, kGrowableArraySuccessorBlocks); 451311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 45202c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom for (; iterator.HasNext(); iterator.Next()) { 453311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, 454311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false /* creat */, NULL /* immed_pred_block_p */); 455311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catch_block->catch_entry = true; 456311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (kIsDebugBuild) { 457311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catches_.insert(catch_block->start_offset); 458311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 459311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 460f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier (arena_->Alloc(sizeof(SuccessorBlockInfo), ArenaAllocator::kAllocSuccessor)); 4610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = catch_block->id; 462311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = iterator.GetHandlerTypeIndex(); 4630d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 4640d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee catch_block->predecessors->Insert(cur_block->id); 465311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 46617189ac098b2f156713db1821b49db7b2f018bbebuzbee } else if (build_all_edges) { 467862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *eh_block = NewMemBB(kExceptionHandling, num_blocks_++); 4680d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = eh_block->id; 469862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(eh_block); 470311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee eh_block->start_offset = cur_offset; 4710d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee eh_block->predecessors->Insert(cur_block->id); 472311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 473311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 47417189ac098b2f156713db1821b49db7b2f018bbebuzbee if (is_throw) { 475311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->explicit_throw = true; 4762724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (code_ptr < code_end) { 477311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Force creation of new block following THROW via side-effect 478311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 479311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 480311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 481311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (!in_try_block) { 482311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Don't split a THROW that can't rethrow - we're done. 483311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 484311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 485311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 486311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 48717189ac098b2f156713db1821b49db7b2f018bbebuzbee if (!build_all_edges) { 48817189ac098b2f156713db1821b49db7b2f018bbebuzbee /* 48917189ac098b2f156713db1821b49db7b2f018bbebuzbee * Even though there is an exception edge here, control cannot return to this 49017189ac098b2f156713db1821b49db7b2f018bbebuzbee * method. Thus, for the purposes of dataflow analysis and optimization, we can 49117189ac098b2f156713db1821b49db7b2f018bbebuzbee * ignore the edge. Doing this reduces compile time, and increases the scope 49217189ac098b2f156713db1821b49db7b2f018bbebuzbee * of the basic-block level optimization pass. 49317189ac098b2f156713db1821b49db7b2f018bbebuzbee */ 49417189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 49517189ac098b2f156713db1821b49db7b2f018bbebuzbee } 49617189ac098b2f156713db1821b49db7b2f018bbebuzbee 497311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 498311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Split the potentially-throwing instruction into two parts. 499311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The first half will be a pseudo-op that captures the exception 500311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * edges and terminates the basic block. It always falls through. 501311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Then, create a new basic block that begins with the throwing instruction 502311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (minus exceptions). Note: this new basic block must NOT be entered into 503311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the block_map. If the potentially-throwing instruction is the target of a 504311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * future branch, we need to find the check psuedo half. The new 505311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * basic block containing the work portion of the instruction should 506311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * only be entered via fallthrough from the block containing the 507311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * pseudo exception edge MIR. Note also that this new block is 508311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * not automatically terminated after the work portion, and may 509311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * contain following instructions. 510b48819db07f9a0992a72173380c24249d7fc648abuzbee * 511b48819db07f9a0992a72173380c24249d7fc648abuzbee * Note also that the dex_pc_to_block_map_ entry for the potentially 512b48819db07f9a0992a72173380c24249d7fc648abuzbee * throwing instruction will refer to the original basic block. 513311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 514862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *new_block = NewMemBB(kDalvikByteCode, num_blocks_++); 515862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(new_block); 516311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee new_block->start_offset = insn->offset; 5170d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = new_block->id; 5180d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee new_block->predecessors->Insert(cur_block->id); 519f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier MIR* new_insn = static_cast<MIR*>(arena_->Alloc(sizeof(MIR), ArenaAllocator::kAllocMIR)); 520311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *new_insn = *insn; 521311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->dalvikInsn.opcode = 522311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<Instruction::Code>(kMirOpCheck); 523311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Associate the two halves 524311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->meta.throw_insn = new_insn; 525311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee AppendMIR(new_block, new_insn); 526311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return new_block; 527311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 528311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 529311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ 530311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 5318b2c0b9abc3f520495f4387ea040132ba85cae69Ian Rogers InvokeType invoke_type, uint16_t class_def_idx, 5322ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { 533311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_ = code_item; 534311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee method_stack_.push_back(std::make_pair(current_method_, current_offset_)); 535311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_ = m_units_.size(); 536311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ = 0; 537311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: will need to snapshot stack image and use that as the mir context identification. 538311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), 5392730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko dex_file, current_code_item_, class_def_idx, method_idx, access_flags, 5402730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); 541311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_ptr = current_code_item_->insns_; 542311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_end = 543311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; 544311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 545311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: need to rework expansion of block list & try_block_addr when inlining activated. 546b48819db07f9a0992a72173380c24249d7fc648abuzbee // TUNING: use better estimate of basic blocks for following resize. 547862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); 548b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_); 549bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee 550311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: replace with explicit resize routine. Using automatic extension side effect for now. 551862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); 552862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); 553311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 554311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // If this is the first method, set up default entry and exit blocks. 555311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (current_method_ == 0) { 556311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(entry_block_ == NULL); 557311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(exit_block_ == NULL); 5584274889d48ef82369bf2c1ca70d84689b4f9e93aBrian Carlstrom DCHECK_EQ(num_blocks_, 0); 5590d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Use id 0 to represent a null block. 5600d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); 5610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(null_block->id, NullBasicBlockId); 5620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee null_block->hidden = true; 5630d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee block_list_.Insert(null_block); 564862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); 565862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(entry_block_); 5660d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_ = NewMemBB(kExitBlock, num_blocks_++); 567862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(exit_block_); 568311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. 569311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->dex_file = &dex_file; 570311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->class_def_idx = class_def_idx; 571311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->method_idx = method_idx; 572311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->access_flags = access_flags; 573311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->invoke_type = invoke_type; 574311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); 575311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_ins = current_code_item_->ins_size_; 576311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_regs = current_code_item_->registers_size_ - cu_->num_ins; 577311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_outs = current_code_item_->outs_size_; 578311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_dalvik_registers = current_code_item_->registers_size_; 579311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->insns = current_code_item_->insns_; 580311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->code_item = current_code_item_; 581311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 582311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; 583311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 584311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Will need to manage storage for ins & outs, push prevous state and update 585311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * insert point. 586311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 587311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 588311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 589311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Current block to record parsed instructions */ 590862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); 5910d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(current_offset_, 0U); 592311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->start_offset = current_offset_; 593862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(cur_block); 5940d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, insert at the insert point rather than entry block. 5950d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee entry_block_->fall_through = cur_block->id; 5960d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->predecessors->Insert(entry_block_->id); 597311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 598311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Identify code range in try blocks and set up the empty catch blocks */ 599311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ProcessTryCatchBlocks(); 600311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 601311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Parse all instructions and put them into containing basic blocks */ 602311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (code_ptr < code_end) { 603f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier MIR *insn = static_cast<MIR *>(arena_->Alloc(sizeof(MIR), ArenaAllocator::kAllocMIR)); 604311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->offset = current_offset_; 605311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->m_unit_index = current_method_; 606311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int width = ParseInsn(code_ptr, &insn->dalvikInsn); 607311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->width = width; 608311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee Instruction::Code opcode = insn->dalvikInsn.opcode; 609311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_ != NULL) { 610311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_[static_cast<int>(opcode)]++; 611311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 612311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 613311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int flags = Instruction::FlagsOf(insn->dalvikInsn.opcode); 614b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int verify_flags = Instruction::VerifyFlagsOf(insn->dalvikInsn.opcode); 615311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6161da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee uint64_t df_flags = oat_data_flow_attributes_[insn->dalvikInsn.opcode]; 617311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 618311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (df_flags & DF_HAS_DEFS) { 619311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; 620311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 621311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6221da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee if (df_flags & DF_LVN) { 6231da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee cur_block->use_lvn = true; // Run local value numbering on this basic block. 6241da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee } 6251da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee 6262724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Check for inline data block signatures 6272724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (opcode == Instruction::NOP) { 6282724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. 6292724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { 6302724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. 6312724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee uint16_t following_raw_instruction = code_ptr[1]; 6322724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || 6332724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kPackedSwitchSignature) || 6342724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kArrayDataSignature)) { 6352724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); 6362724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6372724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6382724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (width == 1) { 6392724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // It is a simple nop - treat normally. 6402724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee AppendMIR(cur_block, insn); 6412724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 6420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId); 6430d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->taken == NullBasicBlockId); 6442724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Unreachable instruction, mark for no continuation. 6452724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee flags &= ~Instruction::kContinue; 6462724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6472724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 6482724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee AppendMIR(cur_block, insn); 6492724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6502724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 651b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate the starting dex_pc for this opcode with its containing basic block. 652b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(insn->offset, cur_block->id); 653b48819db07f9a0992a72173380c24249d7fc648abuzbee 6542724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee code_ptr += width; 6552724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 656311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kBranch) { 657311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanBranch(cur_block, insn, current_offset_, 658311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee width, flags, code_ptr, code_end); 659311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kReturn) { 660311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->terminated_by_return = true; 6610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = exit_block_->id; 6620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_->predecessors->Insert(cur_block->id); 663311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 664311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Terminate the current block if there are instructions 665311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * afterwards. 666311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 667311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (code_ptr < code_end) { 668311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 669311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Create a fallthrough block for real instructions 670311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (incl. NOP). 671311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 6722724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(current_offset_ + width, /* split */ false, /* create */ true, 6732724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee /* immed_pred_block_p */ NULL); 674311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 675311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kThrow) { 676311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, 677311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee code_ptr, code_end); 678311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kSwitch) { 67917189ac098b2f156713db1821b49db7b2f018bbebuzbee cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); 680311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 681b1f1d642093418612c0a27ce4203b421bb6eb767buzbee if (verify_flags & Instruction::kVerifyVarArgRange) { 682b1f1d642093418612c0a27ce4203b421bb6eb767buzbee /* 683b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * The Quick backend's runtime model includes a gap between a method's 684b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * argument ("in") vregs and the rest of its vregs. Handling a range instruction 685b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * which spans the gap is somewhat complicated, and should not happen 686b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * in normal usage of dx. Punt to the interpreter. 687b1f1d642093418612c0a27ce4203b421bb6eb767buzbee */ 688b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int first_reg_in_range = insn->dalvikInsn.vC; 689b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int last_reg_in_range = first_reg_in_range + insn->dalvikInsn.vA - 1; 690b1f1d642093418612c0a27ce4203b421bb6eb767buzbee if (IsInVReg(first_reg_in_range) != IsInVReg(last_reg_in_range)) { 691b1f1d642093418612c0a27ce4203b421bb6eb767buzbee punt_to_interpreter_ = true; 692b1f1d642093418612c0a27ce4203b421bb6eb767buzbee } 693b1f1d642093418612c0a27ce4203b421bb6eb767buzbee } 694311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ += width; 695311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *next_block = FindBlock(current_offset_, /* split */ false, /* create */ 696311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false, /* immed_pred_block_p */ NULL); 697311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (next_block) { 698311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 699311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The next instruction could be the target of a previously parsed 700311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * forward branch so a block is already created. If the current 701311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * instruction is not an unconditional branch, connect them through 702311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the fall-through link. 703311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 7040d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId || 7050d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == next_block || 7060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == exit_block_); 707311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7080d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { 7090d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = next_block->id; 7100d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee next_block->predecessors->Insert(cur_block->id); 711311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 712311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = next_block; 713311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 714311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 7155816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 716311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 717311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DumpCFG("/sdcard/1_post_parse_cfg/", true); 718311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 719311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 720311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 7211fd3346740dfb7f47be9922312b68a4227fada96buzbee DumpMIRGraph(); 722311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 723311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 724311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7252ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ShowOpcodeStats() { 726311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(opcode_count_ != NULL); 727311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "Opcode Count"; 728311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < kNumPackedOpcodes; i++) { 729311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_[i] != 0) { 730311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) 731311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee << " " << opcode_count_[i]; 732311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 733311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 734311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 735311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 736311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee// TODO: use a configurable base prefix, and adjust callers to supply pass name. 737311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Dump the CFG into a DOT graph */ 738d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beylervoid MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { 739311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FILE* file; 740311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); 741311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ReplaceSpecialChars(fname); 742d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler fname = StringPrintf("%s%s%x%s.dot", dir_prefix, fname.c_str(), 743d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, 744d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler suffix == nullptr ? "" : suffix); 745311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee file = fopen(fname.c_str(), "w"); 746311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (file == NULL) { 747311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 748311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 749311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "digraph G {\n"); 750311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 751311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " rankdir=TB\n"); 752311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 753311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; 754311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int idx; 755311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 756311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (idx = 0; idx < num_blocks; idx++) { 757862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int block_idx = all_blocks ? idx : dfs_order_->Get(idx); 758311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *bb = GetBasicBlock(block_idx); 759311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb == NULL) break; 760311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kDead) continue; 761311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kEntryBlock) { 762311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); 763311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExitBlock) { 764311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); 765311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kDalvikByteCode) { 766311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", 767311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id); 768311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const MIR *mir; 769311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 770311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->first_mir_insn ? " | " : " "); 771311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (mir = bb->first_mir_insn; mir; mir = mir->next) { 772311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int opcode = mir->dalvikInsn.opcode; 773311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {%04x %s %s %s\\l}%s\\\n", mir->offset, 7741fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->ssa_rep ? GetDalvikDisassembly(mir) : 775311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (opcode < kMirOpFirst) ? Instruction::Name(mir->dalvikInsn.opcode) : 7761fd3346740dfb7f47be9922312b68a4227fada96buzbee extended_mir_op_names_[opcode - kMirOpFirst], 777311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", 778311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", 779311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee mir->next ? " | " : " "); 780311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 781311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 782311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExceptionHandling) { 783311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name[BLOCK_NAME_LEN]; 784311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 785311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name); 786311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s [shape=invhouse];\n", block_name); 787311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 788311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 789311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 790311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7910d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 792311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 7930d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->taken), block_name2); 794311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n [style=dotted]\n", 795311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name2); 796311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 7970d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 798311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 7990d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->fall_through), block_name2); 800311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); 801311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 802311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8030d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type != kNotUsed) { 804311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", 805311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id, 8060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); 8070d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 808862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 809311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 810311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int succ_id = 0; 811311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 812311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 813311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8140d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock *dest_block = GetBasicBlock(successor_block_info->block); 815862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *next_successor_block_info = iterator.Next(); 816311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 817311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 818311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id++, 819311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key, 820311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee dest_block->start_offset, 821311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (next_successor_block_info != NULL) ? " | " : " "); 822311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 823311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info = next_successor_block_info; 824311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 825311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 826311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 827311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 828311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", 829311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, bb->start_offset, bb->id); 830311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8310d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type == kPackedSwitch || 8320d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->successor_block_list_type == kSparseSwitch) { 8330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); 834311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 835311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id = 0; 836311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 837862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iter.Next(); 838311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 839311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8400d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 841311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 842311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(dest_block, block_name2); 843311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, 844311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->id, succ_id++, block_name2); 845311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 846311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 847311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 848311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "\n"); 849311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 850311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 851311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Display the dominator tree */ 852311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 853311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 854311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name1); 855311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->i_dom) { 8560d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->i_dom), block_name2); 857311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); 858311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 859311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 860311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 861311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "}\n"); 862311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fclose(file); 863311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 864311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8651fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the end of a basic block */ 8662ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::AppendMIR(BasicBlock* bb, MIR* mir) { 8671fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->first_mir_insn == NULL) { 8681fd3346740dfb7f47be9922312b68a4227fada96buzbee DCHECK(bb->last_mir_insn == NULL); 8691fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = bb->first_mir_insn = mir; 8700d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee mir->next = NULL; 8711fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 8721fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn->next = mir; 8731fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->next = NULL; 8741fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = mir; 8751fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8761fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8771fd3346740dfb7f47be9922312b68a4227fada96buzbee 8781fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the head of a basic block */ 8792ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::PrependMIR(BasicBlock* bb, MIR* mir) { 8801fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->first_mir_insn == NULL) { 8811fd3346740dfb7f47be9922312b68a4227fada96buzbee DCHECK(bb->last_mir_insn == NULL); 8821fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = bb->first_mir_insn = mir; 8830d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee mir->next = NULL; 8841fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 8851fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->next = bb->first_mir_insn; 8861fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->first_mir_insn = mir; 8871fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8881fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8891fd3346740dfb7f47be9922312b68a4227fada96buzbee 8901fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert a MIR instruction after the specified MIR */ 8912ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir) { 8921fd3346740dfb7f47be9922312b68a4227fada96buzbee new_mir->next = current_mir->next; 8931fd3346740dfb7f47be9922312b68a4227fada96buzbee current_mir->next = new_mir; 8941fd3346740dfb7f47be9922312b68a4227fada96buzbee 8950d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->last_mir_insn == current_mir) { 8961fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Is the last MIR in the block */ 8971fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = new_mir; 8981fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8991fd3346740dfb7f47be9922312b68a4227fada96buzbee} 9001fd3346740dfb7f47be9922312b68a4227fada96buzbee 9013bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A LupusoruMIR* MIRGraph::GetNextUnconditionalMir(BasicBlock* bb, MIR* current) { 9023bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru MIR* next_mir = nullptr; 9033bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9043bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru if (current != nullptr) { 9053bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru next_mir = current->next; 9063bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 9073bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9083bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru if (next_mir == nullptr) { 9093bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru // Only look for next MIR that follows unconditionally. 9103bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru if ((bb->taken == NullBasicBlockId) && (bb->fall_through != NullBasicBlockId)) { 9113bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru next_mir = GetBasicBlock(bb->fall_through)->first_mir_insn; 9123bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 9133bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 9143bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9153bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru return next_mir; 9163bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru} 9173bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9182ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromchar* MIRGraph::GetDalvikDisassembly(const MIR* mir) { 9191fd3346740dfb7f47be9922312b68a4227fada96buzbee DecodedInstruction insn = mir->dalvikInsn; 9201fd3346740dfb7f47be9922312b68a4227fada96buzbee std::string str; 9211fd3346740dfb7f47be9922312b68a4227fada96buzbee int flags = 0; 9221fd3346740dfb7f47be9922312b68a4227fada96buzbee int opcode = insn.opcode; 9231fd3346740dfb7f47be9922312b68a4227fada96buzbee char* ret; 9241fd3346740dfb7f47be9922312b68a4227fada96buzbee bool nop = false; 9251fd3346740dfb7f47be9922312b68a4227fada96buzbee SSARepresentation* ssa_rep = mir->ssa_rep; 9261fd3346740dfb7f47be9922312b68a4227fada96buzbee Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format 9271fd3346740dfb7f47be9922312b68a4227fada96buzbee int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; 9281fd3346740dfb7f47be9922312b68a4227fada96buzbee int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; 9291fd3346740dfb7f47be9922312b68a4227fada96buzbee 9301fd3346740dfb7f47be9922312b68a4227fada96buzbee // Handle special cases. 9311fd3346740dfb7f47be9922312b68a4227fada96buzbee if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { 9321fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 9331fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(": "); 9341fd3346740dfb7f47be9922312b68a4227fada96buzbee // Recover the original Dex instruction 9351fd3346740dfb7f47be9922312b68a4227fada96buzbee insn = mir->meta.throw_insn->dalvikInsn; 9361fd3346740dfb7f47be9922312b68a4227fada96buzbee ssa_rep = mir->meta.throw_insn->ssa_rep; 9371fd3346740dfb7f47be9922312b68a4227fada96buzbee defs = ssa_rep->num_defs; 9381fd3346740dfb7f47be9922312b68a4227fada96buzbee uses = ssa_rep->num_uses; 9391fd3346740dfb7f47be9922312b68a4227fada96buzbee opcode = insn.opcode; 9401fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if (opcode == kMirOpNop) { 9411fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("["); 9420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Recover original opcode. 9430d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); 9440d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee opcode = insn.opcode; 9451fd3346740dfb7f47be9922312b68a4227fada96buzbee nop = true; 9461fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9471fd3346740dfb7f47be9922312b68a4227fada96buzbee 9481fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode >= kMirOpFirst) { 9491fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 9501fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 9511fd3346740dfb7f47be9922312b68a4227fada96buzbee dalvik_format = Instruction::FormatOf(insn.opcode); 9521fd3346740dfb7f47be9922312b68a4227fada96buzbee flags = Instruction::FlagsOf(insn.opcode); 9531fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(Instruction::Name(insn.opcode)); 9541fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9551fd3346740dfb7f47be9922312b68a4227fada96buzbee 9561fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode == kMirOpPhi) { 9570d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlockId* incoming = mir->meta.phi_incoming; 9581fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s = (%s", 9591fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), 9601fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); 961b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom str.append(StringPrintf(":%d", incoming[0])); 9621fd3346740dfb7f47be9922312b68a4227fada96buzbee int i; 9631fd3346740dfb7f47be9922312b68a4227fada96buzbee for (i = 1; i < uses; i++) { 9641fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", %s:%d", 9651fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), 9661fd3346740dfb7f47be9922312b68a4227fada96buzbee incoming[i])); 9671fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9681fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(")"); 9691fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if ((flags & Instruction::kBranch) != 0) { 9701fd3346740dfb7f47be9922312b68a4227fada96buzbee // For branches, decode the instructions to print out the branch targets. 9711fd3346740dfb7f47be9922312b68a4227fada96buzbee int offset = 0; 9721fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 9731fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21t: 9741fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 9751fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vB; 9761fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9771fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22t: 9781fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), 9791fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); 9801fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vC; 9811fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9821fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k10t: 9831fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k20t: 9841fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k30t: 9851fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vA; 9861fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9871fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 9881fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; 9891fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9901fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset, 9911fd3346740dfb7f47be9922312b68a4227fada96buzbee offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); 9921fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 9931fd3346740dfb7f47be9922312b68a4227fada96buzbee // For invokes-style formats, treat wide regs as a pair of singles 9941fd3346740dfb7f47be9922312b68a4227fada96buzbee bool show_singles = ((dalvik_format == Instruction::k35c) || 9951fd3346740dfb7f47be9922312b68a4227fada96buzbee (dalvik_format == Instruction::k3rc)); 9961fd3346740dfb7f47be9922312b68a4227fada96buzbee if (defs != 0) { 9971fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s", GetSSANameWithConst(ssa_rep->defs[0], false).c_str())); 9981fd3346740dfb7f47be9922312b68a4227fada96buzbee if (uses != 0) { 9991fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(", "); 10001fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10011fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10021fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < uses; i++) { 10031fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append( 10041fd3346740dfb7f47be9922312b68a4227fada96buzbee StringPrintf(" %s", GetSSANameWithConst(ssa_rep->uses[i], show_singles).c_str())); 10051fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { 10061fd3346740dfb7f47be9922312b68a4227fada96buzbee // For the listing, skip the high sreg. 10071fd3346740dfb7f47be9922312b68a4227fada96buzbee i++; 10081fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10091fd3346740dfb7f47be9922312b68a4227fada96buzbee if (i != (uses -1)) { 10101fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(","); 10111fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10121fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10131fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 10147934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k11n: // Add one immediate from vB 10151fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21s: 10161fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31i: 10171fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21h: 10181fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vB)); 10191fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10207934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k51l: // Add one wide immediate 102123b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); 10221fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10237934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k21c: // One register, one string/type/method index 10241fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31c: 10251fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vB)); 10261fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10277934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k22c: // Two registers, one string/type/method index 10281fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vC)); 10291fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10307934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k22s: // Add one immediate from vC 10311fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22b: 10321fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vC)); 10331fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 103402c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom default: { 103502c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom // Nothing left to print 10361fd3346740dfb7f47be9922312b68a4227fada96buzbee } 103702c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom } 10381fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10391fd3346740dfb7f47be9922312b68a4227fada96buzbee if (nop) { 10401fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("]--optimized away"); 10411fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10421fd3346740dfb7f47be9922312b68a4227fada96buzbee int length = str.length() + 1; 1043f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ret = static_cast<char*>(arena_->Alloc(length, ArenaAllocator::kAllocDFInfo)); 10441fd3346740dfb7f47be9922312b68a4227fada96buzbee strncpy(ret, str.c_str(), length); 10451fd3346740dfb7f47be9922312b68a4227fada96buzbee return ret; 10461fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10471fd3346740dfb7f47be9922312b68a4227fada96buzbee 10481fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Turn method name into a legal Linux file name */ 10492ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ReplaceSpecialChars(std::string& str) { 10509b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static const struct { const char before; const char after; } match[] = { 10519b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, 10529b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} 10539b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom }; 10541fd3346740dfb7f47be9922312b68a4227fada96buzbee for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { 10551fd3346740dfb7f47be9922312b68a4227fada96buzbee std::replace(str.begin(), str.end(), match[i].before, match[i].after); 10561fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10571fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10581fd3346740dfb7f47be9922312b68a4227fada96buzbee 10592ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSAName(int ssa_reg) { 106039ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to 106139ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // the arena. We should be smarter and just place straight into the arena, or compute the 106239ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // value more lazily. 10631fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 10641fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10651fd3346740dfb7f47be9922312b68a4227fada96buzbee 10661fd3346740dfb7f47be9922312b68a4227fada96buzbee// Similar to GetSSAName, but if ssa name represents an immediate show that as well. 10672ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { 10681fd3346740dfb7f47be9922312b68a4227fada96buzbee if (reg_location_ == NULL) { 10691fd3346740dfb7f47be9922312b68a4227fada96buzbee // Pre-SSA - just use the standard name 10701fd3346740dfb7f47be9922312b68a4227fada96buzbee return GetSSAName(ssa_reg); 10711fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10721fd3346740dfb7f47be9922312b68a4227fada96buzbee if (IsConst(reg_location_[ssa_reg])) { 10731fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!singles_only && reg_location_[ssa_reg].wide) { 107423b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 10751fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValueWide(reg_location_[ssa_reg])); 10761fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 1077b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 10781fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValue(reg_location_[ssa_reg])); 10791fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10801fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 10811fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 10821fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10831fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10841fd3346740dfb7f47be9922312b68a4227fada96buzbee 10852ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::GetBlockName(BasicBlock* bb, char* name) { 10861fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (bb->block_type) { 10871fd3346740dfb7f47be9922312b68a4227fada96buzbee case kEntryBlock: 10881fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); 10891fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10901fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExitBlock: 10911fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); 10921fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10931fd3346740dfb7f47be9922312b68a4227fada96buzbee case kDalvikByteCode: 10941fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); 10951fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10961fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExceptionHandling: 10971fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, 10981fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id); 10991fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 11001fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 11011fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); 11021fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 11031fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11041fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11051fd3346740dfb7f47be9922312b68a4227fada96buzbee 11062ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromconst char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { 11070d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, use current code unit. 11081fd3346740dfb7f47be9922312b68a4227fada96buzbee const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); 11091fd3346740dfb7f47be9922312b68a4227fada96buzbee return cu_->dex_file->GetShorty(method_id.proto_idx_); 11101fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11111fd3346740dfb7f47be9922312b68a4227fada96buzbee 11121fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Debug Utility - dump a compilation unit */ 11132ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DumpMIRGraph() { 11141fd3346740dfb7f47be9922312b68a4227fada96buzbee BasicBlock* bb; 11151fd3346740dfb7f47be9922312b68a4227fada96buzbee const char* block_type_names[] = { 111617189ac098b2f156713db1821b49db7b2f018bbebuzbee "Null Block", 11171fd3346740dfb7f47be9922312b68a4227fada96buzbee "Entry Block", 11181fd3346740dfb7f47be9922312b68a4227fada96buzbee "Code Block", 11191fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exit Block", 11201fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exception Handling", 11211fd3346740dfb7f47be9922312b68a4227fada96buzbee "Catch Block" 11221fd3346740dfb7f47be9922312b68a4227fada96buzbee }; 11231fd3346740dfb7f47be9922312b68a4227fada96buzbee 11241fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); 11251fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << cu_->insns << " insns"; 11261fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << GetNumBlocks() << " blocks in total"; 1127862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 11281fd3346740dfb7f47be9922312b68a4227fada96buzbee 11291fd3346740dfb7f47be9922312b68a4227fada96buzbee while (true) { 1130862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = iterator.Next(); 11311fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb == NULL) break; 11321fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", 11331fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id, 11341fd3346740dfb7f47be9922312b68a4227fada96buzbee block_type_names[bb->block_type], 11351fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->start_offset, 11361fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, 11371fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? "" : " empty"); 11380d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 11390d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Taken branch: block " << bb->taken 11400d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; 11411fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 11430d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Fallthrough : block " << bb->fall_through 11440d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; 11451fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11461fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11471fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11481fd3346740dfb7f47be9922312b68a4227fada96buzbee 11491fd3346740dfb7f47be9922312b68a4227fada96buzbee/* 11501fd3346740dfb7f47be9922312b68a4227fada96buzbee * Build an array of location records for the incoming arguments. 11511fd3346740dfb7f47be9922312b68a4227fada96buzbee * Note: one location record per word of arguments, with dummy 11521fd3346740dfb7f47be9922312b68a4227fada96buzbee * high-word loc for wide arguments. Also pull up any following 11531fd3346740dfb7f47be9922312b68a4227fada96buzbee * MOVE_RESULT and incorporate it into the invoke. 11541fd3346740dfb7f47be9922312b68a4227fada96buzbee */ 11551fd3346740dfb7f47be9922312b68a4227fada96buzbeeCallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, 11562ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom bool is_range) { 1157f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), 1158f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocMisc)); 11591fd3346740dfb7f47be9922312b68a4227fada96buzbee MIR* move_result_mir = FindMoveResult(bb, mir); 11601fd3346740dfb7f47be9922312b68a4227fada96buzbee if (move_result_mir == NULL) { 11611fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result.location = kLocInvalid; 11621fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 11631fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result = GetRawDest(move_result_mir); 11641fd3346740dfb7f47be9922312b68a4227fada96buzbee move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); 11651fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11661fd3346740dfb7f47be9922312b68a4227fada96buzbee info->num_arg_words = mir->ssa_rep->num_uses; 11671fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> 1168f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, ArenaAllocator::kAllocMisc)); 11691fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < info->num_arg_words; i++) { 11701fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args[i] = GetRawSrc(mir, i); 11711fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11721fd3346740dfb7f47be9922312b68a4227fada96buzbee info->opt_flags = mir->optimization_flags; 11731fd3346740dfb7f47be9922312b68a4227fada96buzbee info->type = type; 11741fd3346740dfb7f47be9922312b68a4227fada96buzbee info->is_range = is_range; 11751fd3346740dfb7f47be9922312b68a4227fada96buzbee info->index = mir->dalvikInsn.vB; 11761fd3346740dfb7f47be9922312b68a4227fada96buzbee info->offset = mir->offset; 11771fd3346740dfb7f47be9922312b68a4227fada96buzbee return info; 11781fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11791fd3346740dfb7f47be9922312b68a4227fada96buzbee 1180862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee// Allocate a new basic block. 11812ce745c06271d5223d57dbf08117b20d5b60694aBrian CarlstromBasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { 1182f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier BasicBlock* bb = static_cast<BasicBlock*>(arena_->Alloc(sizeof(BasicBlock), 1183f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocBB)); 1184862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->block_type = block_type; 1185862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->id = block_id; 1186862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // TUNING: better estimate of the exit block predecessors? 11870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, 1188df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom (block_type == kExitBlock) ? 2048 : 2, 1189df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom kGrowableArrayPredecessors); 11900d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->successor_block_list_type = kNotUsed; 1191862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_id_map_.Put(block_id, block_id); 1192862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return bb; 1193862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} 11941fd3346740dfb7f47be9922312b68a4227fada96buzbee 11954e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeConstantPropagation() { 11964e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); 11974e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), ArenaAllocator::kAllocDFInfo)); 11984e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 11994e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12004e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeMethodUses() { 12014e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler // The gate starts by initializing the use counts 12024e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler int num_ssa_regs = GetNumSSARegs(); 12034e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Resize(num_ssa_regs + 32); 12044e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Resize(num_ssa_regs + 32); 12054e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler // Initialize list 12064e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler for (int i = 0; i < num_ssa_regs; i++) { 12074e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Insert(0); 12084e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Insert(0); 12094e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler } 12104e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12114e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12124e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeSSATransformation() { 12134e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Compute the DFS order */ 12144e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDFSOrders(); 12154e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12164e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Compute the dominator info */ 12174e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDominators(); 12184e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12194e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Allocate data structures in preparation for SSA conversion */ 12204e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler CompilerInitializeSSAConversion(); 12214e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12224e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Find out the "Dalvik reg def x block" relation */ 12234e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDefBlockMatrix(); 12244e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12254e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Insert phi nodes to dominance frontiers for all variables */ 12264e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler InsertPhiNodes(); 12274e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12284e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Rename register names by local defs and phi nodes */ 12294e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ClearAllVisitedFlags(); 12304e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler DoDFSPreOrderSSARename(GetEntryBlock()); 12314e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12324e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* 12334e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler * Shared temp bit vector used by each block to count the number of defs 12344e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler * from all the predecessor blocks. 12354e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler */ 12364e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler temp_ssa_register_v_ = 12374e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false, kBitMapTempSSARegisterV); 12384e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12394e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12404e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::CheckSSARegisterVector() { 12414e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler DCHECK(temp_ssa_register_v_ != nullptr); 12424e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12434e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12447934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom} // namespace art 1245