mir_graph.cc revision 29a2648821ea4d0b5d3aecb9f835822fdfe6faa1
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" 2429a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers#include "dex_instruction-inl.h" 255816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_to_method_inliner_map.h" 265816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_method_inliner.h" 27f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray#include "leb128.h" 285816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 29311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeenamespace art { 30311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 31311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#define MAX_PATTERN_LEN 5 32311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 331fd3346740dfb7f47be9922312b68a4227fada96buzbeeconst char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { 341fd3346740dfb7f47be9922312b68a4227fada96buzbee "Phi", 351fd3346740dfb7f47be9922312b68a4227fada96buzbee "Copy", 361fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplFloat", 371fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgFloat", 381fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplDouble", 391fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgDouble", 401fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpLong", 411fd3346740dfb7f47be9922312b68a4227fada96buzbee "Nop", 421fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpNullCheck", 431fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpRangeCheck", 441fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpDivZeroCheck", 451fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check1", 461fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check2", 471fd3346740dfb7f47be9922312b68a4227fada96buzbee "Select", 481fd3346740dfb7f47be9922312b68a4227fada96buzbee}; 491fd3346740dfb7f47be9922312b68a4227fada96buzbee 50862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeMIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 511fd3346740dfb7f47be9922312b68a4227fada96buzbee : reg_location_(NULL), 521fd3346740dfb7f47be9922312b68a4227fada96buzbee cu_(cu), 53311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_base_vregs_(NULL), 54311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_subscripts_(NULL), 55311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee vreg_to_ssa_map_(NULL), 56311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_last_defs_(NULL), 57311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee is_constant_v_(NULL), 58311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee constant_values_(NULL), 59862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee use_counts_(arena, 256, kGrowableArrayMisc), 60862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee raw_use_counts_(arena, 256, kGrowableArrayMisc), 61311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_reachable_blocks_(0), 62862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_(NULL), 63862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_(NULL), 64862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dom_post_order_traversal_(NULL), 65311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_(NULL), 66311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_block_matrix_(NULL), 67311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_dalvik_register_v_(NULL), 68bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_scoped_alloc_(), 69bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_insn_data_(nullptr), 70bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_bit_vector_size_(0u), 71bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_bit_vector_(nullptr), 72862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_(arena, 100, kGrowableArrayBlockList), 73311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee try_block_addr_(NULL), 74311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee entry_block_(NULL), 75311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee exit_block_(NULL), 76311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_blocks_(0), 77311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_(NULL), 78b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), 79311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_(kInvalidEntry), 80311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_(kInvalidEntry), 81311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_(0), 82311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_(NULL), 831fd3346740dfb7f47be9922312b68a4227fada96buzbee num_ssa_regs_(0), 841fd3346740dfb7f47be9922312b68a4227fada96buzbee method_sreg_(0), 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. 86862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee checkstats_(NULL), 87b48819db07f9a0992a72173380c24249d7fc648abuzbee arena_(arena), 88b48819db07f9a0992a72173380c24249d7fc648abuzbee backward_branches_(0), 89da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru forward_branches_(0), 90da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru compiler_temps_(arena, 6, kGrowableArrayMisc), 91da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru num_non_special_compiler_temps_(0), 92b1f1d642093418612c0a27ce4203b421bb6eb767buzbee max_available_non_special_compiler_temps_(0), 93be0e546730e532ef0987cd4bde2c6f5a1b14dd2aVladimir Marko punt_to_interpreter_(false), 943d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko merged_df_flags_(0u), 95be0e546730e532ef0987cd4bde2c6f5a1b14dd2aVladimir Marko ifield_lowering_infos_(arena, 0u), 96f096aad9203d7c50b2f9cbe1c1215a50c265a059Vladimir Marko sfield_lowering_infos_(arena, 0u), 97f096aad9203d7c50b2f9cbe1c1215a50c265a059Vladimir Marko method_lowering_infos_(arena, 0u) { 98862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); 99da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru max_available_special_compiler_temps_ = std::abs(static_cast<int>(kVRegNonSpecialTempBaseReg)) 100da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru - std::abs(static_cast<int>(kVRegTempBaseReg)); 101311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 102311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 1036282dc12440a2072dc06a616160027ff21bd895eIan RogersMIRGraph::~MIRGraph() { 1046282dc12440a2072dc06a616160027ff21bd895eIan Rogers STLDeleteElements(&m_units_); 1056282dc12440a2072dc06a616160027ff21bd895eIan Rogers} 1066282dc12440a2072dc06a616160027ff21bd895eIan Rogers 107311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 108311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Parse an instruction, return the length of the instruction 109311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 11029a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogersint MIRGraph::ParseInsn(const uint16_t* code_ptr, MIR::DecodedInstruction* decoded_instruction) { 11129a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers const Instruction* inst = Instruction::At(code_ptr); 11229a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->opcode = inst->Opcode(); 11329a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vA = inst->HasVRegA() ? inst->VRegA() : 0; 11429a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vB = inst->HasVRegB() ? inst->VRegB() : 0; 11529a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vB_wide = inst->HasWideVRegB() ? inst->WideVRegB() : 0; 11629a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vC = inst->HasVRegC() ? inst->VRegC() : 0; 11729a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers if (inst->HasVarArgs()) { 11829a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers inst->GetVarArgs(decoded_instruction->arg); 11929a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers } 12029a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers return inst->SizeInCodeUnits(); 121311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 122311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 123311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 124311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Split an existing block from the specified code offset into two */ 1250d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, 1262ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { 1270d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_GT(code_offset, orig_block->start_offset); 128311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MIR* insn = orig_block->first_mir_insn; 1290d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee MIR* prev = NULL; 130311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (insn) { 131311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->offset == code_offset) break; 1320d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee prev = insn; 133311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn = insn->next; 134311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 135311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn == NULL) { 136311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Break split failed"; 137311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 138862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); 139862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bottom_block); 140311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 141311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->start_offset = code_offset; 142311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->first_mir_insn = insn; 143311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->last_mir_insn = orig_block->last_mir_insn; 144311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 145311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* If this block was terminated by a return, the flag needs to go with the bottom block */ 146311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->terminated_by_return = orig_block->terminated_by_return; 147311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->terminated_by_return = false; 148311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 149311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the taken path */ 150311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->taken = orig_block->taken; 1510d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->taken != NullBasicBlockId) { 1520d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->taken = NullBasicBlockId; 1530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); 1540d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Delete(orig_block->id); 1550d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Insert(bottom_block->id); 156311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 157311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 158311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the fallthrough path */ 159311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->fall_through = orig_block->fall_through; 1600d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->fall_through = bottom_block->id; 1610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->predecessors->Insert(orig_block->id); 1620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->fall_through != NullBasicBlockId) { 1630d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); 1640d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Delete(orig_block->id); 1650d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Insert(bottom_block->id); 166311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 167311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 168311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the successor list */ 1690d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (orig_block->successor_block_list_type != kNotUsed) { 1700d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_block_list_type = orig_block->successor_block_list_type; 1710d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_blocks = orig_block->successor_blocks; 1720d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->successor_block_list_type = kNotUsed; 1730d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->successor_blocks = NULL; 1740d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); 175311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 176862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 177311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 1780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock *bb = GetBasicBlock(successor_block_info->block); 1790d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors->Delete(orig_block->id); 1800d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors->Insert(bottom_block->id); 181311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 182311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 183311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 1840d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->last_mir_insn = prev; 1850d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee prev->next = NULL; 186311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 187311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 188311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Update the immediate predecessor block pointer so that outgoing edges 189311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * can be applied to the proper block. 190311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 191311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (immed_pred_block_p) { 192311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(*immed_pred_block_p, orig_block); 193311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *immed_pred_block_p = bottom_block; 194311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 195b48819db07f9a0992a72173380c24249d7fc648abuzbee 196b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate dex instructions in the bottom block with the new container. 1974376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != nullptr); 1984376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != orig_block->first_mir_insn); 1994376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn == bottom_block->first_mir_insn); 2004376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(insn->offset, bottom_block->start_offset); 2014376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || 2024376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko !IsPseudoMirOp(insn->dalvikInsn.opcode)); 2034376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); 2044376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko MIR* p = insn; 2054376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 2064376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko while (p != bottom_block->last_mir_insn) { 2074376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko p = p->next; 2084376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(p != nullptr); 209b48819db07f9a0992a72173380c24249d7fc648abuzbee int opcode = p->dalvikInsn.opcode; 210b48819db07f9a0992a72173380c24249d7fc648abuzbee /* 211b48819db07f9a0992a72173380c24249d7fc648abuzbee * Some messiness here to ensure that we only enter real opcodes and only the 212b48819db07f9a0992a72173380c24249d7fc648abuzbee * first half of a potentially throwing instruction that has been split into 2134376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * CHECK and work portions. Since the 2nd half of a split operation is always 2144376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * the first in a BasicBlock, we can't hit it here. 215b48819db07f9a0992a72173380c24249d7fc648abuzbee */ 2164376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko if ((opcode == kMirOpCheck) || !IsPseudoMirOp(opcode)) { 2174376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); 218b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 219b48819db07f9a0992a72173380c24249d7fc648abuzbee } 220b48819db07f9a0992a72173380c24249d7fc648abuzbee } 221b48819db07f9a0992a72173380c24249d7fc648abuzbee 222311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bottom_block; 223311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 224311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 225311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 226311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Given a code offset, find out the block that starts with it. If the offset 227311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is in the middle of an existing block, split it into two. If immed_pred_block_p 228311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is not non-null and is the block being split, update *immed_pred_block_p to 229311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * point to the bottom block so that outgoing edges can be set up properly 230311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (by the caller) 231311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Utilizes a map for fast lookup of the typical cases. 232311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 2330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, 2342ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock** immed_pred_block_p) { 235bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee if (code_offset >= cu_->code_item->insns_size_in_code_units_) { 236311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return NULL; 237311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 238b48819db07f9a0992a72173380c24249d7fc648abuzbee 239b48819db07f9a0992a72173380c24249d7fc648abuzbee int block_id = dex_pc_to_block_map_.Get(code_offset); 240b48819db07f9a0992a72173380c24249d7fc648abuzbee BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); 241b48819db07f9a0992a72173380c24249d7fc648abuzbee 242b48819db07f9a0992a72173380c24249d7fc648abuzbee if ((bb != NULL) && (bb->start_offset == code_offset)) { 243b48819db07f9a0992a72173380c24249d7fc648abuzbee // Does this containing block start with the desired instruction? 244bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee return bb; 245bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee } 246311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 247b48819db07f9a0992a72173380c24249d7fc648abuzbee // No direct hit. 248b48819db07f9a0992a72173380c24249d7fc648abuzbee if (!create) { 249b48819db07f9a0992a72173380c24249d7fc648abuzbee return NULL; 250b48819db07f9a0992a72173380c24249d7fc648abuzbee } 251b48819db07f9a0992a72173380c24249d7fc648abuzbee 252b48819db07f9a0992a72173380c24249d7fc648abuzbee if (bb != NULL) { 253b48819db07f9a0992a72173380c24249d7fc648abuzbee // The target exists somewhere in an existing block. 254b48819db07f9a0992a72173380c24249d7fc648abuzbee return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : NULL); 255311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 256311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 257b48819db07f9a0992a72173380c24249d7fc648abuzbee // Create a new block. 258862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = NewMemBB(kDalvikByteCode, num_blocks_++); 259862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bb); 260311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset = code_offset; 261b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(bb->start_offset, bb->id); 262311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bb; 263311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 264311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 265b48819db07f9a0992a72173380c24249d7fc648abuzbee 266311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Identify code range in try blocks and set up the empty catch blocks */ 2672ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ProcessTryCatchBlocks() { 268311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int tries_size = current_code_item_->tries_size_; 2690d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset offset; 270311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 271311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (tries_size == 0) { 272311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 273311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 274311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 275311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < tries_size; i++) { 276311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const DexFile::TryItem* pTry = 277311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DexFile::GetTryItems(*current_code_item_, i); 2780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset start_offset = pTry->start_addr_; 2790d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset end_offset = start_offset + pTry->insn_count_; 280311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (offset = start_offset; offset < end_offset; offset++) { 281862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(offset); 282311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 283311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 284311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 285311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Iterate over each of the handlers to enqueue the empty Catch blocks 286311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); 287311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 288311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (uint32_t idx = 0; idx < handlers_size; idx++) { 289311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(handlers_ptr); 290311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (; iterator.HasNext(); iterator.Next()) { 291311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t address = iterator.GetHandlerAddress(); 292311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(address, false /* split */, true /*create*/, 293311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 294311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 295311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee handlers_ptr = iterator.EndDataPointer(); 296311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 297311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 298311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 299311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kBranch flag */ 3000d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 3010d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, const uint16_t* code_ptr, 3022ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_end) { 3030d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset target = cur_offset; 304311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee switch (insn->dalvikInsn.opcode) { 305311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO: 306311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_16: 307311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_32: 308311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vA; 309311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 310311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQ: 311311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NE: 312311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LT: 313311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GE: 314311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GT: 315311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LE: 316311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 317311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vC; 318311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 319311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQZ: 320311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NEZ: 321311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LTZ: 322311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GEZ: 323311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GTZ: 324311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LEZ: 325311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 326311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vB; 327311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 328311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee default: 329311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; 330311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 331b48819db07f9a0992a72173380c24249d7fc648abuzbee CountBranch(target); 332311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *taken_block = FindBlock(target, /* split */ true, /* create */ true, 333311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ &cur_block); 3340d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = taken_block->id; 3350d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee taken_block->predecessors->Insert(cur_block->id); 336311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 337311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Always terminate the current block for conditional branches */ 338311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kContinue) { 339311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *fallthrough_block = FindBlock(cur_offset + width, 340311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 341311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * If the method is processed 342311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * in sequential order from the 343311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * beginning, we don't need to 344311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * specify split for continue 345311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * blocks. However, this 346311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * routine can be called by 347311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * compileLoop, which starts 348311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * parsing the method from an 349311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * arbitrary address in the 350311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * method body. 351311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 352311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 353311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ 354311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 355311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ 356311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee &cur_block); 3570d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 3580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 359311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (code_ptr < code_end) { 3602724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 361311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 362311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 363311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 364311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 365311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 366311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kSwitch flag */ 36717189ac098b2f156713db1821b49db7b2f018bbebuzbeeBasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 36817189ac098b2f156713db1821b49db7b2f018bbebuzbee int width, int flags) { 369311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* switch_data = 370311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); 371311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int size; 372311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* keyTable; 373311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* target_table; 374311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int i; 375311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int first_key; 376311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 377311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 378311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Packed switch data format: 379311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0100 magic value 380311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table 381311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int first_key first (and lowest) switch case value 382311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 383311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 384311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (4+size*2) 16-bit code units. 385311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 386311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { 387311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 388311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kPackedSwitchSignature)); 389311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 390311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = switch_data[2] | (switch_data[3] << 16); 391311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[4]); 392311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = NULL; // Make the compiler happy 393311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 394311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Sparse switch data format: 395311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0200 magic value 396311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table; > 0 397311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int keys[size] keys, sorted low-to-high; 32-bit aligned 398311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 399311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 400311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (2+size*4) 16-bit code units. 401311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 402311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 403311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 404311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kSparseSwitchSignature)); 405311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 406311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = reinterpret_cast<const int*>(&switch_data[2]); 407311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); 408311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = 0; // To make the compiler happy 409311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 410311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4110d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 412311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 4130d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 414311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 4150d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_block_list_type = 4160d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; 4170d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks = 418df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); 419311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 420311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (i = 0; i < size; i++) { 421311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *case_block = FindBlock(cur_offset + target_table[i], /* split */ true, 422311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ true, /* immed_pred_block_p */ &cur_block); 423311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = 424f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), 42583cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocSuccessor)); 4260d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = case_block->id; 427311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = 428311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 429311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key + i : keyTable[i]; 4300d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 4310d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee case_block->predecessors->Insert(cur_block->id); 432311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 433311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 434311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Fall-through case */ 435df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, 436df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom /* create */ true, /* immed_pred_block_p */ NULL); 4370d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 4380d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 43917189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 440311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 441311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 442311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kThrow flag */ 4430d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 4440d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, ArenaBitVector* try_block_addr, 4452ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_ptr, const uint16_t* code_end) { 446862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool in_try_block = try_block_addr->IsBitSet(cur_offset); 44717189ac098b2f156713db1821b49db7b2f018bbebuzbee bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); 44817189ac098b2f156713db1821b49db7b2f018bbebuzbee bool build_all_edges = 44917189ac098b2f156713db1821b49db7b2f018bbebuzbee (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; 450311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 451311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* In try block */ 452311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (in_try_block) { 453311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(*current_code_item_, cur_offset); 454311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4550d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 456311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 457311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 4580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 459311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 460311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_block_list_type = kCatch; 4620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks = 463862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, 2, kGrowableArraySuccessorBlocks); 464311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 46502c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom for (; iterator.HasNext(); iterator.Next()) { 466311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, 467311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false /* creat */, NULL /* immed_pred_block_p */); 468311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catch_block->catch_entry = true; 469311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (kIsDebugBuild) { 470311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catches_.insert(catch_block->start_offset); 471311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 472311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 47383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 4740d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = catch_block->id; 475311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = iterator.GetHandlerTypeIndex(); 4760d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 4770d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee catch_block->predecessors->Insert(cur_block->id); 478311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 47917189ac098b2f156713db1821b49db7b2f018bbebuzbee } else if (build_all_edges) { 480862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *eh_block = NewMemBB(kExceptionHandling, num_blocks_++); 4810d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = eh_block->id; 482862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(eh_block); 483311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee eh_block->start_offset = cur_offset; 4840d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee eh_block->predecessors->Insert(cur_block->id); 485311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 486311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 48717189ac098b2f156713db1821b49db7b2f018bbebuzbee if (is_throw) { 488311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->explicit_throw = true; 4892724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (code_ptr < code_end) { 490311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Force creation of new block following THROW via side-effect 491311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 492311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 493311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 494311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (!in_try_block) { 495311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Don't split a THROW that can't rethrow - we're done. 496311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 497311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 498311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 499311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 50017189ac098b2f156713db1821b49db7b2f018bbebuzbee if (!build_all_edges) { 50117189ac098b2f156713db1821b49db7b2f018bbebuzbee /* 50217189ac098b2f156713db1821b49db7b2f018bbebuzbee * Even though there is an exception edge here, control cannot return to this 50317189ac098b2f156713db1821b49db7b2f018bbebuzbee * method. Thus, for the purposes of dataflow analysis and optimization, we can 50417189ac098b2f156713db1821b49db7b2f018bbebuzbee * ignore the edge. Doing this reduces compile time, and increases the scope 50517189ac098b2f156713db1821b49db7b2f018bbebuzbee * of the basic-block level optimization pass. 50617189ac098b2f156713db1821b49db7b2f018bbebuzbee */ 50717189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 50817189ac098b2f156713db1821b49db7b2f018bbebuzbee } 50917189ac098b2f156713db1821b49db7b2f018bbebuzbee 510311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 511311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Split the potentially-throwing instruction into two parts. 512311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The first half will be a pseudo-op that captures the exception 513311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * edges and terminates the basic block. It always falls through. 514311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Then, create a new basic block that begins with the throwing instruction 515311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (minus exceptions). Note: this new basic block must NOT be entered into 516311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the block_map. If the potentially-throwing instruction is the target of a 517311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * future branch, we need to find the check psuedo half. The new 518311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * basic block containing the work portion of the instruction should 519311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * only be entered via fallthrough from the block containing the 520311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * pseudo exception edge MIR. Note also that this new block is 521311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * not automatically terminated after the work portion, and may 522311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * contain following instructions. 523b48819db07f9a0992a72173380c24249d7fc648abuzbee * 524b48819db07f9a0992a72173380c24249d7fc648abuzbee * Note also that the dex_pc_to_block_map_ entry for the potentially 525b48819db07f9a0992a72173380c24249d7fc648abuzbee * throwing instruction will refer to the original basic block. 526311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 527862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *new_block = NewMemBB(kDalvikByteCode, num_blocks_++); 528862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(new_block); 529311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee new_block->start_offset = insn->offset; 5300d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = new_block->id; 5310d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee new_block->predecessors->Insert(cur_block->id); 53283cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko MIR* new_insn = static_cast<MIR*>(arena_->Alloc(sizeof(MIR), kArenaAllocMIR)); 533311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *new_insn = *insn; 534311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->dalvikInsn.opcode = 535311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<Instruction::Code>(kMirOpCheck); 536311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Associate the two halves 537311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->meta.throw_insn = new_insn; 538cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler new_block->AppendMIR(new_insn); 539311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return new_block; 540311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 541311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 542311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ 543311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 5448b2c0b9abc3f520495f4387ea040132ba85cae69Ian Rogers InvokeType invoke_type, uint16_t class_def_idx, 5452ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { 546311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_ = code_item; 547311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee method_stack_.push_back(std::make_pair(current_method_, current_offset_)); 548311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_ = m_units_.size(); 549311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ = 0; 550311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: will need to snapshot stack image and use that as the mir context identification. 551311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), 5522730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko dex_file, current_code_item_, class_def_idx, method_idx, access_flags, 5532730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); 554311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_ptr = current_code_item_->insns_; 555311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_end = 556311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; 557311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 558311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: need to rework expansion of block list & try_block_addr when inlining activated. 559b48819db07f9a0992a72173380c24249d7fc648abuzbee // TUNING: use better estimate of basic blocks for following resize. 560862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); 561b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_); 562bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee 563311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: replace with explicit resize routine. Using automatic extension side effect for now. 564862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); 565862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); 566311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 567311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // If this is the first method, set up default entry and exit blocks. 568311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (current_method_ == 0) { 569311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(entry_block_ == NULL); 570311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(exit_block_ == NULL); 5714274889d48ef82369bf2c1ca70d84689b4f9e93aBrian Carlstrom DCHECK_EQ(num_blocks_, 0); 5720d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Use id 0 to represent a null block. 5730d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); 5740d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(null_block->id, NullBasicBlockId); 5750d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee null_block->hidden = true; 5760d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee block_list_.Insert(null_block); 577862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); 578862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(entry_block_); 5790d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_ = NewMemBB(kExitBlock, num_blocks_++); 580862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(exit_block_); 581311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. 582311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->dex_file = &dex_file; 583311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->class_def_idx = class_def_idx; 584311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->method_idx = method_idx; 585311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->access_flags = access_flags; 586311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->invoke_type = invoke_type; 587311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); 588311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_ins = current_code_item_->ins_size_; 589311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_regs = current_code_item_->registers_size_ - cu_->num_ins; 590311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_outs = current_code_item_->outs_size_; 591311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_dalvik_registers = current_code_item_->registers_size_; 592311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->insns = current_code_item_->insns_; 593311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->code_item = current_code_item_; 594311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 595311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; 596311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 597311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Will need to manage storage for ins & outs, push prevous state and update 598311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * insert point. 599311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 600311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 601311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 602311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Current block to record parsed instructions */ 603862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); 6040d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(current_offset_, 0U); 605311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->start_offset = current_offset_; 606862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(cur_block); 6070d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, insert at the insert point rather than entry block. 6080d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee entry_block_->fall_through = cur_block->id; 6090d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->predecessors->Insert(entry_block_->id); 610311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6113d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko /* Identify code range in try blocks and set up the empty catch blocks */ 612311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ProcessTryCatchBlocks(); 613311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6143d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko uint64_t merged_df_flags = 0u; 6153d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko 616311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Parse all instructions and put them into containing basic blocks */ 617311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (code_ptr < code_end) { 61883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko MIR *insn = static_cast<MIR *>(arena_->Alloc(sizeof(MIR), kArenaAllocMIR)); 619311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->offset = current_offset_; 620311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->m_unit_index = current_method_; 621311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int width = ParseInsn(code_ptr, &insn->dalvikInsn); 622311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->width = width; 623311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee Instruction::Code opcode = insn->dalvikInsn.opcode; 624311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_ != NULL) { 625311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_[static_cast<int>(opcode)]++; 626311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 627311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 628311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int flags = Instruction::FlagsOf(insn->dalvikInsn.opcode); 629b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int verify_flags = Instruction::VerifyFlagsOf(insn->dalvikInsn.opcode); 630311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 631cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler uint64_t df_flags = GetDataFlowAttributes(insn); 6323d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko merged_df_flags |= df_flags; 633311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 634311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (df_flags & DF_HAS_DEFS) { 635311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; 636311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 637311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6381da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee if (df_flags & DF_LVN) { 6391da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee cur_block->use_lvn = true; // Run local value numbering on this basic block. 6401da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee } 6411da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee 6422724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Check for inline data block signatures 6432724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (opcode == Instruction::NOP) { 6442724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. 6452724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { 6462724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. 6472724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee uint16_t following_raw_instruction = code_ptr[1]; 6482724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || 6492724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kPackedSwitchSignature) || 6502724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kArrayDataSignature)) { 6512724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); 6522724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6532724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6542724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (width == 1) { 6552724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // It is a simple nop - treat normally. 656cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler cur_block->AppendMIR(insn); 6572724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 6580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId); 6590d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->taken == NullBasicBlockId); 6602724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Unreachable instruction, mark for no continuation. 6612724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee flags &= ~Instruction::kContinue; 6622724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6632724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 664cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler cur_block->AppendMIR(insn); 6652724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6662724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 667b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate the starting dex_pc for this opcode with its containing basic block. 668b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(insn->offset, cur_block->id); 669b48819db07f9a0992a72173380c24249d7fc648abuzbee 6702724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee code_ptr += width; 6712724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 672311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kBranch) { 673311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanBranch(cur_block, insn, current_offset_, 674311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee width, flags, code_ptr, code_end); 675311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kReturn) { 676311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->terminated_by_return = true; 6770d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = exit_block_->id; 6780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_->predecessors->Insert(cur_block->id); 679311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 680311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Terminate the current block if there are instructions 681311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * afterwards. 682311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 683311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (code_ptr < code_end) { 684311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 685311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Create a fallthrough block for real instructions 686311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (incl. NOP). 687311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 6882724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(current_offset_ + width, /* split */ false, /* create */ true, 6892724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee /* immed_pred_block_p */ NULL); 690311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 691311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kThrow) { 692311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, 693311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee code_ptr, code_end); 694311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kSwitch) { 69517189ac098b2f156713db1821b49db7b2f018bbebuzbee cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); 696311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 697b1f1d642093418612c0a27ce4203b421bb6eb767buzbee if (verify_flags & Instruction::kVerifyVarArgRange) { 698b1f1d642093418612c0a27ce4203b421bb6eb767buzbee /* 699b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * The Quick backend's runtime model includes a gap between a method's 700b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * argument ("in") vregs and the rest of its vregs. Handling a range instruction 701b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * which spans the gap is somewhat complicated, and should not happen 702b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * in normal usage of dx. Punt to the interpreter. 703b1f1d642093418612c0a27ce4203b421bb6eb767buzbee */ 704b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int first_reg_in_range = insn->dalvikInsn.vC; 705b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int last_reg_in_range = first_reg_in_range + insn->dalvikInsn.vA - 1; 706b1f1d642093418612c0a27ce4203b421bb6eb767buzbee if (IsInVReg(first_reg_in_range) != IsInVReg(last_reg_in_range)) { 707b1f1d642093418612c0a27ce4203b421bb6eb767buzbee punt_to_interpreter_ = true; 708b1f1d642093418612c0a27ce4203b421bb6eb767buzbee } 709b1f1d642093418612c0a27ce4203b421bb6eb767buzbee } 710311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ += width; 711311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *next_block = FindBlock(current_offset_, /* split */ false, /* create */ 712311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false, /* immed_pred_block_p */ NULL); 713311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (next_block) { 714311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 715311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The next instruction could be the target of a previously parsed 716311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * forward branch so a block is already created. If the current 717311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * instruction is not an unconditional branch, connect them through 718311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the fall-through link. 719311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 7200d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId || 7210d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == next_block || 7220d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == exit_block_); 723311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7240d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { 7250d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = next_block->id; 7260d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee next_block->predecessors->Insert(cur_block->id); 727311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 728311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = next_block; 729311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 730311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 7313d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko merged_df_flags_ = merged_df_flags; 7325816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 733311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 734311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DumpCFG("/sdcard/1_post_parse_cfg/", true); 735311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 736311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 737311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 7381fd3346740dfb7f47be9922312b68a4227fada96buzbee DumpMIRGraph(); 739311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 740311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 741311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7422ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ShowOpcodeStats() { 743311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(opcode_count_ != NULL); 744311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "Opcode Count"; 745311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < kNumPackedOpcodes; i++) { 746311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_[i] != 0) { 747311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) 748311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee << " " << opcode_count_[i]; 749311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 750311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 751311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 752311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 753cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyleruint64_t MIRGraph::GetDataFlowAttributes(Instruction::Code opcode) { 754cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler DCHECK_LT((size_t) opcode, (sizeof(oat_data_flow_attributes_) / sizeof(oat_data_flow_attributes_[0]))); 755cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler return oat_data_flow_attributes_[opcode]; 756cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler} 757cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler 758cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyleruint64_t MIRGraph::GetDataFlowAttributes(MIR* mir) { 759cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler DCHECK(mir != nullptr); 760cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler Instruction::Code opcode = mir->dalvikInsn.opcode; 761cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler return GetDataFlowAttributes(opcode); 762cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler} 763cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler 764311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee// TODO: use a configurable base prefix, and adjust callers to supply pass name. 765311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Dump the CFG into a DOT graph */ 766d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beylervoid MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { 767311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FILE* file; 768311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); 769311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ReplaceSpecialChars(fname); 770d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler fname = StringPrintf("%s%s%x%s.dot", dir_prefix, fname.c_str(), 771d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, 772d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler suffix == nullptr ? "" : suffix); 773311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee file = fopen(fname.c_str(), "w"); 774311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (file == NULL) { 775311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 776311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 777311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "digraph G {\n"); 778311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 779311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " rankdir=TB\n"); 780311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 781311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; 782311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int idx; 783311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 784311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (idx = 0; idx < num_blocks; idx++) { 785862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int block_idx = all_blocks ? idx : dfs_order_->Get(idx); 786311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *bb = GetBasicBlock(block_idx); 78725bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru if (bb == NULL) continue; 788311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kDead) continue; 789311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kEntryBlock) { 790311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); 791311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExitBlock) { 792311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); 793311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kDalvikByteCode) { 794311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", 795311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id); 796311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const MIR *mir; 797311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 798311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->first_mir_insn ? " | " : " "); 799311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (mir = bb->first_mir_insn; mir; mir = mir->next) { 800311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int opcode = mir->dalvikInsn.opcode; 801311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {%04x %s %s %s\\l}%s\\\n", mir->offset, 8021fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->ssa_rep ? GetDalvikDisassembly(mir) : 803311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (opcode < kMirOpFirst) ? Instruction::Name(mir->dalvikInsn.opcode) : 8041fd3346740dfb7f47be9922312b68a4227fada96buzbee extended_mir_op_names_[opcode - kMirOpFirst], 805311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", 806311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", 807311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee mir->next ? " | " : " "); 808311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 809311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 810311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExceptionHandling) { 811311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name[BLOCK_NAME_LEN]; 812311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 813311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name); 814311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s [shape=invhouse];\n", block_name); 815311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 816311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 817311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 818311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8190d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 820311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 8210d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->taken), block_name2); 822311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n [style=dotted]\n", 823311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name2); 824311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 8250d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 826311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 8270d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->fall_through), block_name2); 828311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); 829311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 830311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8310d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type != kNotUsed) { 832311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", 833311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id, 8340d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); 8350d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 836862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 837311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 838311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int succ_id = 0; 839311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 840311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 841311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock *dest_block = GetBasicBlock(successor_block_info->block); 843862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *next_successor_block_info = iterator.Next(); 844311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 845311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 846311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id++, 847311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key, 848311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee dest_block->start_offset, 849311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (next_successor_block_info != NULL) ? " | " : " "); 850311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 851311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info = next_successor_block_info; 852311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 853311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 854311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 855311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 856311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", 857311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, bb->start_offset, bb->id); 858311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 85925bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru // Link the successor pseudo-block with all of its potential targets. 86025bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); 861311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 86225bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru succ_id = 0; 86325bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru while (true) { 86425bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru SuccessorBlockInfo *successor_block_info = iter.Next(); 86525bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru if (successor_block_info == NULL) break; 866311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 86725bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 868311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 86925bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru GetBlockName(dest_block, block_name2); 87025bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, 87125bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru bb->id, succ_id++, block_name2); 872311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 873311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 874311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "\n"); 875311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 876311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 877311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Display the dominator tree */ 878311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 879311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 880311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name1); 881311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->i_dom) { 8820d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->i_dom), block_name2); 883311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); 884311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 885311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 886311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 887311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "}\n"); 888311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fclose(file); 889311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 890311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8911fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the end of a basic block */ 892cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beylervoid BasicBlock::AppendMIR(MIR* mir) { 893cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler if (first_mir_insn == nullptr) { 894cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler DCHECK(last_mir_insn == nullptr); 895cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler last_mir_insn = first_mir_insn = mir; 896cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler mir->next = nullptr; 8971fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 898cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler last_mir_insn->next = mir; 899cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler mir->next = nullptr; 900cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler last_mir_insn = mir; 9011fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9021fd3346740dfb7f47be9922312b68a4227fada96buzbee} 9031fd3346740dfb7f47be9922312b68a4227fada96buzbee 9041fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the head of a basic block */ 905cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beylervoid BasicBlock::PrependMIR(MIR* mir) { 906cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler if (first_mir_insn == nullptr) { 907cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler DCHECK(last_mir_insn == nullptr); 908cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler last_mir_insn = first_mir_insn = mir; 909cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler mir->next = nullptr; 9101fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 911cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler mir->next = first_mir_insn; 912cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler first_mir_insn = mir; 9131fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9141fd3346740dfb7f47be9922312b68a4227fada96buzbee} 9151fd3346740dfb7f47be9922312b68a4227fada96buzbee 9161fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert a MIR instruction after the specified MIR */ 917cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beylervoid BasicBlock::InsertMIRAfter(MIR* current_mir, MIR* new_mir) { 9181fd3346740dfb7f47be9922312b68a4227fada96buzbee new_mir->next = current_mir->next; 9191fd3346740dfb7f47be9922312b68a4227fada96buzbee current_mir->next = new_mir; 9201fd3346740dfb7f47be9922312b68a4227fada96buzbee 921cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler if (last_mir_insn == current_mir) { 9221fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Is the last MIR in the block */ 923cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler last_mir_insn = new_mir; 9241fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9251fd3346740dfb7f47be9922312b68a4227fada96buzbee} 9261fd3346740dfb7f47be9922312b68a4227fada96buzbee 927cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe BeylerMIR* BasicBlock::GetNextUnconditionalMir(MIRGraph* mir_graph, MIR* current) { 9283bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru MIR* next_mir = nullptr; 9293bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9303bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru if (current != nullptr) { 9313bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru next_mir = current->next; 9323bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 9333bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9343bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru if (next_mir == nullptr) { 9353bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru // Only look for next MIR that follows unconditionally. 936cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler if ((taken == NullBasicBlockId) && (fall_through != NullBasicBlockId)) { 937cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler next_mir = mir_graph->GetBasicBlock(fall_through)->first_mir_insn; 9383bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 9393bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 9403bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9413bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru return next_mir; 9423bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru} 9433bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 9442ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromchar* MIRGraph::GetDalvikDisassembly(const MIR* mir) { 94529a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers MIR::DecodedInstruction insn = mir->dalvikInsn; 9461fd3346740dfb7f47be9922312b68a4227fada96buzbee std::string str; 9471fd3346740dfb7f47be9922312b68a4227fada96buzbee int flags = 0; 9481fd3346740dfb7f47be9922312b68a4227fada96buzbee int opcode = insn.opcode; 9491fd3346740dfb7f47be9922312b68a4227fada96buzbee char* ret; 9501fd3346740dfb7f47be9922312b68a4227fada96buzbee bool nop = false; 9511fd3346740dfb7f47be9922312b68a4227fada96buzbee SSARepresentation* ssa_rep = mir->ssa_rep; 9521fd3346740dfb7f47be9922312b68a4227fada96buzbee Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format 9531fd3346740dfb7f47be9922312b68a4227fada96buzbee int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; 9541fd3346740dfb7f47be9922312b68a4227fada96buzbee int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; 9551fd3346740dfb7f47be9922312b68a4227fada96buzbee 9561fd3346740dfb7f47be9922312b68a4227fada96buzbee // Handle special cases. 9571fd3346740dfb7f47be9922312b68a4227fada96buzbee if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { 9581fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 9591fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(": "); 9601fd3346740dfb7f47be9922312b68a4227fada96buzbee // Recover the original Dex instruction 9611fd3346740dfb7f47be9922312b68a4227fada96buzbee insn = mir->meta.throw_insn->dalvikInsn; 9621fd3346740dfb7f47be9922312b68a4227fada96buzbee ssa_rep = mir->meta.throw_insn->ssa_rep; 9631fd3346740dfb7f47be9922312b68a4227fada96buzbee defs = ssa_rep->num_defs; 9641fd3346740dfb7f47be9922312b68a4227fada96buzbee uses = ssa_rep->num_uses; 9651fd3346740dfb7f47be9922312b68a4227fada96buzbee opcode = insn.opcode; 9661fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if (opcode == kMirOpNop) { 9671fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("["); 9680d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Recover original opcode. 9690d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); 9700d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee opcode = insn.opcode; 9711fd3346740dfb7f47be9922312b68a4227fada96buzbee nop = true; 9721fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9731fd3346740dfb7f47be9922312b68a4227fada96buzbee 9741fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode >= kMirOpFirst) { 9751fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 9761fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 9771fd3346740dfb7f47be9922312b68a4227fada96buzbee dalvik_format = Instruction::FormatOf(insn.opcode); 9781fd3346740dfb7f47be9922312b68a4227fada96buzbee flags = Instruction::FlagsOf(insn.opcode); 9791fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(Instruction::Name(insn.opcode)); 9801fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9811fd3346740dfb7f47be9922312b68a4227fada96buzbee 9821fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode == kMirOpPhi) { 9830d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlockId* incoming = mir->meta.phi_incoming; 9841fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s = (%s", 9851fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), 9861fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); 987b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom str.append(StringPrintf(":%d", incoming[0])); 9881fd3346740dfb7f47be9922312b68a4227fada96buzbee int i; 9891fd3346740dfb7f47be9922312b68a4227fada96buzbee for (i = 1; i < uses; i++) { 9901fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", %s:%d", 9911fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), 9921fd3346740dfb7f47be9922312b68a4227fada96buzbee incoming[i])); 9931fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9941fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(")"); 9951fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if ((flags & Instruction::kBranch) != 0) { 9961fd3346740dfb7f47be9922312b68a4227fada96buzbee // For branches, decode the instructions to print out the branch targets. 9971fd3346740dfb7f47be9922312b68a4227fada96buzbee int offset = 0; 9981fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 9991fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21t: 10001fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 10011fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vB; 10021fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10031fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22t: 10041fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), 10051fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); 10061fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vC; 10071fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10081fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k10t: 10091fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k20t: 10101fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k30t: 10111fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vA; 10121fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10131fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 10141fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; 10151fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10161fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset, 10171fd3346740dfb7f47be9922312b68a4227fada96buzbee offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); 10181fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 10191fd3346740dfb7f47be9922312b68a4227fada96buzbee // For invokes-style formats, treat wide regs as a pair of singles 10201fd3346740dfb7f47be9922312b68a4227fada96buzbee bool show_singles = ((dalvik_format == Instruction::k35c) || 10211fd3346740dfb7f47be9922312b68a4227fada96buzbee (dalvik_format == Instruction::k3rc)); 10221fd3346740dfb7f47be9922312b68a4227fada96buzbee if (defs != 0) { 10231fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s", GetSSANameWithConst(ssa_rep->defs[0], false).c_str())); 10241fd3346740dfb7f47be9922312b68a4227fada96buzbee if (uses != 0) { 10251fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(", "); 10261fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10271fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10281fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < uses; i++) { 10291fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append( 10301fd3346740dfb7f47be9922312b68a4227fada96buzbee StringPrintf(" %s", GetSSANameWithConst(ssa_rep->uses[i], show_singles).c_str())); 10311fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { 10321fd3346740dfb7f47be9922312b68a4227fada96buzbee // For the listing, skip the high sreg. 10331fd3346740dfb7f47be9922312b68a4227fada96buzbee i++; 10341fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10351fd3346740dfb7f47be9922312b68a4227fada96buzbee if (i != (uses -1)) { 10361fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(","); 10371fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10381fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10391fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 10407934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k11n: // Add one immediate from vB 10411fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21s: 10421fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31i: 10431fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21h: 10441fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vB)); 10451fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10467934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k51l: // Add one wide immediate 104723b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); 10481fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10497934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k21c: // One register, one string/type/method index 10501fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31c: 10511fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vB)); 10521fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10537934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k22c: // Two registers, one string/type/method index 10541fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vC)); 10551fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10567934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k22s: // Add one immediate from vC 10571fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22b: 10581fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vC)); 10591fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 106002c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom default: { 106102c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom // Nothing left to print 10621fd3346740dfb7f47be9922312b68a4227fada96buzbee } 106302c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom } 10641fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10651fd3346740dfb7f47be9922312b68a4227fada96buzbee if (nop) { 10661fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("]--optimized away"); 10671fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10681fd3346740dfb7f47be9922312b68a4227fada96buzbee int length = str.length() + 1; 106983cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ret = static_cast<char*>(arena_->Alloc(length, kArenaAllocDFInfo)); 10701fd3346740dfb7f47be9922312b68a4227fada96buzbee strncpy(ret, str.c_str(), length); 10711fd3346740dfb7f47be9922312b68a4227fada96buzbee return ret; 10721fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10731fd3346740dfb7f47be9922312b68a4227fada96buzbee 10741fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Turn method name into a legal Linux file name */ 10752ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ReplaceSpecialChars(std::string& str) { 10769b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static const struct { const char before; const char after; } match[] = { 10779b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, 10789b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} 10799b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom }; 10801fd3346740dfb7f47be9922312b68a4227fada96buzbee for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { 10811fd3346740dfb7f47be9922312b68a4227fada96buzbee std::replace(str.begin(), str.end(), match[i].before, match[i].after); 10821fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10831fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10841fd3346740dfb7f47be9922312b68a4227fada96buzbee 10852ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSAName(int ssa_reg) { 108639ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to 108739ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // the arena. We should be smarter and just place straight into the arena, or compute the 108839ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // value more lazily. 10891fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 10901fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10911fd3346740dfb7f47be9922312b68a4227fada96buzbee 10921fd3346740dfb7f47be9922312b68a4227fada96buzbee// Similar to GetSSAName, but if ssa name represents an immediate show that as well. 10932ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { 10941fd3346740dfb7f47be9922312b68a4227fada96buzbee if (reg_location_ == NULL) { 10951fd3346740dfb7f47be9922312b68a4227fada96buzbee // Pre-SSA - just use the standard name 10961fd3346740dfb7f47be9922312b68a4227fada96buzbee return GetSSAName(ssa_reg); 10971fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10981fd3346740dfb7f47be9922312b68a4227fada96buzbee if (IsConst(reg_location_[ssa_reg])) { 10991fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!singles_only && reg_location_[ssa_reg].wide) { 110023b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 11011fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValueWide(reg_location_[ssa_reg])); 11021fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 1103b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 11041fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValue(reg_location_[ssa_reg])); 11051fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11061fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 11071fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 11081fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11091fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11101fd3346740dfb7f47be9922312b68a4227fada96buzbee 11112ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::GetBlockName(BasicBlock* bb, char* name) { 11121fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (bb->block_type) { 11131fd3346740dfb7f47be9922312b68a4227fada96buzbee case kEntryBlock: 11141fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); 11151fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 11161fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExitBlock: 11171fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); 11181fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 11191fd3346740dfb7f47be9922312b68a4227fada96buzbee case kDalvikByteCode: 11201fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); 11211fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 11221fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExceptionHandling: 11231fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, 11241fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id); 11251fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 11261fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 11271fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); 11281fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 11291fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11301fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11311fd3346740dfb7f47be9922312b68a4227fada96buzbee 11322ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromconst char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { 11330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, use current code unit. 11341fd3346740dfb7f47be9922312b68a4227fada96buzbee const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); 11351fd3346740dfb7f47be9922312b68a4227fada96buzbee return cu_->dex_file->GetShorty(method_id.proto_idx_); 11361fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11371fd3346740dfb7f47be9922312b68a4227fada96buzbee 11381fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Debug Utility - dump a compilation unit */ 11392ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DumpMIRGraph() { 11401fd3346740dfb7f47be9922312b68a4227fada96buzbee BasicBlock* bb; 11411fd3346740dfb7f47be9922312b68a4227fada96buzbee const char* block_type_names[] = { 114217189ac098b2f156713db1821b49db7b2f018bbebuzbee "Null Block", 11431fd3346740dfb7f47be9922312b68a4227fada96buzbee "Entry Block", 11441fd3346740dfb7f47be9922312b68a4227fada96buzbee "Code Block", 11451fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exit Block", 11461fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exception Handling", 11471fd3346740dfb7f47be9922312b68a4227fada96buzbee "Catch Block" 11481fd3346740dfb7f47be9922312b68a4227fada96buzbee }; 11491fd3346740dfb7f47be9922312b68a4227fada96buzbee 11501fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); 11511fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << cu_->insns << " insns"; 11521fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << GetNumBlocks() << " blocks in total"; 1153862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 11541fd3346740dfb7f47be9922312b68a4227fada96buzbee 11551fd3346740dfb7f47be9922312b68a4227fada96buzbee while (true) { 1156862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = iterator.Next(); 11571fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb == NULL) break; 11581fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", 11591fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id, 11601fd3346740dfb7f47be9922312b68a4227fada96buzbee block_type_names[bb->block_type], 11611fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->start_offset, 11621fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, 11631fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? "" : " empty"); 11640d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 11650d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Taken branch: block " << bb->taken 11660d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; 11671fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11680d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 11690d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Fallthrough : block " << bb->fall_through 11700d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; 11711fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11721fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11731fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11741fd3346740dfb7f47be9922312b68a4227fada96buzbee 11751fd3346740dfb7f47be9922312b68a4227fada96buzbee/* 11761fd3346740dfb7f47be9922312b68a4227fada96buzbee * Build an array of location records for the incoming arguments. 11771fd3346740dfb7f47be9922312b68a4227fada96buzbee * Note: one location record per word of arguments, with dummy 11781fd3346740dfb7f47be9922312b68a4227fada96buzbee * high-word loc for wide arguments. Also pull up any following 11791fd3346740dfb7f47be9922312b68a4227fada96buzbee * MOVE_RESULT and incorporate it into the invoke. 11801fd3346740dfb7f47be9922312b68a4227fada96buzbee */ 11811fd3346740dfb7f47be9922312b68a4227fada96buzbeeCallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, 11822ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom bool is_range) { 1183f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), 118483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocMisc)); 11851fd3346740dfb7f47be9922312b68a4227fada96buzbee MIR* move_result_mir = FindMoveResult(bb, mir); 11861fd3346740dfb7f47be9922312b68a4227fada96buzbee if (move_result_mir == NULL) { 11871fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result.location = kLocInvalid; 11881fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 11891fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result = GetRawDest(move_result_mir); 11901fd3346740dfb7f47be9922312b68a4227fada96buzbee move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); 11911fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11921fd3346740dfb7f47be9922312b68a4227fada96buzbee info->num_arg_words = mir->ssa_rep->num_uses; 11931fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> 119483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, kArenaAllocMisc)); 11951fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < info->num_arg_words; i++) { 11961fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args[i] = GetRawSrc(mir, i); 11971fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11981fd3346740dfb7f47be9922312b68a4227fada96buzbee info->opt_flags = mir->optimization_flags; 11991fd3346740dfb7f47be9922312b68a4227fada96buzbee info->type = type; 12001fd3346740dfb7f47be9922312b68a4227fada96buzbee info->is_range = is_range; 12011fd3346740dfb7f47be9922312b68a4227fada96buzbee info->index = mir->dalvikInsn.vB; 12021fd3346740dfb7f47be9922312b68a4227fada96buzbee info->offset = mir->offset; 1203f096aad9203d7c50b2f9cbe1c1215a50c265a059Vladimir Marko info->mir = mir; 12041fd3346740dfb7f47be9922312b68a4227fada96buzbee return info; 12051fd3346740dfb7f47be9922312b68a4227fada96buzbee} 12061fd3346740dfb7f47be9922312b68a4227fada96buzbee 1207862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee// Allocate a new basic block. 12082ce745c06271d5223d57dbf08117b20d5b60694aBrian CarlstromBasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { 1209f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier BasicBlock* bb = static_cast<BasicBlock*>(arena_->Alloc(sizeof(BasicBlock), 121083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocBB)); 1211862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->block_type = block_type; 1212862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->id = block_id; 1213862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // TUNING: better estimate of the exit block predecessors? 12140d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, 1215df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom (block_type == kExitBlock) ? 2048 : 2, 1216df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom kGrowableArrayPredecessors); 12170d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->successor_block_list_type = kNotUsed; 1218862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_id_map_.Put(block_id, block_id); 1219862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return bb; 1220862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} 12211fd3346740dfb7f47be9922312b68a4227fada96buzbee 12224e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeConstantPropagation() { 12234e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); 122483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), kArenaAllocDFInfo)); 12254e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12264e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12274e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeMethodUses() { 12284e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler // The gate starts by initializing the use counts 12294e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler int num_ssa_regs = GetNumSSARegs(); 12304e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Resize(num_ssa_regs + 32); 12314e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Resize(num_ssa_regs + 32); 12324e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler // Initialize list 12334e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler for (int i = 0; i < num_ssa_regs; i++) { 12344e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Insert(0); 12354e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Insert(0); 12364e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler } 12374e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12384e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12394e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeSSATransformation() { 12404e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Compute the DFS order */ 12414e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDFSOrders(); 12424e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12434e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Compute the dominator info */ 12444e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDominators(); 12454e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12464e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Allocate data structures in preparation for SSA conversion */ 12474e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler CompilerInitializeSSAConversion(); 12484e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12494e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Find out the "Dalvik reg def x block" relation */ 12504e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDefBlockMatrix(); 12514e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12524e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Insert phi nodes to dominance frontiers for all variables */ 12534e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler InsertPhiNodes(); 12544e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12554e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Rename register names by local defs and phi nodes */ 12564e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ClearAllVisitedFlags(); 12574e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler DoDFSPreOrderSSARename(GetEntryBlock()); 12584e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12594e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12607934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom} // namespace art 1261