mir_graph.cc revision df62950e7a32031b82360c407d46a37b94188fbb
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 23311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeenamespace art { 24311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 25311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#define MAX_PATTERN_LEN 5 26311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 27311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeestruct CodePattern { 28311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const Instruction::Code opcodes[MAX_PATTERN_LEN]; 29311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const SpecialCaseHandler handler_code; 30311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee}; 31311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 32311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeestatic const CodePattern special_patterns[] = { 33311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::RETURN_VOID}, kNullMethod}, 34311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::CONST, Instruction::RETURN}, kConstFunction}, 35311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::CONST_4, Instruction::RETURN}, kConstFunction}, 36311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::CONST_4, Instruction::RETURN_OBJECT}, kConstFunction}, 37311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::CONST_16, Instruction::RETURN}, kConstFunction}, 38311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IGET, Instruction:: RETURN}, kIGet}, 39311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IGET_BOOLEAN, Instruction::RETURN}, kIGetBoolean}, 40311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IGET_OBJECT, Instruction::RETURN_OBJECT}, kIGetObject}, 41311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IGET_BYTE, Instruction::RETURN}, kIGetByte}, 42311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IGET_CHAR, Instruction::RETURN}, kIGetChar}, 43311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IGET_SHORT, Instruction::RETURN}, kIGetShort}, 44311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IGET_WIDE, Instruction::RETURN_WIDE}, kIGetWide}, 45311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IPUT, Instruction::RETURN_VOID}, kIPut}, 46311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IPUT_BOOLEAN, Instruction::RETURN_VOID}, kIPutBoolean}, 47311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IPUT_OBJECT, Instruction::RETURN_VOID}, kIPutObject}, 48311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IPUT_BYTE, Instruction::RETURN_VOID}, kIPutByte}, 49311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IPUT_CHAR, Instruction::RETURN_VOID}, kIPutChar}, 50311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IPUT_SHORT, Instruction::RETURN_VOID}, kIPutShort}, 51311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::IPUT_WIDE, Instruction::RETURN_VOID}, kIPutWide}, 52311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::RETURN}, kIdentity}, 53311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::RETURN_OBJECT}, kIdentity}, 54311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee {{Instruction::RETURN_WIDE}, kIdentity}, 55311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee}; 56311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 571fd3346740dfb7f47be9922312b68a4227fada96buzbeeconst char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { 581fd3346740dfb7f47be9922312b68a4227fada96buzbee "Phi", 591fd3346740dfb7f47be9922312b68a4227fada96buzbee "Copy", 601fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplFloat", 611fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgFloat", 621fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplDouble", 631fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgDouble", 641fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpLong", 651fd3346740dfb7f47be9922312b68a4227fada96buzbee "Nop", 661fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpNullCheck", 671fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpRangeCheck", 681fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpDivZeroCheck", 691fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check1", 701fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check2", 711fd3346740dfb7f47be9922312b68a4227fada96buzbee "Select", 721fd3346740dfb7f47be9922312b68a4227fada96buzbee}; 731fd3346740dfb7f47be9922312b68a4227fada96buzbee 74862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeMIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 751fd3346740dfb7f47be9922312b68a4227fada96buzbee : reg_location_(NULL), 76862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee compiler_temps_(arena, 6, kGrowableArrayMisc), 771fd3346740dfb7f47be9922312b68a4227fada96buzbee cu_(cu), 78311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_base_vregs_(NULL), 79311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_subscripts_(NULL), 80311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee vreg_to_ssa_map_(NULL), 81311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_last_defs_(NULL), 82311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee is_constant_v_(NULL), 83311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee constant_values_(NULL), 84862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee use_counts_(arena, 256, kGrowableArrayMisc), 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee raw_use_counts_(arena, 256, kGrowableArrayMisc), 86311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_reachable_blocks_(0), 87862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_(NULL), 88862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_(NULL), 89862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dom_post_order_traversal_(NULL), 90311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_(NULL), 91311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_block_matrix_(NULL), 92311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_block_v_(NULL), 93311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_dalvik_register_v_(NULL), 94311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee temp_ssa_register_v_(NULL), 95862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_(arena, 100, kGrowableArrayBlockList), 96311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee try_block_addr_(NULL), 97311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee entry_block_(NULL), 98311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee exit_block_(NULL), 99311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block_(NULL), 100311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_blocks_(0), 101311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_(NULL), 102311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_(kInvalidEntry), 103311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_(kInvalidEntry), 104311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_(0), 105311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_(NULL), 1061fd3346740dfb7f47be9922312b68a4227fada96buzbee num_ssa_regs_(0), 1071fd3346740dfb7f47be9922312b68a4227fada96buzbee method_sreg_(0), 108862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. 109862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee checkstats_(NULL), 1102ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom arena_(arena) { 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); 112311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 113311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 1146282dc12440a2072dc06a616160027ff21bd895eIan RogersMIRGraph::~MIRGraph() { 1156282dc12440a2072dc06a616160027ff21bd895eIan Rogers STLDeleteElements(&m_units_); 1166282dc12440a2072dc06a616160027ff21bd895eIan Rogers} 1176282dc12440a2072dc06a616160027ff21bd895eIan Rogers 118311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeebool MIRGraph::ContentIsInsn(const uint16_t* code_ptr) { 119311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint16_t instr = *code_ptr; 120311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee Instruction::Code opcode = static_cast<Instruction::Code>(instr & 0xff); 121311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 122311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Since the low 8-bit in metadata may look like NOP, we need to check 123311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * both the low and whole sub-word to determine whether it is code or data. 124311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 125311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return (opcode != Instruction::NOP || instr == 0); 126311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 127311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 128311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 129311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Parse an instruction, return the length of the instruction 130311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 1312ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromint MIRGraph::ParseInsn(const uint16_t* code_ptr, DecodedInstruction* decoded_instruction) { 132311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Don't parse instruction data 133311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (!ContentIsInsn(code_ptr)) { 134311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return 0; 135311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 136311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 137311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const Instruction* instruction = Instruction::At(code_ptr); 138311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *decoded_instruction = DecodedInstruction(instruction); 139311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 140311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return instruction->SizeInCodeUnits(); 141311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 142311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 143311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 144311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Split an existing block from the specified code offset into two */ 145311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeeBasicBlock* MIRGraph::SplitBlock(unsigned int code_offset, 1462ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { 147311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MIR* insn = orig_block->first_mir_insn; 148311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (insn) { 149311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->offset == code_offset) break; 150311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn = insn->next; 151311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 152311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn == NULL) { 153311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Break split failed"; 154311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 155862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); 156862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bottom_block); 157311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 158311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->start_offset = code_offset; 159311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->first_mir_insn = insn; 160311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->last_mir_insn = orig_block->last_mir_insn; 161311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 162311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* If this block was terminated by a return, the flag needs to go with the bottom block */ 163311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->terminated_by_return = orig_block->terminated_by_return; 164311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->terminated_by_return = false; 165311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 166311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Add it to the quick lookup cache */ 167311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_map_.Put(bottom_block->start_offset, bottom_block); 168311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 169311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the taken path */ 170311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->taken = orig_block->taken; 171311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bottom_block->taken) { 172311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->taken = NULL; 173862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bottom_block->taken->predecessors->Delete(orig_block); 174862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bottom_block->taken->predecessors->Insert(bottom_block); 175311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 176311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 177311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the fallthrough path */ 178311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->fall_through = orig_block->fall_through; 179311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->fall_through = bottom_block; 180862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bottom_block->predecessors->Insert(orig_block); 181311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bottom_block->fall_through) { 182862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bottom_block->fall_through->predecessors->Delete(orig_block); 183862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bottom_block->fall_through->predecessors->Insert(bottom_block); 184311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 185311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 186311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the successor list */ 187311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (orig_block->successor_block_list.block_list_type != kNotUsed) { 188311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->successor_block_list = orig_block->successor_block_list; 189311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->successor_block_list.block_list_type = kNotUsed; 190862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_block_list.blocks); 191311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 192862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 193311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 194311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *bb = successor_block_info->block; 195862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->predecessors->Delete(orig_block); 196862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->predecessors->Insert(bottom_block); 197311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 198311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 199311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 200311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->last_mir_insn = insn->prev; 201311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 202311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->prev->next = NULL; 203311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->prev = NULL; 204311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 205311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Update the immediate predecessor block pointer so that outgoing edges 206311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * can be applied to the proper block. 207311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 208311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (immed_pred_block_p) { 209311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(*immed_pred_block_p, orig_block); 210311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *immed_pred_block_p = bottom_block; 211311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 212311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bottom_block; 213311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 214311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 215311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 216311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Given a code offset, find out the block that starts with it. If the offset 217311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is in the middle of an existing block, split it into two. If immed_pred_block_p 218311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is not non-null and is the block being split, update *immed_pred_block_p to 219311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * point to the bottom block so that outgoing edges can be set up properly 220311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (by the caller) 221311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Utilizes a map for fast lookup of the typical cases. 222311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 223311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeeBasicBlock* MIRGraph::FindBlock(unsigned int code_offset, bool split, bool create, 2242ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock** immed_pred_block_p) { 225311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock* bb; 226311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee unsigned int i; 227311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SafeMap<unsigned int, BasicBlock*>::iterator it; 228311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 229311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee it = block_map_.find(code_offset); 230311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (it != block_map_.end()) { 231311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return it->second; 232311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (!create) { 233311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return NULL; 234311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 235311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 236311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (split) { 237862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee for (i = 0; i < block_list_.Size(); i++) { 238862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = block_list_.Get(i); 239311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type != kDalvikByteCode) continue; 240311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Check if a branch jumps into the middle of an existing block */ 241311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if ((code_offset > bb->start_offset) && (bb->last_mir_insn != NULL) && 242311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (code_offset <= bb->last_mir_insn->offset)) { 243311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *new_bb = SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? 244311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee immed_pred_block_p : NULL); 245311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return new_bb; 246311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 247311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 248311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 249311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 250311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Create a new one */ 251862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = NewMemBB(kDalvikByteCode, num_blocks_++); 252862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bb); 253311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset = code_offset; 254311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_map_.Put(bb->start_offset, bb); 255311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bb; 256311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 257311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 258311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Identify code range in try blocks and set up the empty catch blocks */ 2592ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ProcessTryCatchBlocks() { 260311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int tries_size = current_code_item_->tries_size_; 261311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int offset; 262311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 263311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (tries_size == 0) { 264311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 265311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 266311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 267311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < tries_size; i++) { 268311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const DexFile::TryItem* pTry = 269311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DexFile::GetTryItems(*current_code_item_, i); 270311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int start_offset = pTry->start_addr_; 271311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int end_offset = start_offset + pTry->insn_count_; 272311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (offset = start_offset; offset < end_offset; offset++) { 273862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(offset); 274311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 275311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 276311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 277311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Iterate over each of the handlers to enqueue the empty Catch blocks 278311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); 279311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 280311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (uint32_t idx = 0; idx < handlers_size; idx++) { 281311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(handlers_ptr); 282311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (; iterator.HasNext(); iterator.Next()) { 283311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t address = iterator.GetHandlerAddress(); 284311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(address, false /* split */, true /*create*/, 285311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 286311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 287311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee handlers_ptr = iterator.EndDataPointer(); 288311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 289311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 290311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 291311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kBranch flag */ 292311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeeBasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, int cur_offset, int width, 293311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int flags, const uint16_t* code_ptr, 2942ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_end) { 295311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int target = cur_offset; 296311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee switch (insn->dalvikInsn.opcode) { 297311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO: 298311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_16: 299311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_32: 300311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vA; 301311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 302311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQ: 303311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NE: 304311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LT: 305311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GE: 306311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GT: 307311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LE: 308311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 309311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vC; 310311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 311311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQZ: 312311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NEZ: 313311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LTZ: 314311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GEZ: 315311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GTZ: 316311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LEZ: 317311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 318311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vB; 319311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 320311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee default: 321311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; 322311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 323311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *taken_block = FindBlock(target, /* split */ true, /* create */ true, 324311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ &cur_block); 325311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->taken = taken_block; 326862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee taken_block->predecessors->Insert(cur_block); 327311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 328311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Always terminate the current block for conditional branches */ 329311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kContinue) { 330311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *fallthrough_block = FindBlock(cur_offset + width, 331311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 332311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * If the method is processed 333311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * in sequential order from the 334311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * beginning, we don't need to 335311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * specify split for continue 336311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * blocks. However, this 337311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * routine can be called by 338311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * compileLoop, which starts 339311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * parsing the method from an 340311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * arbitrary address in the 341311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * method body. 342311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 343311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 344311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ 345311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 346311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ 347311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee &cur_block); 348311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->fall_through = fallthrough_block; 349862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee fallthrough_block->predecessors->Insert(cur_block); 350311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (code_ptr < code_end) { 351311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Create a fallthrough block for real instructions (incl. NOP) */ 352311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (ContentIsInsn(code_ptr)) { 353311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 354311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 355311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 356311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 357311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 358311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 359311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 360311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kSwitch flag */ 361311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, int cur_offset, int width, 3622ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom int flags) { 363311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* switch_data = 364311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); 365311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int size; 366311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* keyTable; 367311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* target_table; 368311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int i; 369311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int first_key; 370311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 371311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 372311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Packed switch data format: 373311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0100 magic value 374311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table 375311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int first_key first (and lowest) switch case value 376311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 377311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 378311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (4+size*2) 16-bit code units. 379311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 380311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { 381311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 382311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kPackedSwitchSignature)); 383311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 384311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = switch_data[2] | (switch_data[3] << 16); 385311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[4]); 386311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = NULL; // Make the compiler happy 387311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 388311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Sparse switch data format: 389311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0200 magic value 390311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table; > 0 391311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int keys[size] keys, sorted low-to-high; 32-bit aligned 392311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 393311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 394311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (2+size*4) 16-bit code units. 395311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 396311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 397311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 398311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kSparseSwitchSignature)); 399311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 400311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = reinterpret_cast<const int*>(&switch_data[2]); 401311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); 402311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = 0; // To make the compiler happy 403311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 404311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 405311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cur_block->successor_block_list.block_list_type != kNotUsed) { 406311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 407311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee << static_cast<int>(cur_block->successor_block_list.block_list_type); 408311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 409311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->successor_block_list.block_list_type = 410311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 411311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee kPackedSwitch : kSparseSwitch; 412862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee cur_block->successor_block_list.blocks = 413df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); 414311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 415311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (i = 0; i < size; i++) { 416311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *case_block = FindBlock(cur_offset + target_table[i], /* split */ true, 417311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ true, /* immed_pred_block_p */ &cur_block); 418311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = 419862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static_cast<SuccessorBlockInfo*>(arena_->NewMem(sizeof(SuccessorBlockInfo), false, 420862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator::kAllocSuccessor)); 421311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->block = case_block; 422311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = 423311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 424311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key + i : keyTable[i]; 425862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee cur_block->successor_block_list.blocks->Insert(successor_block_info); 426862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee case_block->predecessors->Insert(cur_block); 427311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 428311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 429311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Fall-through case */ 430df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, 431df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom /* create */ true, /* immed_pred_block_p */ NULL); 432311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->fall_through = fallthrough_block; 433862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee fallthrough_block->predecessors->Insert(cur_block); 434311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 435311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 436311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kThrow flag */ 437311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeeBasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, int cur_offset, int width, 438311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int flags, ArenaBitVector* try_block_addr, 4392ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_ptr, const uint16_t* code_end) { 440862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool in_try_block = try_block_addr->IsBitSet(cur_offset); 441311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 442311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* In try block */ 443311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (in_try_block) { 444311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(*current_code_item_, cur_offset); 445311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 446311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cur_block->successor_block_list.block_list_type != kNotUsed) { 447311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 448311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 449311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee << static_cast<int>(cur_block->successor_block_list.block_list_type); 450311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 451311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 452311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->successor_block_list.block_list_type = kCatch; 453862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee cur_block->successor_block_list.blocks = 454862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, 2, kGrowableArraySuccessorBlocks); 455311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 456311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (;iterator.HasNext(); iterator.Next()) { 457311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, 458311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false /* creat */, NULL /* immed_pred_block_p */); 459311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catch_block->catch_entry = true; 460311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (kIsDebugBuild) { 461311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catches_.insert(catch_block->start_offset); 462311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 463311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SuccessorBlockInfo *successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 464862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee (arena_->NewMem(sizeof(SuccessorBlockInfo), false, ArenaAllocator::kAllocSuccessor)); 465311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->block = catch_block; 466311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = iterator.GetHandlerTypeIndex(); 467862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee cur_block->successor_block_list.blocks->Insert(successor_block_info); 468862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee catch_block->predecessors->Insert(cur_block); 469311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 470311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 471862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *eh_block = NewMemBB(kExceptionHandling, num_blocks_++); 472311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->taken = eh_block; 473862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(eh_block); 474311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee eh_block->start_offset = cur_offset; 475862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee eh_block->predecessors->Insert(cur_block); 476311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 477311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 4782ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom if (insn->dalvikInsn.opcode == Instruction::THROW) { 479311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->explicit_throw = true; 480311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if ((code_ptr < code_end) && ContentIsInsn(code_ptr)) { 481311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Force creation of new block following THROW via side-effect 482311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 483311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 484311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 485311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (!in_try_block) { 486311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Don't split a THROW that can't rethrow - we're done. 487311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 488311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 489311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 490311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 491311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 492311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Split the potentially-throwing instruction into two parts. 493311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The first half will be a pseudo-op that captures the exception 494311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * edges and terminates the basic block. It always falls through. 495311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Then, create a new basic block that begins with the throwing instruction 496311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (minus exceptions). Note: this new basic block must NOT be entered into 497311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the block_map. If the potentially-throwing instruction is the target of a 498311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * future branch, we need to find the check psuedo half. The new 499311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * basic block containing the work portion of the instruction should 500311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * only be entered via fallthrough from the block containing the 501311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * pseudo exception edge MIR. Note also that this new block is 502311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * not automatically terminated after the work portion, and may 503311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * contain following instructions. 504311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 505862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *new_block = NewMemBB(kDalvikByteCode, num_blocks_++); 506862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(new_block); 507311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee new_block->start_offset = insn->offset; 508311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->fall_through = new_block; 509862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee new_block->predecessors->Insert(cur_block); 510862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee MIR* new_insn = static_cast<MIR*>(arena_->NewMem(sizeof(MIR), true, ArenaAllocator::kAllocMIR)); 511311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *new_insn = *insn; 512311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->dalvikInsn.opcode = 513311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<Instruction::Code>(kMirOpCheck); 514311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Associate the two halves 515311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->meta.throw_insn = new_insn; 516311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee new_insn->meta.throw_insn = insn; 517311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee AppendMIR(new_block, new_insn); 518311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return new_block; 519311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 520311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 521311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ 522311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 523311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee InvokeType invoke_type, uint32_t class_def_idx, 5242ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { 525311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_ = code_item; 526311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee method_stack_.push_back(std::make_pair(current_method_, current_offset_)); 527311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_ = m_units_.size(); 528311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ = 0; 529311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: will need to snapshot stack image and use that as the mir context identification. 530311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), 531311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee dex_file, current_code_item_, class_def_idx, method_idx, access_flags)); 532311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_ptr = current_code_item_->insns_; 533311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_end = 534311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; 535311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 536311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: need to rework expansion of block list & try_block_addr when inlining activated. 537862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); 538311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: replace with explicit resize routine. Using automatic extension side effect for now. 539862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); 540862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); 541311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 542311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // If this is the first method, set up default entry and exit blocks. 543311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (current_method_ == 0) { 544311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(entry_block_ == NULL); 545311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(exit_block_ == NULL); 546311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(num_blocks_ == 0); 547862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); 548862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee exit_block_ = NewMemBB(kExitBlock, num_blocks_++); 549862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(entry_block_); 550862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(exit_block_); 551311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. 552311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->dex_file = &dex_file; 553311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->class_def_idx = class_def_idx; 554311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->method_idx = method_idx; 555311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->access_flags = access_flags; 556311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->invoke_type = invoke_type; 557311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); 558311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_ins = current_code_item_->ins_size_; 559311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_regs = current_code_item_->registers_size_ - cu_->num_ins; 560311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_outs = current_code_item_->outs_size_; 561311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_dalvik_registers = current_code_item_->registers_size_; 562311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->insns = current_code_item_->insns_; 563311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->code_item = current_code_item_; 564311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 565311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; 566311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 567311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Will need to manage storage for ins & outs, push prevous state and update 568311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * insert point. 569311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 570311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 571311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 572311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Current block to record parsed instructions */ 573862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock *cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); 574311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(current_offset_, 0); 575311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->start_offset = current_offset_; 576862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(cur_block); 577311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Add first block to the fast lookup cache */ 578311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee// FIXME: block map needs association with offset/method pair rather than just offset 579311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_map_.Put(cur_block->start_offset, cur_block); 580311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee// FIXME: this needs to insert at the insert point rather than entry block. 581311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee entry_block_->fall_through = cur_block; 582862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee cur_block->predecessors->Insert(entry_block_); 583311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 584311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Identify code range in try blocks and set up the empty catch blocks */ 585311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ProcessTryCatchBlocks(); 586311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 587311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Set up for simple method detection */ 588311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_patterns = sizeof(special_patterns)/sizeof(special_patterns[0]); 589311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bool live_pattern = (num_patterns > 0) && !(cu_->disable_opt & (1 << kMatch)); 590311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bool* dead_pattern = 591862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static_cast<bool*>(arena_->NewMem(sizeof(bool) * num_patterns, true, 592862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator::kAllocMisc)); 593311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee SpecialCaseHandler special_case = kNoHandler; 594311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // FIXME - wire this up 595311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (void)special_case; 596311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int pattern_pos = 0; 597311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 598311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Parse all instructions and put them into containing basic blocks */ 599311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (code_ptr < code_end) { 600862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee MIR *insn = static_cast<MIR *>(arena_->NewMem(sizeof(MIR), true, ArenaAllocator::kAllocMIR)); 601311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->offset = current_offset_; 602311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->m_unit_index = current_method_; 603311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int width = ParseInsn(code_ptr, &insn->dalvikInsn); 604311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->width = width; 605311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee Instruction::Code opcode = insn->dalvikInsn.opcode; 606311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_ != NULL) { 607311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_[static_cast<int>(opcode)]++; 608311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 609311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 610311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Terminate when the data section is seen */ 611311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (width == 0) 612311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 613311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 614311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Possible simple method? */ 615311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (live_pattern) { 616311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee live_pattern = false; 617311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee special_case = kNoHandler; 618311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < num_patterns; i++) { 619311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (!dead_pattern[i]) { 620311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (special_patterns[i].opcodes[pattern_pos] == opcode) { 621311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee live_pattern = true; 622311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee special_case = special_patterns[i].handler_code; 623311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 624311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee dead_pattern[i] = true; 625311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 626311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 627311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 628311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee pattern_pos++; 629311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 630311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 631311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee AppendMIR(cur_block, insn); 632311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 633311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee code_ptr += width; 634311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int flags = Instruction::FlagsOf(insn->dalvikInsn.opcode); 635311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6361fd3346740dfb7f47be9922312b68a4227fada96buzbee int df_flags = oat_data_flow_attributes_[insn->dalvikInsn.opcode]; 637311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 638311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (df_flags & DF_HAS_DEFS) { 639311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; 640311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 641311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 642311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kBranch) { 643311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanBranch(cur_block, insn, current_offset_, 644311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee width, flags, code_ptr, code_end); 645311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kReturn) { 646311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->terminated_by_return = true; 647311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->fall_through = exit_block_; 648862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee exit_block_->predecessors->Insert(cur_block); 649311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 650311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Terminate the current block if there are instructions 651311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * afterwards. 652311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 653311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (code_ptr < code_end) { 654311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 655311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Create a fallthrough block for real instructions 656311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (incl. NOP). 657311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 658311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (ContentIsInsn(code_ptr)) { 659311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(current_offset_ + width, /* split */ false, /* create */ true, 660311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 661311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 662311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 663311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kThrow) { 664311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, 665311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee code_ptr, code_end); 666311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kSwitch) { 667311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); 668311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 669311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ += width; 670311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *next_block = FindBlock(current_offset_, /* split */ false, /* create */ 671311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false, /* immed_pred_block_p */ NULL); 672311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (next_block) { 673311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 674311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The next instruction could be the target of a previously parsed 675311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * forward branch so a block is already created. If the current 676311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * instruction is not an unconditional branch, connect them through 677311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the fall-through link. 678311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 679311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(cur_block->fall_through == NULL || 680311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->fall_through == next_block || 681311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->fall_through == exit_block_); 682311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 683311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if ((cur_block->fall_through == NULL) && (flags & Instruction::kContinue)) { 684311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->fall_through = next_block; 685862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee next_block->predecessors->Insert(cur_block); 686311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 687311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = next_block; 688311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 689311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 690311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 691311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DumpCFG("/sdcard/1_post_parse_cfg/", true); 692311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 693311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 694311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 6951fd3346740dfb7f47be9922312b68a4227fada96buzbee DumpMIRGraph(); 696311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 697311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 698311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 6992ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ShowOpcodeStats() { 700311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(opcode_count_ != NULL); 701311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "Opcode Count"; 702311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < kNumPackedOpcodes; i++) { 703311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_[i] != 0) { 704311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) 705311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee << " " << opcode_count_[i]; 706311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 707311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 708311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 709311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 710311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee// TODO: use a configurable base prefix, and adjust callers to supply pass name. 711311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Dump the CFG into a DOT graph */ 7122ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks) { 713311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FILE* file; 714311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); 715311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ReplaceSpecialChars(fname); 716311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fname = StringPrintf("%s%s%x.dot", dir_prefix, fname.c_str(), 717311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetEntryBlock()->fall_through->start_offset); 718311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee file = fopen(fname.c_str(), "w"); 719311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (file == NULL) { 720311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 721311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 722311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "digraph G {\n"); 723311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 724311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " rankdir=TB\n"); 725311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 726311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; 727311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int idx; 728311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 729311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (idx = 0; idx < num_blocks; idx++) { 730862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int block_idx = all_blocks ? idx : dfs_order_->Get(idx); 731311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *bb = GetBasicBlock(block_idx); 732311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb == NULL) break; 733311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kDead) continue; 734311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kEntryBlock) { 735311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); 736311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExitBlock) { 737311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); 738311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kDalvikByteCode) { 739311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", 740311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id); 741311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const MIR *mir; 742311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 743311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->first_mir_insn ? " | " : " "); 744311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (mir = bb->first_mir_insn; mir; mir = mir->next) { 745311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int opcode = mir->dalvikInsn.opcode; 746311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {%04x %s %s %s\\l}%s\\\n", mir->offset, 7471fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->ssa_rep ? GetDalvikDisassembly(mir) : 748311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (opcode < kMirOpFirst) ? Instruction::Name(mir->dalvikInsn.opcode) : 7491fd3346740dfb7f47be9922312b68a4227fada96buzbee extended_mir_op_names_[opcode - kMirOpFirst], 750311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", 751311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", 752311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee mir->next ? " | " : " "); 753311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 754311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 755311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExceptionHandling) { 756311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name[BLOCK_NAME_LEN]; 757311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 758311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name); 759311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s [shape=invhouse];\n", block_name); 760311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 761311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 762311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 763311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 764311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->taken) { 765311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 766311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb->taken, block_name2); 767311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n [style=dotted]\n", 768311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name2); 769311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 770311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->fall_through) { 771311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 772311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb->fall_through, block_name2); 773311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); 774311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 775311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 776311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->successor_block_list.block_list_type != kNotUsed) { 777311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", 778311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id, 779311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (bb->successor_block_list.block_list_type == kCatch) ? 780311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee "Mrecord" : "record"); 781862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_block_list.blocks); 782862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iterator.Next(); 783311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 784311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int succ_id = 0; 785311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 786311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 787311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 788311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *dest_block = successor_block_info->block; 789862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *next_successor_block_info = iterator.Next(); 790311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 791311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 792311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id++, 793311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key, 794311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee dest_block->start_offset, 795311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (next_successor_block_info != NULL) ? " | " : " "); 796311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 797311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info = next_successor_block_info; 798311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 799311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 800311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 801311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 802311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", 803311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, bb->start_offset, bb->id); 804311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 805311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->successor_block_list.block_list_type == kPackedSwitch || 806311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->successor_block_list.block_list_type == kSparseSwitch) { 807862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_block_list.blocks); 808311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 809311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id = 0; 810311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 811862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *successor_block_info = iter.Next(); 812311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 813311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 814311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee BasicBlock *dest_block = successor_block_info->block; 815311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 816311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(dest_block, block_name2); 817311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, 818311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->id, succ_id++, block_name2); 819311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 820311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 821311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 822311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "\n"); 823311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 824311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 825311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Display the dominator tree */ 826311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 827311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 828311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name1); 829311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->i_dom) { 830311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb->i_dom, block_name2); 831311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); 832311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 833311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 834311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 835311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "}\n"); 836311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fclose(file); 837311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 838311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8391fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the end of a basic block */ 8402ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::AppendMIR(BasicBlock* bb, MIR* mir) { 8411fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->first_mir_insn == NULL) { 8421fd3346740dfb7f47be9922312b68a4227fada96buzbee DCHECK(bb->last_mir_insn == NULL); 8431fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = bb->first_mir_insn = mir; 8441fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->prev = mir->next = NULL; 8451fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 8461fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn->next = mir; 8471fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->prev = bb->last_mir_insn; 8481fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->next = NULL; 8491fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = mir; 8501fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8511fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8521fd3346740dfb7f47be9922312b68a4227fada96buzbee 8531fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert an MIR instruction to the head of a basic block */ 8542ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::PrependMIR(BasicBlock* bb, MIR* mir) { 8551fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->first_mir_insn == NULL) { 8561fd3346740dfb7f47be9922312b68a4227fada96buzbee DCHECK(bb->last_mir_insn == NULL); 8571fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = bb->first_mir_insn = mir; 8581fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->prev = mir->next = NULL; 8591fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 8601fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->first_mir_insn->prev = mir; 8611fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->next = bb->first_mir_insn; 8621fd3346740dfb7f47be9922312b68a4227fada96buzbee mir->prev = NULL; 8631fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->first_mir_insn = mir; 8641fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8651fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8661fd3346740dfb7f47be9922312b68a4227fada96buzbee 8671fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Insert a MIR instruction after the specified MIR */ 8682ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir) { 8691fd3346740dfb7f47be9922312b68a4227fada96buzbee new_mir->prev = current_mir; 8701fd3346740dfb7f47be9922312b68a4227fada96buzbee new_mir->next = current_mir->next; 8711fd3346740dfb7f47be9922312b68a4227fada96buzbee current_mir->next = new_mir; 8721fd3346740dfb7f47be9922312b68a4227fada96buzbee 8731fd3346740dfb7f47be9922312b68a4227fada96buzbee if (new_mir->next) { 8741fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Is not the last MIR in the block */ 8751fd3346740dfb7f47be9922312b68a4227fada96buzbee new_mir->next->prev = new_mir; 8761fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 8771fd3346740dfb7f47be9922312b68a4227fada96buzbee /* Is the last MIR in the block */ 8781fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn = new_mir; 8791fd3346740dfb7f47be9922312b68a4227fada96buzbee } 8801fd3346740dfb7f47be9922312b68a4227fada96buzbee} 8811fd3346740dfb7f47be9922312b68a4227fada96buzbee 8822ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromchar* MIRGraph::GetDalvikDisassembly(const MIR* mir) { 8831fd3346740dfb7f47be9922312b68a4227fada96buzbee DecodedInstruction insn = mir->dalvikInsn; 8841fd3346740dfb7f47be9922312b68a4227fada96buzbee std::string str; 8851fd3346740dfb7f47be9922312b68a4227fada96buzbee int flags = 0; 8861fd3346740dfb7f47be9922312b68a4227fada96buzbee int opcode = insn.opcode; 8871fd3346740dfb7f47be9922312b68a4227fada96buzbee char* ret; 8881fd3346740dfb7f47be9922312b68a4227fada96buzbee bool nop = false; 8891fd3346740dfb7f47be9922312b68a4227fada96buzbee SSARepresentation* ssa_rep = mir->ssa_rep; 8901fd3346740dfb7f47be9922312b68a4227fada96buzbee Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format 8911fd3346740dfb7f47be9922312b68a4227fada96buzbee int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; 8921fd3346740dfb7f47be9922312b68a4227fada96buzbee int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; 8931fd3346740dfb7f47be9922312b68a4227fada96buzbee 8941fd3346740dfb7f47be9922312b68a4227fada96buzbee // Handle special cases. 8951fd3346740dfb7f47be9922312b68a4227fada96buzbee if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { 8961fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 8971fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(": "); 8981fd3346740dfb7f47be9922312b68a4227fada96buzbee // Recover the original Dex instruction 8991fd3346740dfb7f47be9922312b68a4227fada96buzbee insn = mir->meta.throw_insn->dalvikInsn; 9001fd3346740dfb7f47be9922312b68a4227fada96buzbee ssa_rep = mir->meta.throw_insn->ssa_rep; 9011fd3346740dfb7f47be9922312b68a4227fada96buzbee defs = ssa_rep->num_defs; 9021fd3346740dfb7f47be9922312b68a4227fada96buzbee uses = ssa_rep->num_uses; 9031fd3346740dfb7f47be9922312b68a4227fada96buzbee opcode = insn.opcode; 9041fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if (opcode == kMirOpNop) { 9051fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("["); 9061fd3346740dfb7f47be9922312b68a4227fada96buzbee insn.opcode = mir->meta.original_opcode; 9071fd3346740dfb7f47be9922312b68a4227fada96buzbee opcode = mir->meta.original_opcode; 9081fd3346740dfb7f47be9922312b68a4227fada96buzbee nop = true; 9091fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9101fd3346740dfb7f47be9922312b68a4227fada96buzbee 9111fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode >= kMirOpFirst) { 9121fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 9131fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 9141fd3346740dfb7f47be9922312b68a4227fada96buzbee dalvik_format = Instruction::FormatOf(insn.opcode); 9151fd3346740dfb7f47be9922312b68a4227fada96buzbee flags = Instruction::FlagsOf(insn.opcode); 9161fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(Instruction::Name(insn.opcode)); 9171fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9181fd3346740dfb7f47be9922312b68a4227fada96buzbee 9191fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode == kMirOpPhi) { 9201fd3346740dfb7f47be9922312b68a4227fada96buzbee int* incoming = reinterpret_cast<int*>(insn.vB); 9211fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s = (%s", 9221fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), 9231fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); 924b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom str.append(StringPrintf(":%d", incoming[0])); 9251fd3346740dfb7f47be9922312b68a4227fada96buzbee int i; 9261fd3346740dfb7f47be9922312b68a4227fada96buzbee for (i = 1; i < uses; i++) { 9271fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", %s:%d", 9281fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), 9291fd3346740dfb7f47be9922312b68a4227fada96buzbee incoming[i])); 9301fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9311fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(")"); 9321fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if ((flags & Instruction::kBranch) != 0) { 9331fd3346740dfb7f47be9922312b68a4227fada96buzbee // For branches, decode the instructions to print out the branch targets. 9341fd3346740dfb7f47be9922312b68a4227fada96buzbee int offset = 0; 9351fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 9361fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21t: 9371fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 9381fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vB; 9391fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9401fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22t: 9411fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), 9421fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); 9431fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vC; 9441fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9451fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k10t: 9461fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k20t: 9471fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k30t: 9481fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vA; 9491fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9501fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 9511fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; 9521fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9531fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset, 9541fd3346740dfb7f47be9922312b68a4227fada96buzbee offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); 9551fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 9561fd3346740dfb7f47be9922312b68a4227fada96buzbee // For invokes-style formats, treat wide regs as a pair of singles 9571fd3346740dfb7f47be9922312b68a4227fada96buzbee bool show_singles = ((dalvik_format == Instruction::k35c) || 9581fd3346740dfb7f47be9922312b68a4227fada96buzbee (dalvik_format == Instruction::k3rc)); 9591fd3346740dfb7f47be9922312b68a4227fada96buzbee if (defs != 0) { 9601fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s", GetSSANameWithConst(ssa_rep->defs[0], false).c_str())); 9611fd3346740dfb7f47be9922312b68a4227fada96buzbee if (uses != 0) { 9621fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(", "); 9631fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9641fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9651fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < uses; i++) { 9661fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append( 9671fd3346740dfb7f47be9922312b68a4227fada96buzbee StringPrintf(" %s", GetSSANameWithConst(ssa_rep->uses[i], show_singles).c_str())); 9681fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { 9691fd3346740dfb7f47be9922312b68a4227fada96buzbee // For the listing, skip the high sreg. 9701fd3346740dfb7f47be9922312b68a4227fada96buzbee i++; 9711fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9721fd3346740dfb7f47be9922312b68a4227fada96buzbee if (i != (uses -1)) { 9731fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(","); 9741fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9751fd3346740dfb7f47be9922312b68a4227fada96buzbee } 9761fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 9771fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k11n: // Add one immediate from vB 9781fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21s: 9791fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31i: 9801fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21h: 9811fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vB)); 9821fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9831fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k51l: // Add one wide immediate 9841fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%lld", insn.vB_wide)); 9851fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9861fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21c: // One register, one string/type/method index 9871fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31c: 9881fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vB)); 9891fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9901fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22c: // Two registers, one string/type/method index 9911fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vC)); 9921fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9931fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22s: // Add one immediate from vC 9941fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22b: 9951fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vC)); 9961fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 9971fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 9981fd3346740dfb7f47be9922312b68a4227fada96buzbee ; // Nothing left to print 9991fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10001fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10011fd3346740dfb7f47be9922312b68a4227fada96buzbee if (nop) { 10021fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("]--optimized away"); 10031fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10041fd3346740dfb7f47be9922312b68a4227fada96buzbee int length = str.length() + 1; 1005862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ret = static_cast<char*>(arena_->NewMem(length, false, 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) { 10121fd3346740dfb7f47be9922312b68a4227fada96buzbee static const struct { const char before; const char after; } match[] = 1013b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom {{'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, 1014b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='}}; 10151fd3346740dfb7f47be9922312b68a4227fada96buzbee for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { 10161fd3346740dfb7f47be9922312b68a4227fada96buzbee std::replace(str.begin(), str.end(), match[i].before, match[i].after); 10171fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10181fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10191fd3346740dfb7f47be9922312b68a4227fada96buzbee 10202ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSAName(int ssa_reg) { 102139ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to 102239ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // the arena. We should be smarter and just place straight into the arena, or compute the 102339ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // value more lazily. 10241fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 10251fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10261fd3346740dfb7f47be9922312b68a4227fada96buzbee 10271fd3346740dfb7f47be9922312b68a4227fada96buzbee// Similar to GetSSAName, but if ssa name represents an immediate show that as well. 10282ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { 10291fd3346740dfb7f47be9922312b68a4227fada96buzbee if (reg_location_ == NULL) { 10301fd3346740dfb7f47be9922312b68a4227fada96buzbee // Pre-SSA - just use the standard name 10311fd3346740dfb7f47be9922312b68a4227fada96buzbee return GetSSAName(ssa_reg); 10321fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10331fd3346740dfb7f47be9922312b68a4227fada96buzbee if (IsConst(reg_location_[ssa_reg])) { 10341fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!singles_only && reg_location_[ssa_reg].wide) { 10351fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d#0x%llx", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 10361fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValueWide(reg_location_[ssa_reg])); 10371fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 1038b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 10391fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValue(reg_location_[ssa_reg])); 10401fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10411fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 10421fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 10431fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10441fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10451fd3346740dfb7f47be9922312b68a4227fada96buzbee 10462ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::GetBlockName(BasicBlock* bb, char* name) { 10471fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (bb->block_type) { 10481fd3346740dfb7f47be9922312b68a4227fada96buzbee case kEntryBlock: 10491fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); 10501fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10511fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExitBlock: 10521fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); 10531fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10541fd3346740dfb7f47be9922312b68a4227fada96buzbee case kDalvikByteCode: 10551fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); 10561fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10571fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExceptionHandling: 10581fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, 10591fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id); 10601fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10611fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 10621fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); 10631fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 10641fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10651fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10661fd3346740dfb7f47be9922312b68a4227fada96buzbee 10672ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromconst char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { 10681fd3346740dfb7f47be9922312b68a4227fada96buzbee // FIXME: use current code unit for inline support. 10691fd3346740dfb7f47be9922312b68a4227fada96buzbee const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); 10701fd3346740dfb7f47be9922312b68a4227fada96buzbee return cu_->dex_file->GetShorty(method_id.proto_idx_); 10711fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10721fd3346740dfb7f47be9922312b68a4227fada96buzbee 10731fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Debug Utility - dump a compilation unit */ 10742ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DumpMIRGraph() { 10751fd3346740dfb7f47be9922312b68a4227fada96buzbee BasicBlock* bb; 10761fd3346740dfb7f47be9922312b68a4227fada96buzbee const char* block_type_names[] = { 10771fd3346740dfb7f47be9922312b68a4227fada96buzbee "Entry Block", 10781fd3346740dfb7f47be9922312b68a4227fada96buzbee "Code Block", 10791fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exit Block", 10801fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exception Handling", 10811fd3346740dfb7f47be9922312b68a4227fada96buzbee "Catch Block" 10821fd3346740dfb7f47be9922312b68a4227fada96buzbee }; 10831fd3346740dfb7f47be9922312b68a4227fada96buzbee 10841fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); 10851fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << cu_->insns << " insns"; 10861fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << GetNumBlocks() << " blocks in total"; 1087862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 10881fd3346740dfb7f47be9922312b68a4227fada96buzbee 10891fd3346740dfb7f47be9922312b68a4227fada96buzbee while (true) { 1090862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = iterator.Next(); 10911fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb == NULL) break; 10921fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", 10931fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id, 10941fd3346740dfb7f47be9922312b68a4227fada96buzbee block_type_names[bb->block_type], 10951fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->start_offset, 10961fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, 10971fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? "" : " empty"); 10981fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->taken) { 10991fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << " Taken branch: block " << bb->taken->id 11001fd3346740dfb7f47be9922312b68a4227fada96buzbee << "(0x" << std::hex << bb->taken->start_offset << ")"; 11011fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11021fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb->fall_through) { 11031fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << " Fallthrough : block " << bb->fall_through->id 11041fd3346740dfb7f47be9922312b68a4227fada96buzbee << " (0x" << std::hex << bb->fall_through->start_offset << ")"; 11051fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11061fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11071fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11081fd3346740dfb7f47be9922312b68a4227fada96buzbee 11091fd3346740dfb7f47be9922312b68a4227fada96buzbee/* 11101fd3346740dfb7f47be9922312b68a4227fada96buzbee * Build an array of location records for the incoming arguments. 11111fd3346740dfb7f47be9922312b68a4227fada96buzbee * Note: one location record per word of arguments, with dummy 11121fd3346740dfb7f47be9922312b68a4227fada96buzbee * high-word loc for wide arguments. Also pull up any following 11131fd3346740dfb7f47be9922312b68a4227fada96buzbee * MOVE_RESULT and incorporate it into the invoke. 11141fd3346740dfb7f47be9922312b68a4227fada96buzbee */ 11151fd3346740dfb7f47be9922312b68a4227fada96buzbeeCallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, 11162ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom bool is_range) { 1117862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee CallInfo* info = static_cast<CallInfo*>(arena_->NewMem(sizeof(CallInfo), true, 1118862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator::kAllocMisc)); 11191fd3346740dfb7f47be9922312b68a4227fada96buzbee MIR* move_result_mir = FindMoveResult(bb, mir); 11201fd3346740dfb7f47be9922312b68a4227fada96buzbee if (move_result_mir == NULL) { 11211fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result.location = kLocInvalid; 11221fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 11231fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result = GetRawDest(move_result_mir); 11241fd3346740dfb7f47be9922312b68a4227fada96buzbee move_result_mir->meta.original_opcode = move_result_mir->dalvikInsn.opcode; 11251fd3346740dfb7f47be9922312b68a4227fada96buzbee move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); 11261fd3346740dfb7f47be9922312b68a4227fada96buzbee } 11271fd3346740dfb7f47be9922312b68a4227fada96buzbee info->num_arg_words = mir->ssa_rep->num_uses; 11281fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> 1129862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee (arena_->NewMem(sizeof(RegLocation) * info->num_arg_words, false, 1130862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 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) { 1144862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee BasicBlock* bb = static_cast<BasicBlock*>(arena_->NewMem(sizeof(BasicBlock), true, 1145862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator::kAllocBB)); 1146862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->block_type = block_type; 1147862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->id = block_id; 1148862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // TUNING: better estimate of the exit block predecessors? 1149df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom bb->predecessors = new (arena_) GrowableArray<BasicBlock*>(arena_, 1150df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom (block_type == kExitBlock) ? 2048 : 2, 1151df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom kGrowableArrayPredecessors); 1152862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->successor_block_list.block_list_type = kNotUsed; 1153862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_id_map_.Put(block_id, block_id); 1154862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return bb; 1155862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} 11561fd3346740dfb7f47be9922312b68a4227fada96buzbee 1157311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} // namespace art 1158