mir_graph.cc revision 2730db03beee4d6687ddfb5000c33c0370fbc6eb
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 176282dc12440a2072dc06a616160027ff21bd895eIan Rogers#include "base/stl_util.h" 18311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "compiler_internals.h" 19311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "dex_file-inl.h" 206282dc12440a2072dc06a616160027ff21bd895eIan Rogers#include "leb128.h" 216282dc12440a2072dc06a616160027ff21bd895eIan Rogers#include "mir_graph.h" 22311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 235816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_to_method_inliner_map.h" 245816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_method_inliner.h" 255816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 26311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeenamespace art { 27311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 28311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#define MAX_PATTERN_LEN 5 29311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 301fd3346740dfb7f47be9922312b68a4227fada96buzbeeconst char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { 311fd3346740dfb7f47be9922312b68a4227fada96buzbee "Phi", 321fd3346740dfb7f47be9922312b68a4227fada96buzbee "Copy", 331fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplFloat", 341fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgFloat", 351fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplDouble", 361fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgDouble", 371fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpLong", 381fd3346740dfb7f47be9922312b68a4227fada96buzbee "Nop", 391fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpNullCheck", 401fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpRangeCheck", 411fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpDivZeroCheck", 421fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check1", 431fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check2", 441fd3346740dfb7f47be9922312b68a4227fada96buzbee "Select", 451fd3346740dfb7f47be9922312b68a4227fada96buzbee}; 461fd3346740dfb7f47be9922312b68a4227fada96buzbee 47862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeMIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 481fd3346740dfb7f47be9922312b68a4227fada96buzbee : reg_location_(NULL), 49862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee compiler_temps_(arena, 6, kGrowableArrayMisc), 501fd3346740dfb7f47be9922312b68a4227fada96buzbee cu_(cu), 51311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_base_vregs_(NULL), 52311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_subscripts_(NULL), 53311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee vreg_to_ssa_map_(NULL), 54311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_last_defs_(NULL), 55311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee is_constant_v_(NULL), 56311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee constant_values_(NULL), 57862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee use_counts_(arena, 256, kGrowableArrayMisc), 58862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee raw_use_counts_(arena, 256, kGrowableArrayMisc), 59311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_reachable_blocks_(0), 60862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_(NULL), 61862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_(NULL), 62862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dom_post_order_traversal_(NULL), 63311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_(NULL), 64311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_block_matrix_(NULL), 65311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_block_v_(NULL), 66311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_dalvik_register_v_(NULL), 67311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_ssa_register_v_(NULL), 68862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_(arena, 100, kGrowableArrayBlockList), 69311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee try_block_addr_(NULL), 70311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee entry_block_(NULL), 71311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee exit_block_(NULL), 72311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_blocks_(0), 73311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_(NULL), 74b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), 75311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_(kInvalidEntry), 76311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_(kInvalidEntry), 77311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_(0), 78311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_(NULL), 791fd3346740dfb7f47be9922312b68a4227fada96buzbee num_ssa_regs_(0), 801fd3346740dfb7f47be9922312b68a4227fada96buzbee method_sreg_(0), 81862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. 82862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee checkstats_(NULL), 83b48819db07f9a0992a72173380c24249d7fc648abuzbee arena_(arena), 84b48819db07f9a0992a72173380c24249d7fc648abuzbee backward_branches_(0), 85b48819db07f9a0992a72173380c24249d7fc648abuzbee forward_branches_(0) { 86862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); 87311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 88311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 896282dc12440a2072dc06a616160027ff21bd895eIan RogersMIRGraph::~MIRGraph() { 906282dc12440a2072dc06a616160027ff21bd895eIan Rogers STLDeleteElements(&m_units_); 916282dc12440a2072dc06a616160027ff21bd895eIan Rogers} 926282dc12440a2072dc06a616160027ff21bd895eIan Rogers 93311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 94311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Parse an instruction, return the length of the instruction 95311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 962ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromint MIRGraph::ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction) { 97311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const Instruction* instruction = Instruction::At(code_ptr); 98311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *decoded_instruction = DecodedInstruction(instruction); 99311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 100311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return instruction->SizeInCodeUnits(); 101311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 102311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 103311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 104311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Split an existing block from the specified code offset into two */ 1050d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, 1062ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { 1070d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_GT(code_offset, orig_block->start_offset); 108311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MIR* insn = orig_block->first_mir_insn; 1090d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee MIR* prev = NULL; 110311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (insn) { 111311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->offset == code_offset) break; 1120d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee prev = insn; 113311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn = insn->next; 114311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 115311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn == NULL) { 116311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Break split failed"; 117311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 118862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); 119862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bottom_block); 120311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 121311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->start_offset = code_offset; 122311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->first_mir_insn = insn; 123311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->last_mir_insn = orig_block->last_mir_insn; 124311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 125311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* If this block was terminated by a return, the flag needs to go with the bottom block */ 126311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->terminated_by_return = orig_block->terminated_by_return; 127311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->terminated_by_return = false; 128311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 129311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the taken path */ 130311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->taken = orig_block->taken; 1310d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->taken != NullBasicBlockId) { 1320d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->taken = NullBasicBlockId; 1330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); 1340d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Delete(orig_block->id); 1350d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Insert(bottom_block->id); 136311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 137311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 138311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the fallthrough path */ 139311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->fall_through = orig_block->fall_through; 1400d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->fall_through = bottom_block->id; 1410d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->predecessors->Insert(orig_block->id); 1420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->fall_through != NullBasicBlockId) { 1430d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); 1440d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Delete(orig_block->id); 1450d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Insert(bottom_block->id); 146311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 147311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 148311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the successor list */ 1490d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (orig_block->successor_block_list_type != kNotUsed) { 1500d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_block_list_type = orig_block->successor_block_list_type; 1510d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_blocks = orig_block->successor_blocks; 1520d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->successor_block_list_type = kNotUsed; 1530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->successor_blocks = NULL; 1540d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); 155311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 156862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 157311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 1580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock *bb = GetBasicBlock(successor_block_info->block); 1590d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors->Delete(orig_block->id); 1600d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors->Insert(bottom_block->id); 161311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 162311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 163311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 1640d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->last_mir_insn = prev; 1650d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee prev->next = NULL; 166311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 167311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 168311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Update the immediate predecessor block pointer so that outgoing edges 169311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * can be applied to the proper block. 170311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 171311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (immed_pred_block_p) { 172311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(*immed_pred_block_p, orig_block); 173311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *immed_pred_block_p = bottom_block; 174311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 175b48819db07f9a0992a72173380c24249d7fc648abuzbee 176b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate dex instructions in the bottom block with the new container. 1774376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != nullptr); 1784376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != orig_block->first_mir_insn); 1794376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn == bottom_block->first_mir_insn); 1804376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(insn->offset, bottom_block->start_offset); 1814376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || 1824376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko !IsPseudoMirOp(insn->dalvikInsn.opcode)); 1834376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); 1844376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko MIR* p = insn; 1854376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 1864376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko while (p != bottom_block->last_mir_insn) { 1874376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko p = p->next; 1884376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(p != nullptr); 189b48819db07f9a0992a72173380c24249d7fc648abuzbee int opcode = p->dalvikInsn.opcode; 190b48819db07f9a0992a72173380c24249d7fc648abuzbee /* 191b48819db07f9a0992a72173380c24249d7fc648abuzbee * Some messiness here to ensure that we only enter real opcodes and only the 192b48819db07f9a0992a72173380c24249d7fc648abuzbee * first half of a potentially throwing instruction that has been split into 1934376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * CHECK and work portions. Since the 2nd half of a split operation is always 1944376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * the first in a BasicBlock, we can't hit it here. 195b48819db07f9a0992a72173380c24249d7fc648abuzbee */ 1964376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko if ((opcode == kMirOpCheck) || !IsPseudoMirOp(opcode)) { 1974376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); 198b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 199b48819db07f9a0992a72173380c24249d7fc648abuzbee } 200b48819db07f9a0992a72173380c24249d7fc648abuzbee } 201b48819db07f9a0992a72173380c24249d7fc648abuzbee 202311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bottom_block; 203311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 204311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 205311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 206311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Given a code offset, find out the block that starts with it. If the offset 207311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is in the middle of an existing block, split it into two. If immed_pred_block_p 208311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is not non-null and is the block being split, update *immed_pred_block_p to 209311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * point to the bottom block so that outgoing edges can be set up properly 210311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (by the caller) 211311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Utilizes a map for fast lookup of the typical cases. 212311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 2130d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, 2142ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock** immed_pred_block_p) { 215bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee if (code_offset >= cu_->code_item->insns_size_in_code_units_) { 216311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return NULL; 217311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 218b48819db07f9a0992a72173380c24249d7fc648abuzbee 219b48819db07f9a0992a72173380c24249d7fc648abuzbee int block_id = dex_pc_to_block_map_.Get(code_offset); 220b48819db07f9a0992a72173380c24249d7fc648abuzbee BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); 221b48819db07f9a0992a72173380c24249d7fc648abuzbee 222b48819db07f9a0992a72173380c24249d7fc648abuzbee if ((bb != NULL) && (bb->start_offset == code_offset)) { 223b48819db07f9a0992a72173380c24249d7fc648abuzbee // Does this containing block start with the desired instruction? 224bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee return bb; 225bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee } 226311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 227b48819db07f9a0992a72173380c24249d7fc648abuzbee // No direct hit. 228b48819db07f9a0992a72173380c24249d7fc648abuzbee if (!create) { 229b48819db07f9a0992a72173380c24249d7fc648abuzbee return NULL; 230b48819db07f9a0992a72173380c24249d7fc648abuzbee } 231b48819db07f9a0992a72173380c24249d7fc648abuzbee 232b48819db07f9a0992a72173380c24249d7fc648abuzbee if (bb != NULL) { 233b48819db07f9a0992a72173380c24249d7fc648abuzbee // The target exists somewhere in an existing block. 234b48819db07f9a0992a72173380c24249d7fc648abuzbee return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : NULL); 235311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 236311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 237b48819db07f9a0992a72173380c24249d7fc648abuzbee // Create a new block. 238862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = NewMemBB(kDalvikByteCode, num_blocks_++); 239862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bb); 240311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset = code_offset; 241b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(bb->start_offset, bb->id); 242311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bb; 243311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 244311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 245b48819db07f9a0992a72173380c24249d7fc648abuzbee 246311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Identify code range in try blocks and set up the empty catch blocks */ 2472ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ProcessTryCatchBlocks() { 248311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int tries_size = current_code_item_->tries_size_; 2490d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset offset; 250311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 251311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (tries_size == 0) { 252311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 253311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 254311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 255311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < tries_size; i++) { 256311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const DexFile::TryItem* pTry = 257311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DexFile::GetTryItems(*current_code_item_, i); 2580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset start_offset = pTry->start_addr_; 2590d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset end_offset = start_offset + pTry->insn_count_; 260311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (offset = start_offset; offset < end_offset; offset++) { 261862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(offset); 262311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 263311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 264311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 265311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Iterate over each of the handlers to enqueue the empty Catch blocks 266311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); 267311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 268311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (uint32_t idx = 0; idx < handlers_size; idx++) { 269311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(handlers_ptr); 270311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (; iterator.HasNext(); iterator.Next()) { 271311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t address = iterator.GetHandlerAddress(); 272311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(address, false /* split */, true /*create*/, 273311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 274311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 275311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee handlers_ptr = iterator.EndDataPointer(); 276311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 277311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 278311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 279311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kBranch flag */ 2800d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 2810d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, const uint16_t* code_ptr, 2822ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_end) { 2830d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset target = cur_offset; 284311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee switch (insn->dalvikInsn.opcode) { 285311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO: 286311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_16: 287311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_32: 288311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vA; 289311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 290311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQ: 291311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NE: 292311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LT: 293311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GE: 294311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GT: 295311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LE: 296311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 297311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vC; 298311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 299311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQZ: 300311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NEZ: 301311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LTZ: 302311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GEZ: 303311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GTZ: 304311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LEZ: 305311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 306311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vB; 307311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 308311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee default: 309311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; 310311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 311b48819db07f9a0992a72173380c24249d7fc648abuzbee CountBranch(target); 312311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *taken_block = FindBlock(target, /* split */ true, /* create */ true, 313311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ &cur_block); 3140d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = taken_block->id; 3150d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee taken_block->predecessors->Insert(cur_block->id); 316311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 317311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Always terminate the current block for conditional branches */ 318311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kContinue) { 319311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *fallthrough_block = FindBlock(cur_offset + width, 320311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 321311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * If the method is processed 322311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * in sequential order from the 323311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * beginning, we don't need to 324311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * specify split for continue 325311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * blocks. However, this 326311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * routine can be called by 327311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * compileLoop, which starts 328311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * parsing the method from an 329311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * arbitrary address in the 330311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * method body. 331311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 332311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 333311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ 334311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 335311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ 336311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee &cur_block); 3370d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 3380d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 339311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (code_ptr < code_end) { 3402724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 341311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 342311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 343311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 344311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 345311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 346311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kSwitch flag */ 34717189ac098b2f156713db1821b49db7b2f018bbebuzbeeBasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 34817189ac098b2f156713db1821b49db7b2f018bbebuzbee int width, int flags) { 349311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* switch_data = 350311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); 351311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int size; 352311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* keyTable; 353311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* target_table; 354311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int i; 355311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int first_key; 356311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 357311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 358311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Packed switch data format: 359311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0100 magic value 360311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table 361311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int first_key first (and lowest) switch case value 362311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 363311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 364311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (4+size*2) 16-bit code units. 365311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 366311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { 367311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 368311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kPackedSwitchSignature)); 369311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 370311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = switch_data[2] | (switch_data[3] << 16); 371311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[4]); 372311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = NULL; // Make the compiler happy 373311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 374311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Sparse switch data format: 375311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0200 magic value 376311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table; > 0 377311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int keys[size] keys, sorted low-to-high; 32-bit aligned 378311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 379311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 380311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (2+size*4) 16-bit code units. 381311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 382311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 383311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 384311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kSparseSwitchSignature)); 385311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 386311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = reinterpret_cast<const int*>(&switch_data[2]); 387311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); 388311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = 0; // To make the compiler happy 389311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 390311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 3910d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 392311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 3930d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 394311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 3950d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_block_list_type = 3960d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; 3970d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks = 398df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); 399311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 400311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (i = 0; i < size; i++) { 401311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *case_block = FindBlock(cur_offset + target_table[i], /* split */ true, 402311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ true, /* immed_pred_block_p */ &cur_block); 403311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = 404f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), 405f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocSuccessor)); 4060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = case_block->id; 407311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = 408311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 409311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key + i : keyTable[i]; 4100d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 4110d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee case_block->predecessors->Insert(cur_block->id); 412311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 413311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 414311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Fall-through case */ 415df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, 416df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom /* create */ true, /* immed_pred_block_p */ NULL); 4170d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 4180d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 41917189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 420311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 421311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 422311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kThrow flag */ 4230d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 4240d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, ArenaBitVector* try_block_addr, 4252ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_ptr, const uint16_t* code_end) { 426862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool in_try_block = try_block_addr->IsBitSet(cur_offset); 42717189ac098b2f156713db1821b49db7b2f018bbebuzbee bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); 42817189ac098b2f156713db1821b49db7b2f018bbebuzbee bool build_all_edges = 42917189ac098b2f156713db1821b49db7b2f018bbebuzbee (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; 430311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 431311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* In try block */ 432311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (in_try_block) { 433311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(*current_code_item_, cur_offset); 434311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4350d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 436311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 437311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 4380d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 439311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 440311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4410d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_block_list_type = kCatch; 4420d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks = 443862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, 2, kGrowableArraySuccessorBlocks); 444311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 44502c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom for (; iterator.HasNext(); iterator.Next()) { 446311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, 447311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false /* creat */, NULL /* immed_pred_block_p */); 448311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catch_block->catch_entry = true; 449311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (kIsDebugBuild) { 450311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catches_.insert(catch_block->start_offset); 451311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 452311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 453f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier (arena_->Alloc(sizeof(SuccessorBlockInfo), ArenaAllocator::kAllocSuccessor)); 4540d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = catch_block->id; 455311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = iterator.GetHandlerTypeIndex(); 4560d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 4570d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee catch_block->predecessors->Insert(cur_block->id); 458311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 45917189ac098b2f156713db1821b49db7b2f018bbebuzbee } else if (build_all_edges) { 460862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *eh_block = NewMemBB(kExceptionHandling, num_blocks_++); 4610d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = eh_block->id; 462862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(eh_block); 463311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee eh_block->start_offset = cur_offset; 4640d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee eh_block->predecessors->Insert(cur_block->id); 465311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 466311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 46717189ac098b2f156713db1821b49db7b2f018bbebuzbee if (is_throw) { 468311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->explicit_throw = true; 4692724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (code_ptr < code_end) { 470311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Force creation of new block following THROW via side-effect 471311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 472311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 473311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 474311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (!in_try_block) { 475311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Don't split a THROW that can't rethrow - we're done. 476311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 477311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 478311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 479311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 48017189ac098b2f156713db1821b49db7b2f018bbebuzbee if (!build_all_edges) { 48117189ac098b2f156713db1821b49db7b2f018bbebuzbee /* 48217189ac098b2f156713db1821b49db7b2f018bbebuzbee * Even though there is an exception edge here, control cannot return to this 48317189ac098b2f156713db1821b49db7b2f018bbebuzbee * method. Thus, for the purposes of dataflow analysis and optimization, we can 48417189ac098b2f156713db1821b49db7b2f018bbebuzbee * ignore the edge. Doing this reduces compile time, and increases the scope 48517189ac098b2f156713db1821b49db7b2f018bbebuzbee * of the basic-block level optimization pass. 48617189ac098b2f156713db1821b49db7b2f018bbebuzbee */ 48717189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 48817189ac098b2f156713db1821b49db7b2f018bbebuzbee } 48917189ac098b2f156713db1821b49db7b2f018bbebuzbee 490311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 491311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Split the potentially-throwing instruction into two parts. 492311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The first half will be a pseudo-op that captures the exception 493311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * edges and terminates the basic block. It always falls through. 494311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Then, create a new basic block that begins with the throwing instruction 495311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (minus exceptions). Note: this new basic block must NOT be entered into 496311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the block_map. If the potentially-throwing instruction is the target of a 497311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * future branch, we need to find the check psuedo half. The new 498311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * basic block containing the work portion of the instruction should 499311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * only be entered via fallthrough from the block containing the 500311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * pseudo exception edge MIR. Note also that this new block is 501311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * not automatically terminated after the work portion, and may 502311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * contain following instructions. 503b48819db07f9a0992a72173380c24249d7fc648abuzbee * 504b48819db07f9a0992a72173380c24249d7fc648abuzbee * Note also that the dex_pc_to_block_map_ entry for the potentially 505b48819db07f9a0992a72173380c24249d7fc648abuzbee * throwing instruction will refer to the original basic block. 506311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 507862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *new_block = NewMemBB(kDalvikByteCode, num_blocks_++); 508862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(new_block); 509311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee new_block->start_offset = insn->offset; 5100d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = new_block->id; 5110d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee new_block->predecessors->Insert(cur_block->id); 512f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier MIR* new_insn = static_cast<MIR*>(arena_->Alloc(sizeof(MIR), ArenaAllocator::kAllocMIR)); 513311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *new_insn = *insn; 514311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->dalvikInsn.opcode = 515311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<Instruction::Code>(kMirOpCheck); 516311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Associate the two halves 517311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->meta.throw_insn = new_insn; 518311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee AppendMIR(new_block, new_insn); 519311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return new_block; 520311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 521311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 522311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ 523311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 5248b2c0b9abc3f520495f4387ea040132ba85cae69Ian Rogers InvokeType invoke_type, uint16_t class_def_idx, 5252ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { 526311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_ = code_item; 527311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee method_stack_.push_back(std::make_pair(current_method_, current_offset_)); 528311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_ = m_units_.size(); 529311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ = 0; 530311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: will need to snapshot stack image and use that as the mir context identification. 531311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), 5322730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko dex_file, current_code_item_, class_def_idx, method_idx, access_flags, 5332730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); 534311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_ptr = current_code_item_->insns_; 535311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_end = 536311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; 537311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 538311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: need to rework expansion of block list & try_block_addr when inlining activated. 539b48819db07f9a0992a72173380c24249d7fc648abuzbee // TUNING: use better estimate of basic blocks for following resize. 540862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); 541b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_); 542bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee 543311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: replace with explicit resize routine. Using automatic extension side effect for now. 544862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); 545862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); 546311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 547311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // If this is the first method, set up default entry and exit blocks. 548311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (current_method_ == 0) { 549311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(entry_block_ == NULL); 550311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(exit_block_ == NULL); 5514274889d48ef82369bf2c1ca70d84689b4f9e93aBrian Carlstrom DCHECK_EQ(num_blocks_, 0); 5520d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Use id 0 to represent a null block. 5530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); 5540d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(null_block->id, NullBasicBlockId); 5550d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee null_block->hidden = true; 5560d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee block_list_.Insert(null_block); 557862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); 558862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(entry_block_); 5590d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_ = NewMemBB(kExitBlock, num_blocks_++); 560862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(exit_block_); 561311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. 562311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->dex_file = &dex_file; 563311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->class_def_idx = class_def_idx; 564311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->method_idx = method_idx; 565311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->access_flags = access_flags; 566311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->invoke_type = invoke_type; 567311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); 568311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_ins = current_code_item_->ins_size_; 569311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_regs = current_code_item_->registers_size_ - cu_->num_ins; 570311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_outs = current_code_item_->outs_size_; 571311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_dalvik_registers = current_code_item_->registers_size_; 572311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->insns = current_code_item_->insns_; 573311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->code_item = current_code_item_; 574311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 575311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; 576311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 577311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Will need to manage storage for ins & outs, push prevous state and update 578311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * insert point. 579311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 580311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 581311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 582311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Current block to record parsed instructions */ 583862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); 5840d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(current_offset_, 0U); 585311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->start_offset = current_offset_; 586862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(cur_block); 5870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, insert at the insert point rather than entry block. 5880d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee entry_block_->fall_through = cur_block->id; 5890d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->predecessors->Insert(entry_block_->id); 590311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 591311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Identify code range in try blocks and set up the empty catch blocks */ 592311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ProcessTryCatchBlocks(); 593311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 594311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Parse all instructions and put them into containing basic blocks */ 595311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (code_ptr < code_end) { 596f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier MIR *insn = static_cast<MIR *>(arena_->Alloc(sizeof(MIR), ArenaAllocator::kAllocMIR)); 597311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->offset = current_offset_; 598311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->m_unit_index = current_method_; 599311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int width = ParseInsn(code_ptr, &insn->dalvikInsn); 600311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->width = width; 601311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee Instruction::Code opcode = insn->dalvikInsn.opcode; 602311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_ != NULL) { 603311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_[static_cast<int>(opcode)]++; 604311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 605311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 606311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int flags = Instruction::FlagsOf(insn->dalvikInsn.opcode); 607311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6081da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee uint64_t df_flags = oat_data_flow_attributes_[insn->dalvikInsn.opcode]; 609311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 610311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (df_flags & DF_HAS_DEFS) { 611311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; 612311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 613311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6141da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee if (df_flags & DF_LVN) { 6151da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee cur_block->use_lvn = true; // Run local value numbering on this basic block. 6161da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee } 6171da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee 6182724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Check for inline data block signatures 6192724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (opcode == Instruction::NOP) { 6202724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. 6212724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { 6222724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. 6232724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee uint16_t following_raw_instruction = code_ptr[1]; 6242724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || 6252724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kPackedSwitchSignature) || 6262724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kArrayDataSignature)) { 6272724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); 6282724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6292724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6302724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (width == 1) { 6312724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // It is a simple nop - treat normally. 6322724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee AppendMIR(cur_block, insn); 6332724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 6340d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId); 6350d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->taken == NullBasicBlockId); 6362724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Unreachable instruction, mark for no continuation. 6372724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee flags &= ~Instruction::kContinue; 6382724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6392724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 6402724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee AppendMIR(cur_block, insn); 6412724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 6422724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 643b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate the starting dex_pc for this opcode with its containing basic block. 644b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(insn->offset, cur_block->id); 645b48819db07f9a0992a72173380c24249d7fc648abuzbee 6462724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee code_ptr += width; 6472724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 648311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kBranch) { 649311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanBranch(cur_block, insn, current_offset_, 650311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee width, flags, code_ptr, code_end); 651311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kReturn) { 652311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->terminated_by_return = true; 6530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = exit_block_->id; 6540d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_->predecessors->Insert(cur_block->id); 655311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 656311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Terminate the current block if there are instructions 657311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * afterwards. 658311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 659311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (code_ptr < code_end) { 660311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 661311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Create a fallthrough block for real instructions 662311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (incl. NOP). 663311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 6642724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(current_offset_ + width, /* split */ false, /* create */ true, 6652724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee /* immed_pred_block_p */ NULL); 666311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 667311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kThrow) { 668311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, 669311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee code_ptr, code_end); 670311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kSwitch) { 67117189ac098b2f156713db1821b49db7b2f018bbebuzbee cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); 672311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 673311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ += width; 674311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *next_block = FindBlock(current_offset_, /* split */ false, /* create */ 675311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false, /* immed_pred_block_p */ NULL); 676311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (next_block) { 677311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 678311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The next instruction could be the target of a previously parsed 679311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * forward branch so a block is already created. If the current 680311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * instruction is not an unconditional branch, connect them through 681311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the fall-through link. 682311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 6830d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId || 6840d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == next_block || 6850d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == exit_block_); 686311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { 6880d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = next_block->id; 6890d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee next_block->predecessors->Insert(cur_block->id); 690311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 691311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = next_block; 692311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 693311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 6945816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 695311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 696311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DumpCFG("/sdcard/1_post_parse_cfg/", true); 697311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 698311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 699311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 7001fd3346740dfb7f47be9922312b68a4227fada96buzbee DumpMIRGraph(); 701311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 702311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 703311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7042ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ShowOpcodeStats() { 705311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(opcode_count_ != NULL); 706311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "Opcode Count"; 707311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < kNumPackedOpcodes; i++) { 708311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_[i] != 0) { 709311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) 710311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee << " " << opcode_count_[i]; 711311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 712311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 713311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 714311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 715311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee// TODO: use a configurable base prefix, and adjust callers to supply pass name. 716311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Dump the CFG into a DOT graph */ 717d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beylervoid MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { 718311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FILE* file; 719311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); 720311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ReplaceSpecialChars(fname); 721d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler fname = StringPrintf("%s%s%x%s.dot", dir_prefix, fname.c_str(), 722d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, 723d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler suffix == nullptr ? "" : suffix); 724311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee file = fopen(fname.c_str(), "w"); 725311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (file == NULL) { 726311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 727311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 728311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "digraph G {\n"); 729311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 730311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " rankdir=TB\n"); 731311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 732311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; 733311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int idx; 734311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 735311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (idx = 0; idx < num_blocks; idx++) { 736862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int block_idx = all_blocks ? idx : dfs_order_->Get(idx); 737311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *bb = GetBasicBlock(block_idx); 738311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb == NULL) break; 739311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kDead) continue; 740311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kEntryBlock) { 741311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); 742311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExitBlock) { 743311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); 744311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kDalvikByteCode) { 745311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", 746311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id); 747311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const MIR *mir; 748311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 749311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->first_mir_insn ? " | " : " "); 750311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (mir = bb->first_mir_insn; mir; mir = mir->next) { 751311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int opcode = mir->dalvikInsn.opcode; 752311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {%04x %s %s %s\\l}%s\\\n", mir->offset, 7531fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->ssa_rep ? GetDalvikDisassembly(mir) : 754311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (opcode < kMirOpFirst) ? Instruction::Name(mir->dalvikInsn.opcode) : 7551fd3346740dfb7f47be9922312b68a4227fada96buzbee extended_mir_op_names_[opcode - kMirOpFirst], 756311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", 757311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", 758311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee mir->next ? " | " : " "); 759311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 760311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 761311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExceptionHandling) { 762311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name[BLOCK_NAME_LEN]; 763311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 764311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name); 765311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s [shape=invhouse];\n", block_name); 766311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 767311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 768311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 769311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7700d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 771311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 7720d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->taken), block_name2); 773311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n [style=dotted]\n", 774311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name2); 775311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 7760d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 777311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 7780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->fall_through), block_name2); 779311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); 780311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 781311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7820d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type != kNotUsed) { 783311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", 784311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id, 7850d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); 7860d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 787862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 788311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 789311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int succ_id = 0; 790311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 791311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 792311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7930d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock *dest_block = GetBasicBlock(successor_block_info->block); 794862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *next_successor_block_info = iterator.Next(); 795311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 796311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 797311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id++, 798311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key, 799311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee dest_block->start_offset, 800311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (next_successor_block_info != NULL) ? " | " : " "); 801311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 802311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info = next_successor_block_info; 803311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 804311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 805311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 806311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 807311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", 808311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, bb->start_offset, bb->id); 809311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8100d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type == kPackedSwitch || 8110d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->successor_block_list_type == kSparseSwitch) { 8120d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); 813311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 814311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id = 0; 815311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 816862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iter.Next(); 817311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 818311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8190d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 820311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 821311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(dest_block, block_name2); 822311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, 823311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->id, succ_id++, block_name2); 824311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 825311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 826311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 827311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "\n"); 828311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 829311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 830311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Display the dominator tree */ 831311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 832311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 833311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name1); 834311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->i_dom) { 8350d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->i_dom), block_name2); 836311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); 837311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 838311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 839311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 840311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "}\n"); 841311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fclose(file); 842311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 843311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8441fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the end of a basic block */ 8452ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::AppendMIR(BasicBlock* bb, MIR* mir) { 8461fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->first_mir_insn == NULL) { 8471fd3346740dfb7f47be9922312b68a4227fada96buzbee DCHECK(bb->last_mir_insn == NULL); 8481fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = bb->first_mir_insn = mir; 8490d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee mir->next = NULL; 8501fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 8511fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn->next = mir; 8521fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->next = NULL; 8531fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = mir; 8541fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8551fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8561fd3346740dfb7f47be9922312b68a4227fada96buzbee 8571fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the head of a basic block */ 8582ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::PrependMIR(BasicBlock* bb, MIR* mir) { 8591fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->first_mir_insn == NULL) { 8601fd3346740dfb7f47be9922312b68a4227fada96buzbee DCHECK(bb->last_mir_insn == NULL); 8611fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = bb->first_mir_insn = mir; 8620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee mir->next = NULL; 8631fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 8641fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->next = bb->first_mir_insn; 8651fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->first_mir_insn = mir; 8661fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8671fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8681fd3346740dfb7f47be9922312b68a4227fada96buzbee 8691fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert a MIR instruction after the specified MIR */ 8702ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir) { 8711fd3346740dfb7f47be9922312b68a4227fada96buzbee new_mir->next = current_mir->next; 8721fd3346740dfb7f47be9922312b68a4227fada96buzbee current_mir->next = new_mir; 8731fd3346740dfb7f47be9922312b68a4227fada96buzbee 8740d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->last_mir_insn == current_mir) { 8751fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Is the last MIR in the block */ 8761fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = new_mir; 8771fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8781fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8791fd3346740dfb7f47be9922312b68a4227fada96buzbee 8802ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromchar* MIRGraph::GetDalvikDisassembly(const MIR* mir) { 8811fd3346740dfb7f47be9922312b68a4227fada96buzbee DecodedInstruction insn = mir->dalvikInsn; 8821fd3346740dfb7f47be9922312b68a4227fada96buzbee std::string str; 8831fd3346740dfb7f47be9922312b68a4227fada96buzbee int flags = 0; 8841fd3346740dfb7f47be9922312b68a4227fada96buzbee int opcode = insn.opcode; 8851fd3346740dfb7f47be9922312b68a4227fada96buzbee char* ret; 8861fd3346740dfb7f47be9922312b68a4227fada96buzbee bool nop = false; 8871fd3346740dfb7f47be9922312b68a4227fada96buzbee SSARepresentation* ssa_rep = mir->ssa_rep; 8881fd3346740dfb7f47be9922312b68a4227fada96buzbee Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format 8891fd3346740dfb7f47be9922312b68a4227fada96buzbee int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; 8901fd3346740dfb7f47be9922312b68a4227fada96buzbee int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; 8911fd3346740dfb7f47be9922312b68a4227fada96buzbee 8921fd3346740dfb7f47be9922312b68a4227fada96buzbee // Handle special cases. 8931fd3346740dfb7f47be9922312b68a4227fada96buzbee if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { 8941fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 8951fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(": "); 8961fd3346740dfb7f47be9922312b68a4227fada96buzbee // Recover the original Dex instruction 8971fd3346740dfb7f47be9922312b68a4227fada96buzbee insn = mir->meta.throw_insn->dalvikInsn; 8981fd3346740dfb7f47be9922312b68a4227fada96buzbee ssa_rep = mir->meta.throw_insn->ssa_rep; 8991fd3346740dfb7f47be9922312b68a4227fada96buzbee defs = ssa_rep->num_defs; 9001fd3346740dfb7f47be9922312b68a4227fada96buzbee uses = ssa_rep->num_uses; 9011fd3346740dfb7f47be9922312b68a4227fada96buzbee opcode = insn.opcode; 9021fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if (opcode == kMirOpNop) { 9031fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("["); 9040d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Recover original opcode. 9050d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); 9060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee opcode = insn.opcode; 9071fd3346740dfb7f47be9922312b68a4227fada96buzbee nop = true; 9081fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9091fd3346740dfb7f47be9922312b68a4227fada96buzbee 9101fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode >= kMirOpFirst) { 9111fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 9121fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 9131fd3346740dfb7f47be9922312b68a4227fada96buzbee dalvik_format = Instruction::FormatOf(insn.opcode); 9141fd3346740dfb7f47be9922312b68a4227fada96buzbee flags = Instruction::FlagsOf(insn.opcode); 9151fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(Instruction::Name(insn.opcode)); 9161fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9171fd3346740dfb7f47be9922312b68a4227fada96buzbee 9181fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode == kMirOpPhi) { 9190d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlockId* incoming = mir->meta.phi_incoming; 9201fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s = (%s", 9211fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), 9221fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); 923b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom str.append(StringPrintf(":%d", incoming[0])); 9241fd3346740dfb7f47be9922312b68a4227fada96buzbee int i; 9251fd3346740dfb7f47be9922312b68a4227fada96buzbee for (i = 1; i < uses; i++) { 9261fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", %s:%d", 9271fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), 9281fd3346740dfb7f47be9922312b68a4227fada96buzbee incoming[i])); 9291fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9301fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(")"); 9311fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if ((flags & Instruction::kBranch) != 0) { 9321fd3346740dfb7f47be9922312b68a4227fada96buzbee // For branches, decode the instructions to print out the branch targets. 9331fd3346740dfb7f47be9922312b68a4227fada96buzbee int offset = 0; 9341fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 9351fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21t: 9361fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 9371fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vB; 9381fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9391fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22t: 9401fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), 9411fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); 9421fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vC; 9431fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9441fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k10t: 9451fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k20t: 9461fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k30t: 9471fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vA; 9481fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9491fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 9501fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; 9511fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9521fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset, 9531fd3346740dfb7f47be9922312b68a4227fada96buzbee offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); 9541fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 9551fd3346740dfb7f47be9922312b68a4227fada96buzbee // For invokes-style formats, treat wide regs as a pair of singles 9561fd3346740dfb7f47be9922312b68a4227fada96buzbee bool show_singles = ((dalvik_format == Instruction::k35c) || 9571fd3346740dfb7f47be9922312b68a4227fada96buzbee (dalvik_format == Instruction::k3rc)); 9581fd3346740dfb7f47be9922312b68a4227fada96buzbee if (defs != 0) { 9591fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s", GetSSANameWithConst(ssa_rep->defs[0], false).c_str())); 9601fd3346740dfb7f47be9922312b68a4227fada96buzbee if (uses != 0) { 9611fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(", "); 9621fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9631fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9641fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < uses; i++) { 9651fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append( 9661fd3346740dfb7f47be9922312b68a4227fada96buzbee StringPrintf(" %s", GetSSANameWithConst(ssa_rep->uses[i], show_singles).c_str())); 9671fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { 9681fd3346740dfb7f47be9922312b68a4227fada96buzbee // For the listing, skip the high sreg. 9691fd3346740dfb7f47be9922312b68a4227fada96buzbee i++; 9701fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9711fd3346740dfb7f47be9922312b68a4227fada96buzbee if (i != (uses -1)) { 9721fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(","); 9731fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9741fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9751fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 9767934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k11n: // Add one immediate from vB 9771fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21s: 9781fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31i: 9791fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21h: 9801fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vB)); 9811fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9827934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k51l: // Add one wide immediate 98323b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); 9841fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9857934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k21c: // One register, one string/type/method index 9861fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31c: 9871fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vB)); 9881fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9897934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k22c: // Two registers, one string/type/method index 9901fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vC)); 9911fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9927934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom case Instruction::k22s: // Add one immediate from vC 9931fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22b: 9941fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vC)); 9951fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 99602c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom default: { 99702c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom // Nothing left to print 9981fd3346740dfb7f47be9922312b68a4227fada96buzbee } 99902c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom } 10001fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10011fd3346740dfb7f47be9922312b68a4227fada96buzbee if (nop) { 10021fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("]--optimized away"); 10031fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10041fd3346740dfb7f47be9922312b68a4227fada96buzbee int length = str.length() + 1; 1005f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ret = static_cast<char*>(arena_->Alloc(length, ArenaAllocator::kAllocDFInfo)); 10061fd3346740dfb7f47be9922312b68a4227fada96buzbee strncpy(ret, str.c_str(), length); 10071fd3346740dfb7f47be9922312b68a4227fada96buzbee return ret; 10081fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10091fd3346740dfb7f47be9922312b68a4227fada96buzbee 10101fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Turn method name into a legal Linux file name */ 10112ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ReplaceSpecialChars(std::string& str) { 10129b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static const struct { const char before; const char after; } match[] = { 10139b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, 10149b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} 10159b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom }; 10161fd3346740dfb7f47be9922312b68a4227fada96buzbee for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { 10171fd3346740dfb7f47be9922312b68a4227fada96buzbee std::replace(str.begin(), str.end(), match[i].before, match[i].after); 10181fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10191fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10201fd3346740dfb7f47be9922312b68a4227fada96buzbee 10212ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSAName(int ssa_reg) { 102239ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to 102339ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // the arena. We should be smarter and just place straight into the arena, or compute the 102439ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // value more lazily. 10251fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 10261fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10271fd3346740dfb7f47be9922312b68a4227fada96buzbee 10281fd3346740dfb7f47be9922312b68a4227fada96buzbee// Similar to GetSSAName, but if ssa name represents an immediate show that as well. 10292ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { 10301fd3346740dfb7f47be9922312b68a4227fada96buzbee if (reg_location_ == NULL) { 10311fd3346740dfb7f47be9922312b68a4227fada96buzbee // Pre-SSA - just use the standard name 10321fd3346740dfb7f47be9922312b68a4227fada96buzbee return GetSSAName(ssa_reg); 10331fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10341fd3346740dfb7f47be9922312b68a4227fada96buzbee if (IsConst(reg_location_[ssa_reg])) { 10351fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!singles_only && reg_location_[ssa_reg].wide) { 103623b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 10371fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValueWide(reg_location_[ssa_reg])); 10381fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 1039b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 10401fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValue(reg_location_[ssa_reg])); 10411fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10421fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 10431fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 10441fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10451fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10461fd3346740dfb7f47be9922312b68a4227fada96buzbee 10472ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::GetBlockName(BasicBlock* bb, char* name) { 10481fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (bb->block_type) { 10491fd3346740dfb7f47be9922312b68a4227fada96buzbee case kEntryBlock: 10501fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); 10511fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10521fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExitBlock: 10531fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); 10541fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10551fd3346740dfb7f47be9922312b68a4227fada96buzbee case kDalvikByteCode: 10561fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); 10571fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10581fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExceptionHandling: 10591fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, 10601fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id); 10611fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10621fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 10631fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); 10641fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10651fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10661fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10671fd3346740dfb7f47be9922312b68a4227fada96buzbee 10682ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromconst char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { 10690d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, use current code unit. 10701fd3346740dfb7f47be9922312b68a4227fada96buzbee const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); 10711fd3346740dfb7f47be9922312b68a4227fada96buzbee return cu_->dex_file->GetShorty(method_id.proto_idx_); 10721fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10731fd3346740dfb7f47be9922312b68a4227fada96buzbee 10741fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Debug Utility - dump a compilation unit */ 10752ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DumpMIRGraph() { 10761fd3346740dfb7f47be9922312b68a4227fada96buzbee BasicBlock* bb; 10771fd3346740dfb7f47be9922312b68a4227fada96buzbee const char* block_type_names[] = { 107817189ac098b2f156713db1821b49db7b2f018bbebuzbee "Null Block", 10791fd3346740dfb7f47be9922312b68a4227fada96buzbee "Entry Block", 10801fd3346740dfb7f47be9922312b68a4227fada96buzbee "Code Block", 10811fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exit Block", 10821fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exception Handling", 10831fd3346740dfb7f47be9922312b68a4227fada96buzbee "Catch Block" 10841fd3346740dfb7f47be9922312b68a4227fada96buzbee }; 10851fd3346740dfb7f47be9922312b68a4227fada96buzbee 10861fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); 10871fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << cu_->insns << " insns"; 10881fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << GetNumBlocks() << " blocks in total"; 1089862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 10901fd3346740dfb7f47be9922312b68a4227fada96buzbee 10911fd3346740dfb7f47be9922312b68a4227fada96buzbee while (true) { 1092862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = iterator.Next(); 10931fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb == NULL) break; 10941fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", 10951fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id, 10961fd3346740dfb7f47be9922312b68a4227fada96buzbee block_type_names[bb->block_type], 10971fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->start_offset, 10981fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, 10991fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? "" : " empty"); 11000d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 11010d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Taken branch: block " << bb->taken 11020d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; 11031fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11040d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 11050d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Fallthrough : block " << bb->fall_through 11060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; 11071fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11081fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11091fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11101fd3346740dfb7f47be9922312b68a4227fada96buzbee 11111fd3346740dfb7f47be9922312b68a4227fada96buzbee/* 11121fd3346740dfb7f47be9922312b68a4227fada96buzbee * Build an array of location records for the incoming arguments. 11131fd3346740dfb7f47be9922312b68a4227fada96buzbee * Note: one location record per word of arguments, with dummy 11141fd3346740dfb7f47be9922312b68a4227fada96buzbee * high-word loc for wide arguments. Also pull up any following 11151fd3346740dfb7f47be9922312b68a4227fada96buzbee * MOVE_RESULT and incorporate it into the invoke. 11161fd3346740dfb7f47be9922312b68a4227fada96buzbee */ 11171fd3346740dfb7f47be9922312b68a4227fada96buzbeeCallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, 11182ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom bool is_range) { 1119f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), 1120f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocMisc)); 11211fd3346740dfb7f47be9922312b68a4227fada96buzbee MIR* move_result_mir = FindMoveResult(bb, mir); 11221fd3346740dfb7f47be9922312b68a4227fada96buzbee if (move_result_mir == NULL) { 11231fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result.location = kLocInvalid; 11241fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 11251fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result = GetRawDest(move_result_mir); 11261fd3346740dfb7f47be9922312b68a4227fada96buzbee move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); 11271fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11281fd3346740dfb7f47be9922312b68a4227fada96buzbee info->num_arg_words = mir->ssa_rep->num_uses; 11291fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> 1130f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, ArenaAllocator::kAllocMisc)); 11311fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < info->num_arg_words; i++) { 11321fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args[i] = GetRawSrc(mir, i); 11331fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11341fd3346740dfb7f47be9922312b68a4227fada96buzbee info->opt_flags = mir->optimization_flags; 11351fd3346740dfb7f47be9922312b68a4227fada96buzbee info->type = type; 11361fd3346740dfb7f47be9922312b68a4227fada96buzbee info->is_range = is_range; 11371fd3346740dfb7f47be9922312b68a4227fada96buzbee info->index = mir->dalvikInsn.vB; 11381fd3346740dfb7f47be9922312b68a4227fada96buzbee info->offset = mir->offset; 11391fd3346740dfb7f47be9922312b68a4227fada96buzbee return info; 11401fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11411fd3346740dfb7f47be9922312b68a4227fada96buzbee 1142862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee// Allocate a new basic block. 11432ce745c06271d5223d57dbf08117b20d5b60694aBrian CarlstromBasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { 1144f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier BasicBlock* bb = static_cast<BasicBlock*>(arena_->Alloc(sizeof(BasicBlock), 1145f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier ArenaAllocator::kAllocBB)); 1146862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->block_type = block_type; 1147862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->id = block_id; 1148862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // TUNING: better estimate of the exit block predecessors? 11490d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, 1150df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom (block_type == kExitBlock) ? 2048 : 2, 1151df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom kGrowableArrayPredecessors); 11520d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->successor_block_list_type = kNotUsed; 1153862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_id_map_.Put(block_id, block_id); 1154862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return bb; 1155862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} 11561fd3346740dfb7f47be9922312b68a4227fada96buzbee 11574e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeConstantPropagation() { 11584e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); 11594e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), ArenaAllocator::kAllocDFInfo)); 11604e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 11614e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11624e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeMethodUses() { 11634e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler // The gate starts by initializing the use counts 11644e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler int num_ssa_regs = GetNumSSARegs(); 11654e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Resize(num_ssa_regs + 32); 11664e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Resize(num_ssa_regs + 32); 11674e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler // Initialize list 11684e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler for (int i = 0; i < num_ssa_regs; i++) { 11694e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Insert(0); 11704e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Insert(0); 11714e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler } 11724e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 11734e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11744e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeSSATransformation() { 11754e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Compute the DFS order */ 11764e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDFSOrders(); 11774e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11784e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Compute the dominator info */ 11794e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDominators(); 11804e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11814e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Allocate data structures in preparation for SSA conversion */ 11824e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler CompilerInitializeSSAConversion(); 11834e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11844e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Find out the "Dalvik reg def x block" relation */ 11854e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ComputeDefBlockMatrix(); 11864e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11874e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Insert phi nodes to dominance frontiers for all variables */ 11884e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler InsertPhiNodes(); 11894e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11904e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* Rename register names by local defs and phi nodes */ 11914e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler ClearAllVisitedFlags(); 11924e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler DoDFSPreOrderSSARename(GetEntryBlock()); 11934e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 11944e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler /* 11954e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler * Shared temp bit vector used by each block to count the number of defs 11964e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler * from all the predecessor blocks. 11974e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler */ 11984e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler temp_ssa_register_v_ = 11994e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false, kBitMapTempSSARegisterV); 12004e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12014e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12024e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::CheckSSARegisterVector() { 12034e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler DCHECK(temp_ssa_register_v_ != nullptr); 12044e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 12054e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 12067934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom} // namespace art 1207