mir_graph.cc revision 55fff044d3a4f7196098e25bab1dad106d9b54a2
1311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 2311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Copyright (C) 2013 The Android Open Source Project 3311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 4311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 5311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * you may not use this file except in compliance with the License. 6311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * You may obtain a copy of the License at 7311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 8311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * http://www.apache.org/licenses/LICENSE-2.0 9311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 10311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Unless required by applicable law or agreed to in writing, software 11311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * distributed under the License is distributed on an "AS IS" BASIS, 12311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * See the License for the specific language governing permissions and 14311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * limitations under the License. 15311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 16311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 17f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray#include "mir_graph.h" 18f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray 19f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray#include <inttypes.h> 2044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler#include <queue> 21f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray 226282dc12440a2072dc06a616160027ff21bd895eIan Rogers#include "base/stl_util.h" 23311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "compiler_internals.h" 24311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#include "dex_file-inl.h" 2529a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers#include "dex_instruction-inl.h" 2695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko#include "dex/global_value_numbering.h" 275816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_to_method_inliner_map.h" 285816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko#include "dex/quick/dex_file_method_inliner.h" 29f3e2cc4a38389aa75eb8ee3973a535254bf1c8d2Nicolas Geoffray#include "leb128.h" 302469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler#include "pass_driver_me_post_opt.h" 31622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko#include "utils/scoped_arena_containers.h" 325816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 33311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeenamespace art { 34311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 35311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee#define MAX_PATTERN_LEN 5 36311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 371fd3346740dfb7f47be9922312b68a4227fada96buzbeeconst char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { 381fd3346740dfb7f47be9922312b68a4227fada96buzbee "Phi", 391fd3346740dfb7f47be9922312b68a4227fada96buzbee "Copy", 401fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplFloat", 411fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgFloat", 421fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmplDouble", 431fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpgDouble", 441fd3346740dfb7f47be9922312b68a4227fada96buzbee "FusedCmpLong", 451fd3346740dfb7f47be9922312b68a4227fada96buzbee "Nop", 461fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpNullCheck", 471fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpRangeCheck", 481fd3346740dfb7f47be9922312b68a4227fada96buzbee "OpDivZeroCheck", 491fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check1", 501fd3346740dfb7f47be9922312b68a4227fada96buzbee "Check2", 511fd3346740dfb7f47be9922312b68a4227fada96buzbee "Select", 52d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "ConstVector", 53d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "MoveVector", 54d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedMultiply", 55d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedAddition", 56d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedSubtract", 57d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedShiftLeft", 58d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedSignedShiftRight", 59d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedUnsignedShiftRight", 60d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedAnd", 61d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedOr", 62d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedXor", 63d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedAddReduce", 64d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedReduce", 65d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell "PackedSet", 6660bfe7b3e8f00f0a8ef3f5d8716adfdf86b71f43Udayan Banerji "ReserveVectorRegisters", 6760bfe7b3e8f00f0a8ef3f5d8716adfdf86b71f43Udayan Banerji "ReturnVectorRegisters", 681fd3346740dfb7f47be9922312b68a4227fada96buzbee}; 691fd3346740dfb7f47be9922312b68a4227fada96buzbee 70862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeMIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) 711fd3346740dfb7f47be9922312b68a4227fada96buzbee : reg_location_(NULL), 721fd3346740dfb7f47be9922312b68a4227fada96buzbee cu_(cu), 73311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_base_vregs_(NULL), 74311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_subscripts_(NULL), 75311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee vreg_to_ssa_map_(NULL), 76311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ssa_last_defs_(NULL), 77311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee is_constant_v_(NULL), 78311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee constant_values_(NULL), 79862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee use_counts_(arena, 256, kGrowableArrayMisc), 80862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee raw_use_counts_(arena, 256, kGrowableArrayMisc), 81311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_reachable_blocks_(0), 824896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler max_num_reachable_blocks_(0), 83862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_order_(NULL), 84862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dfs_post_order_(NULL), 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee dom_post_order_traversal_(NULL), 8644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler topological_order_(nullptr), 8755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_ends_(nullptr), 8855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_indexes_(nullptr), 8955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_head_stack_(nullptr), 90311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee i_dom_list_(NULL), 91311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_block_matrix_(NULL), 92bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_scoped_alloc_(), 93bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_insn_data_(nullptr), 94bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_bit_vector_size_(0u), 95bfea9c29e809e04bde4a46591fea64c5a7b922fbVladimir Marko temp_bit_vector_(nullptr), 9695a059793c4c194f026afc74c713cc295d75d91aVladimir Marko temp_gvn_(), 97862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_(arena, 100, kGrowableArrayBlockList), 98311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee try_block_addr_(NULL), 99311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee entry_block_(NULL), 100311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee exit_block_(NULL), 101311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee num_blocks_(0), 102311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_(NULL), 103b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), 104311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_(kInvalidEntry), 105311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_(kInvalidEntry), 106311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_(0), 107311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_(NULL), 1081fd3346740dfb7f47be9922312b68a4227fada96buzbee num_ssa_regs_(0), 1091fd3346740dfb7f47be9922312b68a4227fada96buzbee method_sreg_(0), 110862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee checkstats_(NULL), 112b48819db07f9a0992a72173380c24249d7fc648abuzbee arena_(arena), 113b48819db07f9a0992a72173380c24249d7fc648abuzbee backward_branches_(0), 114da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru forward_branches_(0), 115da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru compiler_temps_(arena, 6, kGrowableArrayMisc), 116da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru num_non_special_compiler_temps_(0), 117b1f1d642093418612c0a27ce4203b421bb6eb767buzbee max_available_non_special_compiler_temps_(0), 118be0e546730e532ef0987cd4bde2c6f5a1b14dd2aVladimir Marko punt_to_interpreter_(false), 1193d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko merged_df_flags_(0u), 120be0e546730e532ef0987cd4bde2c6f5a1b14dd2aVladimir Marko ifield_lowering_infos_(arena, 0u), 121f096aad9203d7c50b2f9cbe1c1215a50c265a059Vladimir Marko sfield_lowering_infos_(arena, 0u), 12204f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin method_lowering_infos_(arena, 0u), 12304f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin gen_suspend_test_list_(arena, 0u) { 124862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); 125da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru max_available_special_compiler_temps_ = std::abs(static_cast<int>(kVRegNonSpecialTempBaseReg)) 126da7a69b3fa7bb22d087567364b7eb5a75824efd8Razvan A Lupusoru - std::abs(static_cast<int>(kVRegTempBaseReg)); 127311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 128311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 1296282dc12440a2072dc06a616160027ff21bd895eIan RogersMIRGraph::~MIRGraph() { 1306282dc12440a2072dc06a616160027ff21bd895eIan Rogers STLDeleteElements(&m_units_); 1316282dc12440a2072dc06a616160027ff21bd895eIan Rogers} 1326282dc12440a2072dc06a616160027ff21bd895eIan Rogers 133311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 134311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Parse an instruction, return the length of the instruction 135311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 13629a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogersint MIRGraph::ParseInsn(const uint16_t* code_ptr, MIR::DecodedInstruction* decoded_instruction) { 13729a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers const Instruction* inst = Instruction::At(code_ptr); 13829a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->opcode = inst->Opcode(); 13929a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vA = inst->HasVRegA() ? inst->VRegA() : 0; 14029a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vB = inst->HasVRegB() ? inst->VRegB() : 0; 14129a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vB_wide = inst->HasWideVRegB() ? inst->WideVRegB() : 0; 14229a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers decoded_instruction->vC = inst->HasVRegC() ? inst->VRegC() : 0; 14329a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers if (inst->HasVarArgs()) { 14429a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers inst->GetVarArgs(decoded_instruction->arg); 14529a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers } 14629a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers return inst->SizeInCodeUnits(); 147311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 148311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 149311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 150311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Split an existing block from the specified code offset into two */ 1510d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, 1522ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { 1530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_GT(code_offset, orig_block->start_offset); 154311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee MIR* insn = orig_block->first_mir_insn; 1550d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee MIR* prev = NULL; 156311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (insn) { 157311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->offset == code_offset) break; 1580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee prev = insn; 159311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn = insn->next; 160311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 161311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn == NULL) { 162311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Break split failed"; 163311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1648512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); 165862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bottom_block); 166311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 167311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->start_offset = code_offset; 168311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->first_mir_insn = insn; 169311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->last_mir_insn = orig_block->last_mir_insn; 170311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 171311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* If this block was terminated by a return, the flag needs to go with the bottom block */ 172311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->terminated_by_return = orig_block->terminated_by_return; 173311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee orig_block->terminated_by_return = false; 174311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 175311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the taken path */ 176311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->taken = orig_block->taken; 1770d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->taken != NullBasicBlockId) { 1780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->taken = NullBasicBlockId; 1790d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); 1800d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Delete(orig_block->id); 1810d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_taken->predecessors->Insert(bottom_block->id); 182311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 183311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 184311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the fallthrough path */ 185311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bottom_block->fall_through = orig_block->fall_through; 1860d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->fall_through = bottom_block->id; 1870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->predecessors->Insert(orig_block->id); 1880d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bottom_block->fall_through != NullBasicBlockId) { 1890d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); 1900d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Delete(orig_block->id); 1910d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb_fall_through->predecessors->Insert(bottom_block->id); 192311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 193311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 194311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Handle the successor list */ 1950d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (orig_block->successor_block_list_type != kNotUsed) { 1960d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_block_list_type = orig_block->successor_block_list_type; 1970d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bottom_block->successor_blocks = orig_block->successor_blocks; 1980d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->successor_block_list_type = kNotUsed; 199989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar orig_block->successor_blocks = nullptr; 2000d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); 201311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 2028512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* successor_block_info = iterator.Next(); 203989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar if (successor_block_info == nullptr) break; 2048512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* bb = GetBasicBlock(successor_block_info->block); 205989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar if (bb != nullptr) { 206989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar bb->predecessors->Delete(orig_block->id); 207989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar bb->predecessors->Insert(bottom_block->id); 208989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar } 209311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 210311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 211311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 2120d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee orig_block->last_mir_insn = prev; 2133aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler prev->next = nullptr; 214311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 215311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 216311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Update the immediate predecessor block pointer so that outgoing edges 217311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * can be applied to the proper block. 218311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 219311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (immed_pred_block_p) { 220311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(*immed_pred_block_p, orig_block); 221311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *immed_pred_block_p = bottom_block; 222311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 223b48819db07f9a0992a72173380c24249d7fc648abuzbee 224b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate dex instructions in the bottom block with the new container. 2254376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != nullptr); 2264376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn != orig_block->first_mir_insn); 2274376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(insn == bottom_block->first_mir_insn); 2284376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(insn->offset, bottom_block->start_offset); 2294376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || 2302ab40eb3c23559205ac7b9b039bd749458e8a761Jean Christophe Beyler !MIR::DecodedInstruction::IsPseudoMirOp(insn->dalvikInsn.opcode)); 2314376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); 2324376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko MIR* p = insn; 2334376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 2344376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko while (p != bottom_block->last_mir_insn) { 2354376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko p = p->next; 2364376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK(p != nullptr); 2373aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler p->bb = bottom_block->id; 238b48819db07f9a0992a72173380c24249d7fc648abuzbee int opcode = p->dalvikInsn.opcode; 239b48819db07f9a0992a72173380c24249d7fc648abuzbee /* 240b48819db07f9a0992a72173380c24249d7fc648abuzbee * Some messiness here to ensure that we only enter real opcodes and only the 241b48819db07f9a0992a72173380c24249d7fc648abuzbee * first half of a potentially throwing instruction that has been split into 2424376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * CHECK and work portions. Since the 2nd half of a split operation is always 2434376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko * the first in a BasicBlock, we can't hit it here. 244b48819db07f9a0992a72173380c24249d7fc648abuzbee */ 2452ab40eb3c23559205ac7b9b039bd749458e8a761Jean Christophe Beyler if ((opcode == kMirOpCheck) || !MIR::DecodedInstruction::IsPseudoMirOp(opcode)) { 2464376c87eb45b287fad77a16738e76ba28956ab7dVladimir Marko DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); 247b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(p->offset, bottom_block->id); 248b48819db07f9a0992a72173380c24249d7fc648abuzbee } 249b48819db07f9a0992a72173380c24249d7fc648abuzbee } 250b48819db07f9a0992a72173380c24249d7fc648abuzbee 251311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bottom_block; 252311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 253311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 254311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* 255311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Given a code offset, find out the block that starts with it. If the offset 256311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is in the middle of an existing block, split it into two. If immed_pred_block_p 257311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * is not non-null and is the block being split, update *immed_pred_block_p to 258311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * point to the bottom block so that outgoing edges can be set up properly 259311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (by the caller) 260311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Utilizes a map for fast lookup of the typical cases. 261311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 2620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, 2632ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom BasicBlock** immed_pred_block_p) { 264bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee if (code_offset >= cu_->code_item->insns_size_in_code_units_) { 265311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return NULL; 266311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 267b48819db07f9a0992a72173380c24249d7fc648abuzbee 268b48819db07f9a0992a72173380c24249d7fc648abuzbee int block_id = dex_pc_to_block_map_.Get(code_offset); 269b48819db07f9a0992a72173380c24249d7fc648abuzbee BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); 270b48819db07f9a0992a72173380c24249d7fc648abuzbee 271b48819db07f9a0992a72173380c24249d7fc648abuzbee if ((bb != NULL) && (bb->start_offset == code_offset)) { 272b48819db07f9a0992a72173380c24249d7fc648abuzbee // Does this containing block start with the desired instruction? 273bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee return bb; 274bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee } 275311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 276b48819db07f9a0992a72173380c24249d7fc648abuzbee // No direct hit. 277b48819db07f9a0992a72173380c24249d7fc648abuzbee if (!create) { 278b48819db07f9a0992a72173380c24249d7fc648abuzbee return NULL; 279b48819db07f9a0992a72173380c24249d7fc648abuzbee } 280b48819db07f9a0992a72173380c24249d7fc648abuzbee 281b48819db07f9a0992a72173380c24249d7fc648abuzbee if (bb != NULL) { 282b48819db07f9a0992a72173380c24249d7fc648abuzbee // The target exists somewhere in an existing block. 283b48819db07f9a0992a72173380c24249d7fc648abuzbee return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : NULL); 284311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 285311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 286b48819db07f9a0992a72173380c24249d7fc648abuzbee // Create a new block. 287862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = NewMemBB(kDalvikByteCode, num_blocks_++); 288862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(bb); 289311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset = code_offset; 290b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(bb->start_offset, bb->id); 291311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return bb; 292311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 293311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 294b48819db07f9a0992a72173380c24249d7fc648abuzbee 295311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Identify code range in try blocks and set up the empty catch blocks */ 2962ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ProcessTryCatchBlocks() { 297311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int tries_size = current_code_item_->tries_size_; 2980d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset offset; 299311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 300311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (tries_size == 0) { 301311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 302311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 303311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 304311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < tries_size; i++) { 305311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const DexFile::TryItem* pTry = 306311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DexFile::GetTryItems(*current_code_item_, i); 3070d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset start_offset = pTry->start_addr_; 3080d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset end_offset = start_offset + pTry->insn_count_; 309311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (offset = start_offset; offset < end_offset; offset++) { 310862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(offset); 311311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 312311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 313311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 3148512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Iterate over each of the handlers to enqueue the empty Catch blocks. 315311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); 316311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); 317311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (uint32_t idx = 0; idx < handlers_size; idx++) { 318311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(handlers_ptr); 319311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (; iterator.HasNext(); iterator.Next()) { 320311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee uint32_t address = iterator.GetHandlerAddress(); 321311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(address, false /* split */, true /*create*/, 322311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 323311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 324311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee handlers_ptr = iterator.EndDataPointer(); 325311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 326311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 327311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 328e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Markobool MIRGraph::IsBadMonitorExitCatch(NarrowDexOffset monitor_exit_offset, 329e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko NarrowDexOffset catch_offset) { 330e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // Catches for monitor-exit during stack unwinding have the pattern 331e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // move-exception (move)* (goto)? monitor-exit throw 332e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // In the currently generated dex bytecode we see these catching a bytecode range including 333e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // either its own or an identical monitor-exit, http://b/15745363 . This function checks if 334e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // it's the case for a given monitor-exit and catch block so that we can ignore it. 335e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // (We don't want to ignore all monitor-exit catches since one could enclose a synchronized 336e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // block in a try-block and catch the NPE, Error or Throwable and we should let it through; 337e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // even though a throwing monitor-exit certainly indicates a bytecode error.) 338e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko const Instruction* monitor_exit = Instruction::At(cu_->code_item->insns_ + monitor_exit_offset); 339e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko DCHECK(monitor_exit->Opcode() == Instruction::MONITOR_EXIT); 340e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko int monitor_reg = monitor_exit->VRegA_11x(); 341e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko const Instruction* check_insn = Instruction::At(cu_->code_item->insns_ + catch_offset); 342e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko DCHECK(check_insn->Opcode() == Instruction::MOVE_EXCEPTION); 343e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko if (check_insn->VRegA_11x() == monitor_reg) { 344e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // Unexpected move-exception to the same register. Probably not the pattern we're looking for. 345e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko return false; 346e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko } 347e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko check_insn = check_insn->Next(); 348e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko while (true) { 349e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko int dest = -1; 350e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko bool wide = false; 351e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko switch (check_insn->Opcode()) { 352e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_WIDE: 353e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko wide = true; 354e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // Intentional fall-through. 355e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_OBJECT: 356e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE: 357e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko dest = check_insn->VRegA_12x(); 358e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko break; 359e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko 360e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_WIDE_FROM16: 361e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko wide = true; 362e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // Intentional fall-through. 363e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_OBJECT_FROM16: 364e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_FROM16: 365e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko dest = check_insn->VRegA_22x(); 366e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko break; 367e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko 368e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_WIDE_16: 369e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko wide = true; 370e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // Intentional fall-through. 371e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_OBJECT_16: 372e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::MOVE_16: 373e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko dest = check_insn->VRegA_32x(); 374e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko break; 375e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko 376e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::GOTO: 377e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::GOTO_16: 378e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko case Instruction::GOTO_32: 379e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko check_insn = check_insn->RelativeAt(check_insn->GetTargetOffset()); 380e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // Intentional fall-through. 381e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko default: 382e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko return check_insn->Opcode() == Instruction::MONITOR_EXIT && 383e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko check_insn->VRegA_11x() == monitor_reg; 384e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko } 385e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko 386e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko if (dest == monitor_reg || (wide && dest + 1 == monitor_reg)) { 387e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko return false; 388e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko } 389e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko 390e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko check_insn = check_insn->Next(); 391e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko } 392e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko} 393e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko 394311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kBranch flag */ 3950d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 3960d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, const uint16_t* code_ptr, 3972ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_end) { 3980d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DexOffset target = cur_offset; 399311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee switch (insn->dalvikInsn.opcode) { 400311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO: 401311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_16: 402311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::GOTO_32: 403311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vA; 404311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 405311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQ: 406311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NE: 407311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LT: 408311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GE: 409311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GT: 410311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LE: 411311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 412311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vC; 413311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 414311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_EQZ: 415311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_NEZ: 416311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LTZ: 417311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GEZ: 418311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_GTZ: 419311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee case Instruction::IF_LEZ: 420311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->conditional_branch = true; 421311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target += insn->dalvikInsn.vB; 422311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee break; 423311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee default: 424311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; 425311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 426b48819db07f9a0992a72173380c24249d7fc648abuzbee CountBranch(target); 4278512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* taken_block = FindBlock(target, /* split */ true, /* create */ true, 428311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ &cur_block); 4290d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = taken_block->id; 4300d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee taken_block->predecessors->Insert(cur_block->id); 431311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 432311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Always terminate the current block for conditional branches */ 433311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kContinue) { 4342469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler BasicBlock* fallthrough_block = FindBlock(cur_offset + width, 435311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 436311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * If the method is processed 437311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * in sequential order from the 438311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * beginning, we don't need to 439311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * specify split for continue 440311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * blocks. However, this 441311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * routine can be called by 442311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * compileLoop, which starts 443311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * parsing the method from an 444311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * arbitrary address in the 445311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * method body. 446311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 447311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 448311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ 449311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee true, 450311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ 451311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee &cur_block); 4520d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 4530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 454311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (code_ptr < code_end) { 4552724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 456311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 457311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 458311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 459311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 460311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 461311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kSwitch flag */ 46217189ac098b2f156713db1821b49db7b2f018bbebuzbeeBasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 46317189ac098b2f156713db1821b49db7b2f018bbebuzbee int width, int flags) { 464311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* switch_data = 465311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); 466311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int size; 467311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* keyTable; 468311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const int* target_table; 469311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int i; 470311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int first_key; 471311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 472311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 473311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Packed switch data format: 474311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0100 magic value 475311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table 476311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int first_key first (and lowest) switch case value 477311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 478311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 479311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (4+size*2) 16-bit code units. 480311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 481311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { 482311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 483311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kPackedSwitchSignature)); 484311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 485311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key = switch_data[2] | (switch_data[3] << 16); 486311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[4]); 4878512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler keyTable = NULL; // Make the compiler happy. 488311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 489311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Sparse switch data format: 490311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort ident = 0x0200 magic value 491311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * ushort size number of entries in the table; > 0 492311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int keys[size] keys, sorted low-to-high; 32-bit aligned 493311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * int targets[size] branch targets, relative to switch opcode 494311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * 495311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Total size is (2+size*4) 16-bit code units. 496311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 497311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 498311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK_EQ(static_cast<int>(switch_data[0]), 499311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee static_cast<int>(Instruction::kSparseSwitchSignature)); 500311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee size = switch_data[1]; 501311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee keyTable = reinterpret_cast<const int*>(&switch_data[2]); 502311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); 5038512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler first_key = 0; // To make the compiler happy. 504311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 505311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 5060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 507311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 5080d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 509311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 5100d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_block_list_type = 5110d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; 5120d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks = 513df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); 514311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 515311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (i = 0; i < size; i++) { 5168512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* case_block = FindBlock(cur_offset + target_table[i], /* split */ true, 517311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* create */ true, /* immed_pred_block_p */ &cur_block); 5188512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* successor_block_info = 519f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), 52083cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocSuccessor)); 5210d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = case_block->id; 522311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = 523311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? 524311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee first_key + i : keyTable[i]; 5250d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 5260d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee case_block->predecessors->Insert(cur_block->id); 527311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 528311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 529311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Fall-through case */ 530df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, 531df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom /* create */ true, /* immed_pred_block_p */ NULL); 5320d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = fallthrough_block->id; 5330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee fallthrough_block->predecessors->Insert(cur_block->id); 53417189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 535311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 536311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 537311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Process instructions with the kThrow flag */ 5380d82948094d9a198e01aa95f64012bdedd5b6fc9buzbeeBasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, 5390d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee int width, int flags, ArenaBitVector* try_block_addr, 5402ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom const uint16_t* code_ptr, const uint16_t* code_end) { 541862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool in_try_block = try_block_addr->IsBitSet(cur_offset); 54217189ac098b2f156713db1821b49db7b2f018bbebuzbee bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); 54317189ac098b2f156713db1821b49db7b2f018bbebuzbee bool build_all_edges = 54417189ac098b2f156713db1821b49db7b2f018bbebuzbee (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; 545311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 546311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* In try block */ 547311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (in_try_block) { 548311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee CatchHandlerIterator iterator(*current_code_item_, cur_offset); 549311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 5500d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (cur_block->successor_block_list_type != kNotUsed) { 551311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 552311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(FATAL) << "Successor block list already in use: " 5530d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << static_cast<int>(cur_block->successor_block_list_type); 554311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 555311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 55602c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom for (; iterator.HasNext(); iterator.Next()) { 5578512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, 558311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false /* creat */, NULL /* immed_pred_block_p */); 559e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko if (insn->dalvikInsn.opcode == Instruction::MONITOR_EXIT && 560e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko IsBadMonitorExitCatch(insn->offset, catch_block->start_offset)) { 561e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko // Don't allow monitor-exit to catch its own exception, http://b/15745363 . 562e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko continue; 563e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko } 564e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko if (cur_block->successor_block_list_type == kNotUsed) { 565e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko cur_block->successor_block_list_type = kCatch; 566e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko cur_block->successor_blocks = new (arena_) GrowableArray<SuccessorBlockInfo*>( 567e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko arena_, 2, kGrowableArraySuccessorBlocks); 568e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko } 569311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catch_block->catch_entry = true; 570311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (kIsDebugBuild) { 571311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee catches_.insert(catch_block->start_offset); 572311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 5738512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 57483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 5750d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee successor_block_info->block = catch_block->id; 576311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key = iterator.GetHandlerTypeIndex(); 5770d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->successor_blocks->Insert(successor_block_info); 5780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee catch_block->predecessors->Insert(cur_block->id); 579311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 580e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko in_try_block = (cur_block->successor_block_list_type != kNotUsed); 581e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko } 582e8ae81453e1d6c19d7db2001a1e7b1849f74241cVladimir Marko if (!in_try_block && build_all_edges) { 5838512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* eh_block = NewMemBB(kExceptionHandling, num_blocks_++); 5840d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->taken = eh_block->id; 585862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(eh_block); 586311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee eh_block->start_offset = cur_offset; 5870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee eh_block->predecessors->Insert(cur_block->id); 588311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 589311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 59017189ac098b2f156713db1821b49db7b2f018bbebuzbee if (is_throw) { 591311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->explicit_throw = true; 5922724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (code_ptr < code_end) { 5938512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Force creation of new block following THROW via side-effect. 594311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FindBlock(cur_offset + width, /* split */ false, /* create */ true, 595311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* immed_pred_block_p */ NULL); 596311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 597311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (!in_try_block) { 598311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // Don't split a THROW that can't rethrow - we're done. 599311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return cur_block; 600311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 601311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 602311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 60317189ac098b2f156713db1821b49db7b2f018bbebuzbee if (!build_all_edges) { 60417189ac098b2f156713db1821b49db7b2f018bbebuzbee /* 60517189ac098b2f156713db1821b49db7b2f018bbebuzbee * Even though there is an exception edge here, control cannot return to this 60617189ac098b2f156713db1821b49db7b2f018bbebuzbee * method. Thus, for the purposes of dataflow analysis and optimization, we can 60717189ac098b2f156713db1821b49db7b2f018bbebuzbee * ignore the edge. Doing this reduces compile time, and increases the scope 60817189ac098b2f156713db1821b49db7b2f018bbebuzbee * of the basic-block level optimization pass. 60917189ac098b2f156713db1821b49db7b2f018bbebuzbee */ 61017189ac098b2f156713db1821b49db7b2f018bbebuzbee return cur_block; 61117189ac098b2f156713db1821b49db7b2f018bbebuzbee } 61217189ac098b2f156713db1821b49db7b2f018bbebuzbee 613311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 614311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Split the potentially-throwing instruction into two parts. 615311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The first half will be a pseudo-op that captures the exception 616311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * edges and terminates the basic block. It always falls through. 617311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Then, create a new basic block that begins with the throwing instruction 618311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (minus exceptions). Note: this new basic block must NOT be entered into 619311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the block_map. If the potentially-throwing instruction is the target of a 620311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * future branch, we need to find the check psuedo half. The new 621311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * basic block containing the work portion of the instruction should 622311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * only be entered via fallthrough from the block containing the 623311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * pseudo exception edge MIR. Note also that this new block is 624311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * not automatically terminated after the work portion, and may 625311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * contain following instructions. 626b48819db07f9a0992a72173380c24249d7fc648abuzbee * 627b48819db07f9a0992a72173380c24249d7fc648abuzbee * Note also that the dex_pc_to_block_map_ entry for the potentially 628b48819db07f9a0992a72173380c24249d7fc648abuzbee * throwing instruction will refer to the original basic block. 629311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 6302469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler BasicBlock* new_block = NewMemBB(kDalvikByteCode, num_blocks_++); 631862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(new_block); 632311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee new_block->start_offset = insn->offset; 6330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = new_block->id; 6340d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee new_block->predecessors->Insert(cur_block->id); 6353aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler MIR* new_insn = NewMIR(); 636311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee *new_insn = *insn; 63735ba7f3a78d38885ec54e61ed060d2771eeceea7buzbee insn->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpCheck); 6388512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Associate the two halves. 639311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->meta.throw_insn = new_insn; 640cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler new_block->AppendMIR(new_insn); 641311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return new_block; 642311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 643311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 644311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ 645311ca169f4727d46a55bdc8dfa0059719fa72b65buzbeevoid MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, 6468b2c0b9abc3f520495f4387ea040132ba85cae69Ian Rogers InvokeType invoke_type, uint16_t class_def_idx, 6472ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { 648311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_ = code_item; 649311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee method_stack_.push_back(std::make_pair(current_method_, current_offset_)); 650311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_method_ = m_units_.size(); 651311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ = 0; 652311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: will need to snapshot stack image and use that as the mir context identification. 653311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), 6542730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko dex_file, current_code_item_, class_def_idx, method_idx, access_flags, 6552730db03beee4d6687ddfb5000c33c0370fbc6ebVladimir Marko cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); 656311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_ptr = current_code_item_->insns_; 657311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee const uint16_t* code_end = 658311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; 659311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 660311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: need to rework expansion of block list & try_block_addr when inlining activated. 661b48819db07f9a0992a72173380c24249d7fc648abuzbee // TUNING: use better estimate of basic blocks for following resize. 662862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); 663b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_); 664bd663de599b16229085759366c56e2ed5a1dc7ecbuzbee 665311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: replace with explicit resize routine. Using automatic extension side effect for now. 666862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); 667862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); 668311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 669311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // If this is the first method, set up default entry and exit blocks. 670311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (current_method_ == 0) { 671311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(entry_block_ == NULL); 672311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(exit_block_ == NULL); 6734439596b00c91f565370bf0813cc2f9165093693Andreas Gampe DCHECK_EQ(num_blocks_, 0U); 6740d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Use id 0 to represent a null block. 6750d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); 6760d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(null_block->id, NullBasicBlockId); 6770d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee null_block->hidden = true; 6780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee block_list_.Insert(null_block); 679862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); 680862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(entry_block_); 6810d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_ = NewMemBB(kExitBlock, num_blocks_++); 682862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(exit_block_); 683311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. 684311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->dex_file = &dex_file; 685311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->class_def_idx = class_def_idx; 686311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->method_idx = method_idx; 687311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->access_flags = access_flags; 688311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->invoke_type = invoke_type; 689311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); 690311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_ins = current_code_item_->ins_size_; 691311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_regs = current_code_item_->registers_size_ - cu_->num_ins; 692311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_outs = current_code_item_->outs_size_; 693311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->num_dalvik_registers = current_code_item_->registers_size_; 694311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->insns = current_code_item_->insns_; 695311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cu_->code_item = current_code_item_; 696311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else { 697311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; 698311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 699311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Will need to manage storage for ins & outs, push prevous state and update 700311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * insert point. 701311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 702311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 703311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 704311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Current block to record parsed instructions */ 7058512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); 7060d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK_EQ(current_offset_, 0U); 707311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->start_offset = current_offset_; 708862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_list_.Insert(cur_block); 7090d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, insert at the insert point rather than entry block. 7100d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee entry_block_->fall_through = cur_block->id; 7110d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->predecessors->Insert(entry_block_->id); 712311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7133d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko /* Identify code range in try blocks and set up the empty catch blocks */ 714311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ProcessTryCatchBlocks(); 715311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7163d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko uint64_t merged_df_flags = 0u; 7173d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko 718311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Parse all instructions and put them into containing basic blocks */ 719311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (code_ptr < code_end) { 7203aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler MIR *insn = NewMIR(); 721311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->offset = current_offset_; 722311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee insn->m_unit_index = current_method_; 723311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int width = ParseInsn(code_ptr, &insn->dalvikInsn); 724311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee Instruction::Code opcode = insn->dalvikInsn.opcode; 725311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_ != NULL) { 726311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee opcode_count_[static_cast<int>(opcode)]++; 727311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 728311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 729311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int flags = Instruction::FlagsOf(insn->dalvikInsn.opcode); 730b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int verify_flags = Instruction::VerifyFlagsOf(insn->dalvikInsn.opcode); 731311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 732cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler uint64_t df_flags = GetDataFlowAttributes(insn); 7333d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko merged_df_flags |= df_flags; 734311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 735311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (df_flags & DF_HAS_DEFS) { 736311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; 737311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 738311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 7391da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee if (df_flags & DF_LVN) { 7401da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee cur_block->use_lvn = true; // Run local value numbering on this basic block. 7411da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee } 7421da1e2fceb0030b4b76b43510b1710a9613e0c2ebuzbee 7438512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Check for inline data block signatures. 7442724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (opcode == Instruction::NOP) { 7452724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. 7462724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { 7472724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. 7482724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee uint16_t following_raw_instruction = code_ptr[1]; 7492724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || 7502724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kPackedSwitchSignature) || 7512724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee (following_raw_instruction == Instruction::kArrayDataSignature)) { 7522724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); 7532724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 7542724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 7552724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee if (width == 1) { 7562724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // It is a simple nop - treat normally. 757cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler cur_block->AppendMIR(insn); 7582724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 7590d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId); 7600d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->taken == NullBasicBlockId); 7612724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee // Unreachable instruction, mark for no continuation. 7622724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee flags &= ~Instruction::kContinue; 7632724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 7642724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } else { 765cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler cur_block->AppendMIR(insn); 7662724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee } 7672724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 768b48819db07f9a0992a72173380c24249d7fc648abuzbee // Associate the starting dex_pc for this opcode with its containing basic block. 769b48819db07f9a0992a72173380c24249d7fc648abuzbee dex_pc_to_block_map_.Put(insn->offset, cur_block->id); 770b48819db07f9a0992a72173380c24249d7fc648abuzbee 7712724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee code_ptr += width; 7722724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee 773311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (flags & Instruction::kBranch) { 774311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanBranch(cur_block, insn, current_offset_, 775311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee width, flags, code_ptr, code_end); 776311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kReturn) { 777311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block->terminated_by_return = true; 7780d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = exit_block_->id; 7790d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee exit_block_->predecessors->Insert(cur_block->id); 780311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 781311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Terminate the current block if there are instructions 782311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * afterwards. 783311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 784311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (code_ptr < code_end) { 785311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 786311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * Create a fallthrough block for real instructions 787311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * (incl. NOP). 788311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 7892724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee FindBlock(current_offset_ + width, /* split */ false, /* create */ true, 7902724776ad521eebb1c7f0e4be56d6e6ab4764f86buzbee /* immed_pred_block_p */ NULL); 791311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 792311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kThrow) { 793311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, 794311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee code_ptr, code_end); 795311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (flags & Instruction::kSwitch) { 79617189ac098b2f156713db1821b49db7b2f018bbebuzbee cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); 797311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 798b1f1d642093418612c0a27ce4203b421bb6eb767buzbee if (verify_flags & Instruction::kVerifyVarArgRange) { 799b1f1d642093418612c0a27ce4203b421bb6eb767buzbee /* 800b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * The Quick backend's runtime model includes a gap between a method's 801b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * argument ("in") vregs and the rest of its vregs. Handling a range instruction 802b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * which spans the gap is somewhat complicated, and should not happen 803b1f1d642093418612c0a27ce4203b421bb6eb767buzbee * in normal usage of dx. Punt to the interpreter. 804b1f1d642093418612c0a27ce4203b421bb6eb767buzbee */ 805b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int first_reg_in_range = insn->dalvikInsn.vC; 806b1f1d642093418612c0a27ce4203b421bb6eb767buzbee int last_reg_in_range = first_reg_in_range + insn->dalvikInsn.vA - 1; 807b1f1d642093418612c0a27ce4203b421bb6eb767buzbee if (IsInVReg(first_reg_in_range) != IsInVReg(last_reg_in_range)) { 808b1f1d642093418612c0a27ce4203b421bb6eb767buzbee punt_to_interpreter_ = true; 809b1f1d642093418612c0a27ce4203b421bb6eb767buzbee } 810b1f1d642093418612c0a27ce4203b421bb6eb767buzbee } 811311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee current_offset_ += width; 8122469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler BasicBlock* next_block = FindBlock(current_offset_, /* split */ false, /* create */ 813311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee false, /* immed_pred_block_p */ NULL); 814311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (next_block) { 815311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* 816311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * The next instruction could be the target of a previously parsed 817311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * forward branch so a block is already created. If the current 818311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * instruction is not an unconditional branch, connect them through 819311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee * the fall-through link. 820311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee */ 8210d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee DCHECK(cur_block->fall_through == NullBasicBlockId || 8220d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == next_block || 8230d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBasicBlock(cur_block->fall_through) == exit_block_); 824311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8250d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { 8260d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee cur_block->fall_through = next_block->id; 8270d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee next_block->predecessors->Insert(cur_block->id); 828311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 829311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee cur_block = next_block; 830311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 831311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 8323d73ba2ce682edfaf41f29521bd6039c6499a1c5Vladimir Marko merged_df_flags_ = merged_df_flags; 8335816ed48bc339c983b40dc493e96b97821ce7966Vladimir Marko 834311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->enable_debug & (1 << kDebugDumpCFG)) { 835311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DumpCFG("/sdcard/1_post_parse_cfg/", true); 836311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 837311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 838311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 8391fd3346740dfb7f47be9922312b68a4227fada96buzbee DumpMIRGraph(); 840311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 841311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 842311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 8432ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ShowOpcodeStats() { 844311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee DCHECK(opcode_count_ != NULL); 845311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "Opcode Count"; 846311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (int i = 0; i < kNumPackedOpcodes; i++) { 847311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (opcode_count_[i] != 0) { 848311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) 849311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee << " " << opcode_count_[i]; 850311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 851311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 852311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 853311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 854cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyleruint64_t MIRGraph::GetDataFlowAttributes(Instruction::Code opcode) { 855cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler DCHECK_LT((size_t) opcode, (sizeof(oat_data_flow_attributes_) / sizeof(oat_data_flow_attributes_[0]))); 856cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler return oat_data_flow_attributes_[opcode]; 857cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler} 858cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler 859cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyleruint64_t MIRGraph::GetDataFlowAttributes(MIR* mir) { 860cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler DCHECK(mir != nullptr); 861cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler Instruction::Code opcode = mir->dalvikInsn.opcode; 862cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler return GetDataFlowAttributes(opcode); 863cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler} 864cc794c3dc5b45601da23fb0d7bc16f9b4ef04065Jean Christophe Beyler 865311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee// TODO: use a configurable base prefix, and adjust callers to supply pass name. 866311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee/* Dump the CFG into a DOT graph */ 867d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beylervoid MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { 868311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee FILE* file; 869a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler static AtomicInteger cnt(0); 870a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler 871a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler // Increment counter to get a unique file number. 872a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler cnt++; 873a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler 874311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); 875311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee ReplaceSpecialChars(fname); 876a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler fname = StringPrintf("%s%s%x%s_%d.dot", dir_prefix, fname.c_str(), 877d0a515562772d7c637160e8779c4f253ee169c3aJean Christophe Beyler GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, 878a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler suffix == nullptr ? "" : suffix, 879a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler cnt.LoadRelaxed()); 880311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee file = fopen(fname.c_str(), "w"); 881311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (file == NULL) { 882311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee return; 883311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 884311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "digraph G {\n"); 885311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 886311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " rankdir=TB\n"); 887311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 888311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; 889311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int idx; 890311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 891311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (idx = 0; idx < num_blocks; idx++) { 892862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int block_idx = all_blocks ? idx : dfs_order_->Get(idx); 8938512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* bb = GetBasicBlock(block_idx); 89425bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru if (bb == NULL) continue; 895311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kDead) continue; 896a8869e60d93ba9eed36a5b53553b7609f58fc05bJean Christophe Beyler if (bb->hidden) continue; 897311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->block_type == kEntryBlock) { 898311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); 899311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExitBlock) { 900311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); 901311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kDalvikByteCode) { 902311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", 903311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id); 9048512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler const MIR* mir; 905311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {block id %d\\l}%s\\\n", bb->id, 906311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->first_mir_insn ? " | " : " "); 907311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee for (mir = bb->first_mir_insn; mir; mir = mir->next) { 908311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int opcode = mir->dalvikInsn.opcode; 909d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell if (opcode > kMirOpSelect && opcode < kMirOpLast) { 910d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell if (opcode == kMirOpConstVector) { 911d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell fprintf(file, " {%04x %s %d %d %d %d %d %d\\l}%s\\\n", mir->offset, 912d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell extended_mir_op_names_[kMirOpConstVector - kMirOpFirst], 913d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.vA, 914d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.vB, 915d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.arg[0], 916d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.arg[1], 917d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.arg[2], 918d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.arg[3], 919d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->next ? " | " : " "); 920d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell } else { 921d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell fprintf(file, " {%04x %s %d %d %d\\l}%s\\\n", mir->offset, 922d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell extended_mir_op_names_[opcode - kMirOpFirst], 923d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.vA, 924d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.vB, 925d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->dalvikInsn.vC, 926d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->next ? " | " : " "); 927d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell } 928d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell } else { 92960bfe7b3e8f00f0a8ef3f5d8716adfdf86b71f43Udayan Banerji fprintf(file, " {%04x %s %s %s %s\\l}%s\\\n", mir->offset, 930d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->ssa_rep ? GetDalvikDisassembly(mir) : 9312ab40eb3c23559205ac7b9b039bd749458e8a761Jean Christophe Beyler !MIR::DecodedInstruction::IsPseudoMirOp(opcode) ? 9322ab40eb3c23559205ac7b9b039bd749458e8a761Jean Christophe Beyler Instruction::Name(mir->dalvikInsn.opcode) : 933d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell extended_mir_op_names_[opcode - kMirOpFirst], 934d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", 935d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", 93660bfe7b3e8f00f0a8ef3f5d8716adfdf86b71f43Udayan Banerji (mir->optimization_flags & MIR_IGNORE_SUSPEND_CHECK) != 0 ? " no_suspendcheck" : " ", 937d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell mir->next ? " | " : " "); 938d65c51a556e6649db4e18bd083c8fec37607a442Mark Mendell } 939311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 940311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 941311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } else if (bb->block_type == kExceptionHandling) { 942311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name[BLOCK_NAME_LEN]; 943311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 944311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name); 945311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s [shape=invhouse];\n", block_name); 946311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 947311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 948311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; 949311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 9500d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 951311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 9520d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->taken), block_name2); 953311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n [style=dotted]\n", 954311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name2); 955311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 9560d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 957311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 9580d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->fall_through), block_name2); 959311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); 960311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 961311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 9620d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->successor_block_list_type != kNotUsed) { 963311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", 964311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee bb->start_offset, bb->id, 9650d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); 9660d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); 9678512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* successor_block_info = iterator.Next(); 968311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 969311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee int succ_id = 0; 970311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee while (true) { 971311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (successor_block_info == NULL) break; 972311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 9738512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 974862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee SuccessorBlockInfo *next_successor_block_info = iterator.Next(); 975311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 976311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", 977311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee succ_id++, 978311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info->key, 979311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee dest_block->start_offset, 980311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee (next_successor_block_info != NULL) ? " | " : " "); 981311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 982311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee successor_block_info = next_successor_block_info; 983311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 984311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " }\"];\n\n"); 985311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 986311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 987311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", 988311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, bb->start_offset, bb->id); 989311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 99025bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru // Link the successor pseudo-block with all of its potential targets. 99125bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); 992311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 99325bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru succ_id = 0; 99425bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru while (true) { 9958512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* successor_block_info = iter.Next(); 99625bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru if (successor_block_info == NULL) break; 997311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 99825bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); 999311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 100025bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru GetBlockName(dest_block, block_name2); 100125bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, 100225bc279080a56546b0f8a33342a853b2778eed0dRazvan A Lupusoru bb->id, succ_id++, block_name2); 1003311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1004311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1005311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "\n"); 1006311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 1007311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (cu_->verbose) { 1008311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee /* Display the dominator tree */ 1009311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee GetBlockName(bb, block_name1); 1010311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", 1011311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee block_name1, block_name1); 1012311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee if (bb->i_dom) { 10130d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee GetBlockName(GetBasicBlock(bb->i_dom), block_name2); 1014311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); 1015311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1016311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1017311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee } 1018311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fprintf(file, "}\n"); 1019311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee fclose(file); 1020311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee} 1021311ca169f4727d46a55bdc8dfa0059719fa72b65buzbee 10223aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler/* Insert an MIR instruction to the end of a basic block. */ 1023cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beylervoid BasicBlock::AppendMIR(MIR* mir) { 10248512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Insert it after the last MIR. 10258512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler InsertMIRListAfter(last_mir_insn, mir, mir); 10268512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 10278512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 10288512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::AppendMIRList(MIR* first_list_mir, MIR* last_list_mir) { 10298512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Insert it after the last MIR. 10308512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler InsertMIRListAfter(last_mir_insn, first_list_mir, last_list_mir); 10318512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 10328512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 10338512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::AppendMIRList(const std::vector<MIR*>& insns) { 10348512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (std::vector<MIR*>::const_iterator it = insns.begin(); it != insns.end(); it++) { 10358512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* new_mir = *it; 10368512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 10378512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Add a copy of each MIR. 10388512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler InsertMIRListAfter(last_mir_insn, new_mir, new_mir); 10398512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 10408512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 10418512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 10428512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler/* Insert a MIR instruction after the specified MIR. */ 10438512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::InsertMIRAfter(MIR* current_mir, MIR* new_mir) { 10448512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler InsertMIRListAfter(current_mir, new_mir, new_mir); 10458512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 10468512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 10478512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::InsertMIRListAfter(MIR* insert_after, MIR* first_list_mir, MIR* last_list_mir) { 10488512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If no MIR, we are done. 10498512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (first_list_mir == nullptr || last_list_mir == nullptr) { 10508512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return; 10518512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 10528512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 10538512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If insert_after is null, assume BB is empty. 10548512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (insert_after == nullptr) { 10558512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler first_mir_insn = first_list_mir; 10568512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_mir_insn = last_list_mir; 10578512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_list_mir->next = nullptr; 10581fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 10598512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* after_list = insert_after->next; 10608512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler insert_after->next = first_list_mir; 10618512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_list_mir->next = after_list; 10628512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (after_list == nullptr) { 10638512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_mir_insn = last_list_mir; 10648512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 10651fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10663aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 10678512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Set this BB to be the basic block of the MIRs. 10688512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* last = last_list_mir->next; 10698512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (MIR* mir = first_list_mir; mir != last; mir = mir->next) { 10708512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler mir->bb = id; 10718512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 10721fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10731fd3346740dfb7f47be9922312b68a4227fada96buzbee 10743aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler/* Insert an MIR instruction to the head of a basic block. */ 1075cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beylervoid BasicBlock::PrependMIR(MIR* mir) { 10768512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler InsertMIRListBefore(first_mir_insn, mir, mir); 10778512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 10783aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 10798512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::PrependMIRList(MIR* first_list_mir, MIR* last_list_mir) { 10808512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Insert it before the first MIR. 10818512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler InsertMIRListBefore(first_mir_insn, first_list_mir, last_list_mir); 10821fd3346740dfb7f47be9922312b68a4227fada96buzbee} 10831fd3346740dfb7f47be9922312b68a4227fada96buzbee 10848512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::PrependMIRList(const std::vector<MIR*>& to_add) { 10858512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (std::vector<MIR*>::const_iterator it = to_add.begin(); it != to_add.end(); it++) { 10868512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* mir = *it; 10871fd3346740dfb7f47be9922312b68a4227fada96buzbee 10888512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler InsertMIRListBefore(first_mir_insn, mir, mir); 10891fd3346740dfb7f47be9922312b68a4227fada96buzbee } 10908512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 10913aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 10928512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler/* Insert a MIR instruction before the specified MIR. */ 10938512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::InsertMIRBefore(MIR* current_mir, MIR* new_mir) { 10948512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Insert as a single element list. 10958512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return InsertMIRListBefore(current_mir, new_mir, new_mir); 10963aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler} 10973aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 10983aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe BeylerMIR* BasicBlock::FindPreviousMIR(MIR* mir) { 10993aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler MIR* current = first_mir_insn; 11003aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 11013aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler while (current != nullptr) { 11023aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler MIR* next = current->next; 11033aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 11043aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler if (next == mir) { 11053aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler return current; 11063aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler } 11073aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 11083aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler current = next; 11093aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler } 11103aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 11113aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler return nullptr; 11123aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler} 11133aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 11148512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::InsertMIRListBefore(MIR* insert_before, MIR* first_list_mir, MIR* last_list_mir) { 11158512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If no MIR, we are done. 11168512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (first_list_mir == nullptr || last_list_mir == nullptr) { 11178512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return; 11188512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11198512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 11208512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If insert_before is null, assume BB is empty. 11218512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (insert_before == nullptr) { 11228512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler first_mir_insn = first_list_mir; 11238512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_mir_insn = last_list_mir; 11248512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_list_mir->next = nullptr; 11258512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } else { 11268512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (first_mir_insn == insert_before) { 11278512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_list_mir->next = first_mir_insn; 11288512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler first_mir_insn = first_list_mir; 11298512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } else { 11308512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Find the preceding MIR. 11318512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* before_list = FindPreviousMIR(insert_before); 11328512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler DCHECK(before_list != nullptr); 11338512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler before_list->next = first_list_mir; 11348512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_list_mir->next = insert_before; 11358512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11368512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11378512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 11388512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Set this BB to be the basic block of the MIRs. 11398512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (MIR* mir = first_list_mir; mir != last_list_mir->next; mir = mir->next) { 11408512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler mir->bb = id; 11413aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler } 11428512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 11438512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 11448512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylerbool BasicBlock::RemoveMIR(MIR* mir) { 11458512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Remove as a single element list. 11468512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return RemoveMIRList(mir, mir); 11478512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 11488512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 11498512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylerbool BasicBlock::RemoveMIRList(MIR* first_list_mir, MIR* last_list_mir) { 11508512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (first_list_mir == nullptr) { 11518512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return false; 11528512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11538512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 11548512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Try to find the MIR. 11558512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* before_list = nullptr; 11568512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* after_list = nullptr; 11573aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 11588512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If we are removing from the beginning of the MIR list. 11598512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (first_mir_insn == first_list_mir) { 11608512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler before_list = nullptr; 11618512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } else { 11628512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler before_list = FindPreviousMIR(first_list_mir); 11638512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (before_list == nullptr) { 11648512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // We did not find the mir. 11658512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return false; 11668512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11678512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11688512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 1169a4307aca310aac0ac62dcb5435daa02b1f950558Jean Christophe Beyler // Remove the BB information and also find the after_list. 11708512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (MIR* mir = first_list_mir; mir != last_list_mir; mir = mir->next) { 11718512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler mir->bb = NullBasicBlockId; 11728512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11738512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 11748512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler after_list = last_list_mir->next; 11758512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 1176a4307aca310aac0ac62dcb5435daa02b1f950558Jean Christophe Beyler // If there is nothing before the list, after_list is the first_mir. 11778512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (before_list == nullptr) { 11788512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler first_mir_insn = after_list; 1179a4307aca310aac0ac62dcb5435daa02b1f950558Jean Christophe Beyler } else { 1180a4307aca310aac0ac62dcb5435daa02b1f950558Jean Christophe Beyler before_list->next = after_list; 11818512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 11823aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 1183a4307aca310aac0ac62dcb5435daa02b1f950558Jean Christophe Beyler // If there is nothing after the list, before_list is last_mir. 11848512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (after_list == nullptr) { 11858512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_mir_insn = before_list; 11863aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler } 11878512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 11888512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return true; 11891fd3346740dfb7f47be9922312b68a4227fada96buzbee} 11901fd3346740dfb7f47be9922312b68a4227fada96buzbee 1191cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe BeylerMIR* BasicBlock::GetNextUnconditionalMir(MIRGraph* mir_graph, MIR* current) { 11923bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru MIR* next_mir = nullptr; 11933bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 11943bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru if (current != nullptr) { 11953bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru next_mir = current->next; 11963bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 11973bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 11983bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru if (next_mir == nullptr) { 11993bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru // Only look for next MIR that follows unconditionally. 1200cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler if ((taken == NullBasicBlockId) && (fall_through != NullBasicBlockId)) { 1201cdacac4a8196bdc620185079ec9e886329606f3dJean Christophe Beyler next_mir = mir_graph->GetBasicBlock(fall_through)->first_mir_insn; 12023bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 12033bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru } 12043bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 12053bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru return next_mir; 12063bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru} 12073bc01748ef1c3e43361bdf520947a9d656658bf8Razvan A Lupusoru 12082ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromchar* MIRGraph::GetDalvikDisassembly(const MIR* mir) { 120929a2648821ea4d0b5d3aecb9f835822fdfe6faa1Ian Rogers MIR::DecodedInstruction insn = mir->dalvikInsn; 12101fd3346740dfb7f47be9922312b68a4227fada96buzbee std::string str; 12111fd3346740dfb7f47be9922312b68a4227fada96buzbee int flags = 0; 12121fd3346740dfb7f47be9922312b68a4227fada96buzbee int opcode = insn.opcode; 12131fd3346740dfb7f47be9922312b68a4227fada96buzbee char* ret; 12141fd3346740dfb7f47be9922312b68a4227fada96buzbee bool nop = false; 12151fd3346740dfb7f47be9922312b68a4227fada96buzbee SSARepresentation* ssa_rep = mir->ssa_rep; 12168512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format. 12171fd3346740dfb7f47be9922312b68a4227fada96buzbee int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; 12181fd3346740dfb7f47be9922312b68a4227fada96buzbee int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; 12191fd3346740dfb7f47be9922312b68a4227fada96buzbee 12201fd3346740dfb7f47be9922312b68a4227fada96buzbee // Handle special cases. 12211fd3346740dfb7f47be9922312b68a4227fada96buzbee if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { 12221fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 12231fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(": "); 12248512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Recover the original Dex instruction. 12251fd3346740dfb7f47be9922312b68a4227fada96buzbee insn = mir->meta.throw_insn->dalvikInsn; 12261fd3346740dfb7f47be9922312b68a4227fada96buzbee ssa_rep = mir->meta.throw_insn->ssa_rep; 12271fd3346740dfb7f47be9922312b68a4227fada96buzbee defs = ssa_rep->num_defs; 12281fd3346740dfb7f47be9922312b68a4227fada96buzbee uses = ssa_rep->num_uses; 12291fd3346740dfb7f47be9922312b68a4227fada96buzbee opcode = insn.opcode; 12301fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if (opcode == kMirOpNop) { 12311fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("["); 12320d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // Recover original opcode. 12330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); 12340d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee opcode = insn.opcode; 12351fd3346740dfb7f47be9922312b68a4227fada96buzbee nop = true; 12361fd3346740dfb7f47be9922312b68a4227fada96buzbee } 12371fd3346740dfb7f47be9922312b68a4227fada96buzbee 12382ab40eb3c23559205ac7b9b039bd749458e8a761Jean Christophe Beyler if (MIR::DecodedInstruction::IsPseudoMirOp(opcode)) { 12391fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(extended_mir_op_names_[opcode - kMirOpFirst]); 12401fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 12411fd3346740dfb7f47be9922312b68a4227fada96buzbee dalvik_format = Instruction::FormatOf(insn.opcode); 12421fd3346740dfb7f47be9922312b68a4227fada96buzbee flags = Instruction::FlagsOf(insn.opcode); 12431fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(Instruction::Name(insn.opcode)); 12441fd3346740dfb7f47be9922312b68a4227fada96buzbee } 12451fd3346740dfb7f47be9922312b68a4227fada96buzbee 12461fd3346740dfb7f47be9922312b68a4227fada96buzbee if (opcode == kMirOpPhi) { 12470d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee BasicBlockId* incoming = mir->meta.phi_incoming; 12481fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s = (%s", 12491fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), 12501fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); 1251b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom str.append(StringPrintf(":%d", incoming[0])); 12521fd3346740dfb7f47be9922312b68a4227fada96buzbee int i; 12531fd3346740dfb7f47be9922312b68a4227fada96buzbee for (i = 1; i < uses; i++) { 12541fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", %s:%d", 12551fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), 12561fd3346740dfb7f47be9922312b68a4227fada96buzbee incoming[i])); 12571fd3346740dfb7f47be9922312b68a4227fada96buzbee } 12581fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(")"); 12591fd3346740dfb7f47be9922312b68a4227fada96buzbee } else if ((flags & Instruction::kBranch) != 0) { 12601fd3346740dfb7f47be9922312b68a4227fada96buzbee // For branches, decode the instructions to print out the branch targets. 12611fd3346740dfb7f47be9922312b68a4227fada96buzbee int offset = 0; 12621fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 12631fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21t: 12641fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); 12651fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vB; 12661fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 12671fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22t: 12681fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), 12691fd3346740dfb7f47be9922312b68a4227fada96buzbee GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); 12701fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vC; 12711fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 12721fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k10t: 12731fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k20t: 12741fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k30t: 12751fd3346740dfb7f47be9922312b68a4227fada96buzbee offset = insn.vA; 12761fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 12771fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 12781fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; 12791fd3346740dfb7f47be9922312b68a4227fada96buzbee } 12801fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset, 12811fd3346740dfb7f47be9922312b68a4227fada96buzbee offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); 12821fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 12838512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // For invokes-style formats, treat wide regs as a pair of singles. 12841fd3346740dfb7f47be9922312b68a4227fada96buzbee bool show_singles = ((dalvik_format == Instruction::k35c) || 12851fd3346740dfb7f47be9922312b68a4227fada96buzbee (dalvik_format == Instruction::k3rc)); 12861fd3346740dfb7f47be9922312b68a4227fada96buzbee if (defs != 0) { 12871fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(" %s", GetSSANameWithConst(ssa_rep->defs[0], false).c_str())); 12881fd3346740dfb7f47be9922312b68a4227fada96buzbee if (uses != 0) { 12891fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(", "); 12901fd3346740dfb7f47be9922312b68a4227fada96buzbee } 12911fd3346740dfb7f47be9922312b68a4227fada96buzbee } 12921fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < uses; i++) { 12931fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append( 12941fd3346740dfb7f47be9922312b68a4227fada96buzbee StringPrintf(" %s", GetSSANameWithConst(ssa_rep->uses[i], show_singles).c_str())); 12951fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { 12961fd3346740dfb7f47be9922312b68a4227fada96buzbee // For the listing, skip the high sreg. 12971fd3346740dfb7f47be9922312b68a4227fada96buzbee i++; 12981fd3346740dfb7f47be9922312b68a4227fada96buzbee } 12991fd3346740dfb7f47be9922312b68a4227fada96buzbee if (i != (uses -1)) { 13001fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(","); 13011fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13021fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13031fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (dalvik_format) { 13048512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler case Instruction::k11n: // Add one immediate from vB. 13051fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21s: 13061fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31i: 13071fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k21h: 13081fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vB)); 13091fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13108512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler case Instruction::k51l: // Add one wide immediate. 131123b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); 13121fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13138512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler case Instruction::k21c: // One register, one string/type/method index. 13141fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k31c: 13151fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vB)); 13161fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13178512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler case Instruction::k22c: // Two registers, one string/type/method index. 13181fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", index #%d", insn.vC)); 13191fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13208512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler case Instruction::k22s: // Add one immediate from vC. 13211fd3346740dfb7f47be9922312b68a4227fada96buzbee case Instruction::k22b: 13221fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append(StringPrintf(", #%d", insn.vC)); 13231fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 132402c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom default: { 13258512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Nothing left to print. 13261fd3346740dfb7f47be9922312b68a4227fada96buzbee } 132702c8cc6d1312a2b55533f02f6369dc7c94672f90Brian Carlstrom } 13281fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13291fd3346740dfb7f47be9922312b68a4227fada96buzbee if (nop) { 13301fd3346740dfb7f47be9922312b68a4227fada96buzbee str.append("]--optimized away"); 13311fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13321fd3346740dfb7f47be9922312b68a4227fada96buzbee int length = str.length() + 1; 133383cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko ret = static_cast<char*>(arena_->Alloc(length, kArenaAllocDFInfo)); 13341fd3346740dfb7f47be9922312b68a4227fada96buzbee strncpy(ret, str.c_str(), length); 13351fd3346740dfb7f47be9922312b68a4227fada96buzbee return ret; 13361fd3346740dfb7f47be9922312b68a4227fada96buzbee} 13371fd3346740dfb7f47be9922312b68a4227fada96buzbee 13381fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Turn method name into a legal Linux file name */ 13392ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::ReplaceSpecialChars(std::string& str) { 13409b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom static const struct { const char before; const char after; } match[] = { 13419b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, 13429b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} 13439b7085a4e7c40e7fa01932ea1647a4a33ac1c585Brian Carlstrom }; 13441fd3346740dfb7f47be9922312b68a4227fada96buzbee for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { 13451fd3346740dfb7f47be9922312b68a4227fada96buzbee std::replace(str.begin(), str.end(), match[i].before, match[i].after); 13461fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13471fd3346740dfb7f47be9922312b68a4227fada96buzbee} 13481fd3346740dfb7f47be9922312b68a4227fada96buzbee 13492ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSAName(int ssa_reg) { 135039ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to 135139ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // the arena. We should be smarter and just place straight into the arena, or compute the 135239ebcb800aabedd0ffa6aa4aeac8aa4194c66e61Ian Rogers // value more lazily. 13531fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 13541fd3346740dfb7f47be9922312b68a4227fada96buzbee} 13551fd3346740dfb7f47be9922312b68a4227fada96buzbee 13561fd3346740dfb7f47be9922312b68a4227fada96buzbee// Similar to GetSSAName, but if ssa name represents an immediate show that as well. 13572ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromstd::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { 13581fd3346740dfb7f47be9922312b68a4227fada96buzbee if (reg_location_ == NULL) { 13598512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Pre-SSA - just use the standard name. 13601fd3346740dfb7f47be9922312b68a4227fada96buzbee return GetSSAName(ssa_reg); 13611fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13621fd3346740dfb7f47be9922312b68a4227fada96buzbee if (IsConst(reg_location_[ssa_reg])) { 13631fd3346740dfb7f47be9922312b68a4227fada96buzbee if (!singles_only && reg_location_[ssa_reg].wide) { 136423b03b5b5fdaa517eda3b8b358752672cf6046b1Ian Rogers return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 13651fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValueWide(reg_location_[ssa_reg])); 13661fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 1367b1eba213afaf7fa6445de863ddc9680ab99762eaBrian Carlstrom return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), 13681fd3346740dfb7f47be9922312b68a4227fada96buzbee ConstantValue(reg_location_[ssa_reg])); 13691fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13701fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 13711fd3346740dfb7f47be9922312b68a4227fada96buzbee return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); 13721fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13731fd3346740dfb7f47be9922312b68a4227fada96buzbee} 13741fd3346740dfb7f47be9922312b68a4227fada96buzbee 13752ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::GetBlockName(BasicBlock* bb, char* name) { 13761fd3346740dfb7f47be9922312b68a4227fada96buzbee switch (bb->block_type) { 13771fd3346740dfb7f47be9922312b68a4227fada96buzbee case kEntryBlock: 13781fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); 13791fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13801fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExitBlock: 13811fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); 13821fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13831fd3346740dfb7f47be9922312b68a4227fada96buzbee case kDalvikByteCode: 13841fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); 13851fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13861fd3346740dfb7f47be9922312b68a4227fada96buzbee case kExceptionHandling: 13871fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, 13881fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id); 13891fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13901fd3346740dfb7f47be9922312b68a4227fada96buzbee default: 13911fd3346740dfb7f47be9922312b68a4227fada96buzbee snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); 13921fd3346740dfb7f47be9922312b68a4227fada96buzbee break; 13931fd3346740dfb7f47be9922312b68a4227fada96buzbee } 13941fd3346740dfb7f47be9922312b68a4227fada96buzbee} 13951fd3346740dfb7f47be9922312b68a4227fada96buzbee 13962ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromconst char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { 13970d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee // TODO: for inlining support, use current code unit. 13981fd3346740dfb7f47be9922312b68a4227fada96buzbee const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); 13991fd3346740dfb7f47be9922312b68a4227fada96buzbee return cu_->dex_file->GetShorty(method_id.proto_idx_); 14001fd3346740dfb7f47be9922312b68a4227fada96buzbee} 14011fd3346740dfb7f47be9922312b68a4227fada96buzbee 14021fd3346740dfb7f47be9922312b68a4227fada96buzbee/* Debug Utility - dump a compilation unit */ 14032ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid MIRGraph::DumpMIRGraph() { 14041fd3346740dfb7f47be9922312b68a4227fada96buzbee BasicBlock* bb; 14051fd3346740dfb7f47be9922312b68a4227fada96buzbee const char* block_type_names[] = { 140617189ac098b2f156713db1821b49db7b2f018bbebuzbee "Null Block", 14071fd3346740dfb7f47be9922312b68a4227fada96buzbee "Entry Block", 14081fd3346740dfb7f47be9922312b68a4227fada96buzbee "Code Block", 14091fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exit Block", 14101fd3346740dfb7f47be9922312b68a4227fada96buzbee "Exception Handling", 14111fd3346740dfb7f47be9922312b68a4227fada96buzbee "Catch Block" 14121fd3346740dfb7f47be9922312b68a4227fada96buzbee }; 14131fd3346740dfb7f47be9922312b68a4227fada96buzbee 14141fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); 14151fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << cu_->insns << " insns"; 14161fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << GetNumBlocks() << " blocks in total"; 1417862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 14181fd3346740dfb7f47be9922312b68a4227fada96buzbee 14191fd3346740dfb7f47be9922312b68a4227fada96buzbee while (true) { 1420862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb = iterator.Next(); 14211fd3346740dfb7f47be9922312b68a4227fada96buzbee if (bb == NULL) break; 14221fd3346740dfb7f47be9922312b68a4227fada96buzbee LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", 14231fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->id, 14241fd3346740dfb7f47be9922312b68a4227fada96buzbee block_type_names[bb->block_type], 14251fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->start_offset, 14261fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, 14271fd3346740dfb7f47be9922312b68a4227fada96buzbee bb->last_mir_insn ? "" : " empty"); 14280d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->taken != NullBasicBlockId) { 14290d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Taken branch: block " << bb->taken 14300d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; 14311fd3346740dfb7f47be9922312b68a4227fada96buzbee } 14320d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee if (bb->fall_through != NullBasicBlockId) { 14330d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee LOG(INFO) << " Fallthrough : block " << bb->fall_through 14340d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; 14351fd3346740dfb7f47be9922312b68a4227fada96buzbee } 14361fd3346740dfb7f47be9922312b68a4227fada96buzbee } 14371fd3346740dfb7f47be9922312b68a4227fada96buzbee} 14381fd3346740dfb7f47be9922312b68a4227fada96buzbee 14391fd3346740dfb7f47be9922312b68a4227fada96buzbee/* 14401fd3346740dfb7f47be9922312b68a4227fada96buzbee * Build an array of location records for the incoming arguments. 14411fd3346740dfb7f47be9922312b68a4227fada96buzbee * Note: one location record per word of arguments, with dummy 14421fd3346740dfb7f47be9922312b68a4227fada96buzbee * high-word loc for wide arguments. Also pull up any following 14431fd3346740dfb7f47be9922312b68a4227fada96buzbee * MOVE_RESULT and incorporate it into the invoke. 14441fd3346740dfb7f47be9922312b68a4227fada96buzbee */ 14451fd3346740dfb7f47be9922312b68a4227fada96buzbeeCallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, 14462ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstrom bool is_range) { 1447f6c4b3ba3825de1dbb3e747a68b809c6cc8eb4dbMathieu Chartier CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), 144883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko kArenaAllocMisc)); 14491fd3346740dfb7f47be9922312b68a4227fada96buzbee MIR* move_result_mir = FindMoveResult(bb, mir); 14501fd3346740dfb7f47be9922312b68a4227fada96buzbee if (move_result_mir == NULL) { 14511fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result.location = kLocInvalid; 14521fd3346740dfb7f47be9922312b68a4227fada96buzbee } else { 14531fd3346740dfb7f47be9922312b68a4227fada96buzbee info->result = GetRawDest(move_result_mir); 14541fd3346740dfb7f47be9922312b68a4227fada96buzbee move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); 14551fd3346740dfb7f47be9922312b68a4227fada96buzbee } 14561fd3346740dfb7f47be9922312b68a4227fada96buzbee info->num_arg_words = mir->ssa_rep->num_uses; 14571fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> 145883cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, kArenaAllocMisc)); 14591fd3346740dfb7f47be9922312b68a4227fada96buzbee for (int i = 0; i < info->num_arg_words; i++) { 14601fd3346740dfb7f47be9922312b68a4227fada96buzbee info->args[i] = GetRawSrc(mir, i); 14611fd3346740dfb7f47be9922312b68a4227fada96buzbee } 14621fd3346740dfb7f47be9922312b68a4227fada96buzbee info->opt_flags = mir->optimization_flags; 14631fd3346740dfb7f47be9922312b68a4227fada96buzbee info->type = type; 14641fd3346740dfb7f47be9922312b68a4227fada96buzbee info->is_range = is_range; 14651fd3346740dfb7f47be9922312b68a4227fada96buzbee info->index = mir->dalvikInsn.vB; 14661fd3346740dfb7f47be9922312b68a4227fada96buzbee info->offset = mir->offset; 1467f096aad9203d7c50b2f9cbe1c1215a50c265a059Vladimir Marko info->mir = mir; 14681fd3346740dfb7f47be9922312b68a4227fada96buzbee return info; 14691fd3346740dfb7f47be9922312b68a4227fada96buzbee} 14701fd3346740dfb7f47be9922312b68a4227fada96buzbee 14713aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler// Allocate a new MIR. 14723aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe BeylerMIR* MIRGraph::NewMIR() { 14733aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler MIR* mir = new (arena_) MIR(); 14743aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler return mir; 14753aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler} 14763aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 1477862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee// Allocate a new basic block. 14782ce745c06271d5223d57dbf08117b20d5b60694aBrian CarlstromBasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { 14798512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* bb = new (arena_) BasicBlock(); 14808512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 1481862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->block_type = block_type; 1482862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bb->id = block_id; 1483862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee // TUNING: better estimate of the exit block predecessors? 14840d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, 1485df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom (block_type == kExitBlock) ? 2048 : 2, 1486df62950e7a32031b82360c407d46a37b94188fbbBrian Carlstrom kGrowableArrayPredecessors); 14870d82948094d9a198e01aa95f64012bdedd5b6fc9buzbee bb->successor_block_list_type = kNotUsed; 1488862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee block_id_map_.Put(block_id, block_id); 1489862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return bb; 1490862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} 14911fd3346740dfb7f47be9922312b68a4227fada96buzbee 14924e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeConstantPropagation() { 14934e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); 149483cc7ae96d4176533dd0391a1591d321b0a87f4fVladimir Marko constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), kArenaAllocDFInfo)); 14954e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 14964e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 14974e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beylervoid MIRGraph::InitializeMethodUses() { 14988512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // The gate starts by initializing the use counts. 14994e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler int num_ssa_regs = GetNumSSARegs(); 15004e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Resize(num_ssa_regs + 32); 15014e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Resize(num_ssa_regs + 32); 15028512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Initialize list. 15034e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler for (int i = 0; i < num_ssa_regs; i++) { 15044e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler use_counts_.Insert(0); 15054e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler raw_use_counts_.Insert(0); 15064e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler } 15074e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 15084e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 1509a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Markovoid MIRGraph::SSATransformationStart() { 1510a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko DCHECK(temp_scoped_alloc_.get() == nullptr); 1511a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack)); 1512a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_bit_vector_size_ = cu_->num_dalvik_registers; 1513a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_bit_vector_ = new (temp_scoped_alloc_.get()) ArenaBitVector( 1514a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_scoped_alloc_.get(), temp_bit_vector_size_, false, kBitMapRegisterV); 1515a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko 15164896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler // Update the maximum number of reachable blocks. 15174896d7b6fb75add25f2d6ba84346ac83d8ba9d51Jean Christophe Beyler max_num_reachable_blocks_ = num_reachable_blocks_; 15184e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler} 15194e97c539408f47145526f0062c1c06df99146a73Jean Christophe Beyler 1520a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Markovoid MIRGraph::SSATransformationEnd() { 1521a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko // Verify the dataflow information after the pass. 1522a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko if (cu_->enable_debug & (1 << kDebugVerifyDataflow)) { 1523a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko VerifyDataflow(); 1524a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko } 1525a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko 1526a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_bit_vector_size_ = 0u; 1527a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_bit_vector_ = nullptr; 1528a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko DCHECK(temp_scoped_alloc_.get() != nullptr); 1529a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko temp_scoped_alloc_.reset(); 1530a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko} 1531a5b8fde2d2bc3167078694fad417fddfe442a6fdVladimir Marko 153255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Markostatic BasicBlock* SelectTopologicalSortOrderFallBack( 153355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko MIRGraph* mir_graph, const ArenaBitVector* current_loop, 153455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko const ScopedArenaVector<size_t>* visited_cnt_values, ScopedArenaAllocator* allocator, 153555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ScopedArenaVector<BasicBlockId>* tmp_stack) { 153655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // No true loop head has been found but there may be true loop heads after the mess we need 153755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // to resolve. To avoid taking one of those, pick the candidate with the highest number of 153855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // reachable unvisited nodes. That candidate will surely be a part of a loop. 153955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlock* fall_back = nullptr; 154055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko size_t fall_back_num_reachable = 0u; 154155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Reuse the same bit vector for each candidate to mark reachable unvisited blocks. 154255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ArenaBitVector candidate_reachable(allocator, mir_graph->GetNumBlocks(), false, kBitMapMisc); 154355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko AllNodesIterator iter(mir_graph); 154455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko for (BasicBlock* candidate = iter.Next(); candidate != nullptr; candidate = iter.Next()) { 154555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (candidate->hidden || // Hidden, or 154655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko candidate->visited || // already processed, or 154755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko (*visited_cnt_values)[candidate->id] == 0u || // no processed predecessors, or 154855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko (current_loop != nullptr && // outside current loop. 154955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko !current_loop->IsBitSet(candidate->id))) { 155055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko continue; 155155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 155255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(tmp_stack->empty()); 155355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko tmp_stack->push_back(candidate->id); 155455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko candidate_reachable.ClearAllBits(); 155555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko size_t num_reachable = 0u; 155655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko while (!tmp_stack->empty()) { 155755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlockId current_id = tmp_stack->back(); 155855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko tmp_stack->pop_back(); 155955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id); 156055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(current_bb != nullptr); 156155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ChildBlockIterator child_iter(current_bb, mir_graph); 156255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlock* child_bb = child_iter.Next(); 156355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko for ( ; child_bb != nullptr; child_bb = child_iter.Next()) { 156455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(!child_bb->hidden); 156555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (child_bb->visited || // Already processed, or 156655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko (current_loop != nullptr && // outside current loop. 156755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko !current_loop->IsBitSet(child_bb->id))) { 156855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko continue; 156955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 157055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (!candidate_reachable.IsBitSet(child_bb->id)) { 157155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko candidate_reachable.SetBit(child_bb->id); 157255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko tmp_stack->push_back(child_bb->id); 157355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko num_reachable += 1u; 157455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 157555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 157655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 157755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (fall_back_num_reachable < num_reachable) { 157855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko fall_back_num_reachable = num_reachable; 157955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko fall_back = candidate; 158055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 158155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 158255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko return fall_back; 158355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko} 158444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 158555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko// Compute from which unvisited blocks is bb_id reachable through unvisited blocks. 158655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Markostatic void ComputeUnvisitedReachableFrom(MIRGraph* mir_graph, BasicBlockId bb_id, 158755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ArenaBitVector* reachable, 158855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ScopedArenaVector<BasicBlockId>* tmp_stack) { 158955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // NOTE: Loop heads indicated by the "visited" flag. 159055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(tmp_stack->empty()); 159155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko reachable->ClearAllBits(); 159255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko tmp_stack->push_back(bb_id); 159355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko while (!tmp_stack->empty()) { 159455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlockId current_id = tmp_stack->back(); 159555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko tmp_stack->pop_back(); 159655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id); 159755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(current_bb != nullptr); 159855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko GrowableArray<BasicBlockId>::Iterator iter(current_bb->predecessors); 159955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlock* pred_bb = mir_graph->GetBasicBlock(iter.Next()); 160055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko for ( ; pred_bb != nullptr; pred_bb = mir_graph->GetBasicBlock(iter.Next())) { 160155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (!pred_bb->visited && !reachable->IsBitSet(pred_bb->id)) { 160255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko reachable->SetBit(pred_bb->id); 160355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko tmp_stack->push_back(pred_bb->id); 160455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 160555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 160644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 160755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko} 160844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 160955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Markovoid MIRGraph::ComputeTopologicalSortOrder() { 1610622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko ScopedArenaAllocator allocator(&cu_->arena_stack); 161155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko unsigned int num_blocks = GetNumBlocks(); 161255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 1613622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko ScopedArenaQueue<BasicBlock*> q(allocator.Adapter()); 161455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ScopedArenaVector<size_t> visited_cnt_values(num_blocks, 0u, allocator.Adapter()); 161555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ScopedArenaVector<BasicBlockId> loop_head_stack(allocator.Adapter()); 161655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko size_t max_nested_loops = 0u; 161755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ArenaBitVector loop_exit_blocks(&allocator, num_blocks, false, kBitMapMisc); 161855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_exit_blocks.ClearAllBits(); 1619622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko 162055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Count the number of blocks to process and add the entry block(s). 162144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); 162255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko unsigned int num_blocks_to_process = 0u; 162355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { 162444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler if (bb->hidden == true) { 162544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler continue; 162644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 162744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 162855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko num_blocks_to_process += 1u; 1629622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko 163055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (bb->predecessors->Size() == 0u) { 163155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Add entry block to the queue. 163244e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler q.push(bb); 163344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 163444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 163544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 163655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Create the topological order if need be. 163755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (topological_order_ == nullptr) { 163855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, num_blocks); 163955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_ends_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks); 164055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_indexes_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks); 164155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 164255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_->Reset(); 164355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_ends_->Reset(); 164455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_indexes_->Reset(); 164555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_ends_->Resize(num_blocks); 164655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_indexes_->Resize(num_blocks); 164755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko for (BasicBlockId i = 0; i != num_blocks; ++i) { 164855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_ends_->Insert(0u); 164955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_indexes_->Insert(static_cast<uint16_t>(-1)); 165055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 165155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 165255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Mark all blocks as unvisited. 165355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ClearAllVisitedFlags(); 165455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 165555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // For loop heads, keep track from which blocks they are reachable not going through other 165655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // loop heads. Other loop heads are excluded to detect the heads of nested loops. The children 165755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // in this set go into the loop body, the other children are jumping over the loop. 165855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ScopedArenaVector<ArenaBitVector*> loop_head_reachable_from(allocator.Adapter()); 165955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_reachable_from.resize(num_blocks, nullptr); 166055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Reuse the same temp stack whenever calculating a loop_head_reachable_from[loop_head_id]. 166155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ScopedArenaVector<BasicBlockId> tmp_stack(allocator.Adapter()); 166255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 166355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko while (num_blocks_to_process != 0u) { 1664622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko BasicBlock* bb = nullptr; 1665622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko if (!q.empty()) { 166655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko num_blocks_to_process -= 1u; 1667622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko // Get top. 1668622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko bb = q.front(); 1669622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko q.pop(); 167055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (bb->visited) { 167155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Loop head: it was already processed, mark end and copy exit blocks to the queue. 167255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(q.empty()) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 167355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko uint16_t idx = static_cast<uint16_t>(topological_order_->Size()); 167455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_ends_->Put(topological_order_indexes_->Get(bb->id), idx); 167555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK_EQ(loop_head_stack.back(), bb->id); 167655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_stack.pop_back(); 167755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ArenaBitVector* reachable = 167855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_stack.empty() ? nullptr : loop_head_reachable_from[loop_head_stack.back()]; 167955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko for (BasicBlockId candidate_id : loop_exit_blocks.Indexes()) { 168055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (reachable == nullptr || reachable->IsBitSet(candidate_id)) { 168155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko q.push(GetBasicBlock(candidate_id)); 168255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // NOTE: The BitVectorSet::IndexIterator will not check the pointed-to bit again, 168355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // so clearing the bit has no effect on the iterator. 168455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_exit_blocks.ClearBit(candidate_id); 168555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 168655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 168755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko continue; 168855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 1689622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko } else { 169055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Find the new loop head. 169155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko AllNodesIterator iter(this); 169255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko while (true) { 169355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlock* candidate = iter.Next(); 169455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (candidate == nullptr) { 169555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // We did not find a true loop head, fall back to a reachable block in any loop. 169655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ArenaBitVector* current_loop = 169755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_stack.empty() ? nullptr : loop_head_reachable_from[loop_head_stack.back()]; 169855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bb = SelectTopologicalSortOrderFallBack(this, current_loop, &visited_cnt_values, 169955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko &allocator, &tmp_stack); 170055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(bb != nullptr) << PrettyMethod(cu_->method_idx, *cu_->dex_file); 170155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (kIsDebugBuild && cu_->dex_file != nullptr) { 170255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko LOG(INFO) << "Topological sort order: Using fall-back in " 170355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " BB #" << bb->id 170455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko << " @0x" << std::hex << bb->start_offset 170555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko << ", num_blocks = " << std::dec << num_blocks; 170655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 170755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko break; 170855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 170955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (candidate->hidden || // Hidden, or 171055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko candidate->visited || // already processed, or 171155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko visited_cnt_values[candidate->id] == 0u || // no processed predecessors, or 171255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko (!loop_head_stack.empty() && // outside current loop. 171355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko !loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(candidate->id))) { 1714622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko continue; 1715622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko } 171655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 171755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko GrowableArray<BasicBlockId>::Iterator pred_iter(candidate->predecessors); 171855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko BasicBlock* pred_bb = GetBasicBlock(pred_iter.Next()); 171955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko for ( ; pred_bb != nullptr; pred_bb = GetBasicBlock(pred_iter.Next())) { 172055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (pred_bb != candidate && !pred_bb->visited && 172155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko !pred_bb->dominators->IsBitSet(candidate->id)) { 172255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko break; // Keep non-null pred_bb to indicate failure. 1723622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko } 1724622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko } 172555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (pred_bb == nullptr) { 172655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko bb = candidate; 172755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko break; 172855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 1729622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko } 173055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Compute blocks from which the loop head is reachable and process those blocks first. 173155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ArenaBitVector* reachable = 173255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko new (&allocator) ArenaBitVector(&allocator, num_blocks, false, kBitMapMisc); 173355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_reachable_from[bb->id] = reachable; 173455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko ComputeUnvisitedReachableFrom(this, bb->id, reachable, &tmp_stack); 173555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Now mark as loop head. (Even if it's only a fall back when we don't find a true loop.) 173655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_stack.push_back(bb->id); 173755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko max_nested_loops = std::max(max_nested_loops, loop_head_stack.size()); 1738622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko } 173944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 174044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler DCHECK_EQ(bb->hidden, false); 1741622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko DCHECK_EQ(bb->visited, false); 1742622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko bb->visited = true; 174344e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 1744622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko // Now add the basic block. 174555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko uint16_t idx = static_cast<uint16_t>(topological_order_->Size()); 174655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_indexes_->Put(bb->id, idx); 1747622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko topological_order_->Insert(bb->id); 174844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 174955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Update visited_cnt_values for children. 1750622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko ChildBlockIterator succIter(bb, this); 1751622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko BasicBlock* successor = succIter.Next(); 1752622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko for ( ; successor != nullptr; successor = succIter.Next()) { 175355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (successor->hidden) { 1754622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko continue; 1755622bdbe6c295b08d06dfaa8d896b9ca152aa899cVladimir Marko } 175644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 175755fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // One more predecessor was visited. 175855fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko visited_cnt_values[successor->id] += 1u; 175955fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (visited_cnt_values[successor->id] == successor->predecessors->Size()) { 176055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko if (loop_head_stack.empty() || 176155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(successor->id)) { 176255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko q.push(successor); 176355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } else { 176455fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko DCHECK(!loop_exit_blocks.IsBitSet(successor->id)); 176555fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko loop_exit_blocks.SetBit(successor->id); 176655fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko } 176744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 176844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 176944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 177055fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko 177155fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko // Prepare the loop head stack for iteration. 177255fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko topological_order_loop_head_stack_ = 177355fff044d3a4f7196098e25bab1dad106d9b54a2Vladimir Marko new (arena_) GrowableArray<std::pair<uint16_t, bool>>(arena_, max_nested_loops); 177444e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler} 177544e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 177644e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beylerbool BasicBlock::IsExceptionBlock() const { 177744e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler if (block_type == kExceptionHandling) { 177844e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler return true; 177944e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler } 178044e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler return false; 178144e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler} 178244e5bdec17d0528b90cc0773be2beb76dcafdc5bJean Christophe Beyler 178304f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jinbool MIRGraph::HasSuspendTestBetween(BasicBlock* source, BasicBlockId target_id) { 178404f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin BasicBlock* target = GetBasicBlock(target_id); 178504f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin 178604f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin if (source == nullptr || target == nullptr) 178704f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin return false; 178804f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin 178904f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin int idx; 179004f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin for (idx = gen_suspend_test_list_.Size() - 1; idx >= 0; idx--) { 179104f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin BasicBlock* bb = gen_suspend_test_list_.Get(idx); 179204f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin if (bb == source) 179304f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin return true; // The block has been inserted by a suspend check before. 179404f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin if (source->dominators->IsBitSet(bb->id) && bb->dominators->IsBitSet(target_id)) 179504f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin return true; 179604f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin } 179704f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin 179804f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin return false; 179904f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin} 180004f4d8abe45d6e79eca983e057de76aea24b7df9Wei Jin 1801f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe BeylerChildBlockIterator::ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph) 1802f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler : basic_block_(bb), mir_graph_(mir_graph), visited_fallthrough_(false), 1803f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler visited_taken_(false), have_successors_(false) { 1804f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler // Check if we actually do have successors. 1805f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler if (basic_block_ != 0 && basic_block_->successor_block_list_type != kNotUsed) { 1806f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler have_successors_ = true; 1807f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler successor_iter_.Reset(basic_block_->successor_blocks); 1808f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1809f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler} 1810f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 1811f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe BeylerBasicBlock* ChildBlockIterator::Next() { 1812f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler // We check if we have a basic block. If we don't we cannot get next child. 1813f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler if (basic_block_ == nullptr) { 1814f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler return nullptr; 1815f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1816f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 1817f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler // If we haven't visited fallthrough, return that. 1818f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler if (visited_fallthrough_ == false) { 1819f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler visited_fallthrough_ = true; 1820f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 1821f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->fall_through); 1822f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler if (result != nullptr) { 1823f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler return result; 1824f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1825f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1826f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 1827f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler // If we haven't visited taken, return that. 1828f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler if (visited_taken_ == false) { 1829f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler visited_taken_ = true; 1830f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 1831f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->taken); 1832f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler if (result != nullptr) { 1833f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler return result; 1834f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1835f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1836f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 1837f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler // We visited both taken and fallthrough. Now check if we have successors we need to visit. 1838f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler if (have_successors_ == true) { 1839f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler // Get information about next successor block. 1840989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar for (SuccessorBlockInfo* successor_block_info = successor_iter_.Next(); 1841989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar successor_block_info != nullptr; 1842989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar successor_block_info = successor_iter_.Next()) { 1843989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar // If block was replaced by zero block, take next one. 1844989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar if (successor_block_info->block != NullBasicBlockId) { 1845989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar return mir_graph_->GetBasicBlock(successor_block_info->block); 1846989367a47b015dd85f850cf756b436fb044b5aeaNiranjan Kumar } 1847f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1848f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler } 1849f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 1850f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler // We do not have anything. 1851f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler return nullptr; 1852f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler} 1853f8c762b8cbd4a223c697d7e7bdb976fb39224cb8Jean Christophe Beyler 18548512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe BeylerBasicBlock* BasicBlock::Copy(CompilationUnit* c_unit) { 18558512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIRGraph* mir_graph = c_unit->mir_graph.get(); 18568512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return Copy(mir_graph); 18578512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 18583aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18598512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe BeylerBasicBlock* BasicBlock::Copy(MIRGraph* mir_graph) { 18608512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* result_bb = mir_graph->CreateNewBB(block_type); 18613aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18628512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // We don't do a memcpy style copy here because it would lead to a lot of things 18638512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // to clean up. Let us do it by hand instead. 18648512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Copy in taken and fallthrough. 18658512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler result_bb->fall_through = fall_through; 18668512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler result_bb->taken = taken; 18673aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18688512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Copy successor links if needed. 18698512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler ArenaAllocator* arena = mir_graph->GetArena(); 18703aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18718512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler result_bb->successor_block_list_type = successor_block_list_type; 18728512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (result_bb->successor_block_list_type != kNotUsed) { 18738512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler size_t size = successor_blocks->Size(); 18748512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler result_bb->successor_blocks = new (arena) GrowableArray<SuccessorBlockInfo*>(arena, size, kGrowableArraySuccessorBlocks); 18758512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks); 18768512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler while (true) { 18778512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* sbi_old = iterator.Next(); 18788512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (sbi_old == nullptr) { 18798512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler break; 18808512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 18818512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>(arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 18828512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler memcpy(sbi_new, sbi_old, sizeof(SuccessorBlockInfo)); 18838512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler result_bb->successor_blocks->Insert(sbi_new); 18843aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler } 18858512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 18863aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18878512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Copy offset, method. 18888512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler result_bb->start_offset = start_offset; 18893aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18908512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Now copy instructions. 18918512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (MIR* mir = first_mir_insn; mir != 0; mir = mir->next) { 18928512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Get a copy first. 18938512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIR* copy = mir->Copy(mir_graph); 18943aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18958512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Append it. 18968512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler result_bb->AppendMIR(copy); 18973aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler } 18983aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 18998512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return result_bb; 19003aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler} 19013aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 19023aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe BeylerMIR* MIR::Copy(MIRGraph* mir_graph) { 19033aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler MIR* res = mir_graph->NewMIR(); 19043aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler *res = *this; 19053aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 19063aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler // Remove links 19073aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler res->next = nullptr; 19083aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler res->bb = NullBasicBlockId; 19093aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler res->ssa_rep = nullptr; 19103aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 19113aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler return res; 19123aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler} 19133aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 19143aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe BeylerMIR* MIR::Copy(CompilationUnit* c_unit) { 19153aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler return Copy(c_unit->mir_graph.get()); 19163aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler} 19173aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 19183aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyleruint32_t SSARepresentation::GetStartUseIndex(Instruction::Code opcode) { 19193aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler // Default result. 19203aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler int res = 0; 19213aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 19223aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler // We are basically setting the iputs to their igets counterparts. 19233aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler switch (opcode) { 19243aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT: 19253aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_OBJECT: 19263aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_BOOLEAN: 19273aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_BYTE: 19283aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_CHAR: 19293aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_SHORT: 19303aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_QUICK: 19313aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_OBJECT_QUICK: 19323aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::APUT: 19333aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::APUT_OBJECT: 19343aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::APUT_BOOLEAN: 19353aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::APUT_BYTE: 19363aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::APUT_CHAR: 19373aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::APUT_SHORT: 19383aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::SPUT: 19393aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::SPUT_OBJECT: 19403aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::SPUT_BOOLEAN: 19413aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::SPUT_BYTE: 19423aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::SPUT_CHAR: 19433aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::SPUT_SHORT: 19443aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler // Skip the VR containing what to store. 19453aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler res = 1; 19463aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler break; 19473aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_WIDE: 19483aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::IPUT_WIDE_QUICK: 19493aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::APUT_WIDE: 19503aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler case Instruction::SPUT_WIDE: 19513aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler // Skip the two VRs containing what to store. 19523aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler res = 2; 19533aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler break; 19543aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler default: 19553aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler // Do nothing in the general case. 19563aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler break; 19573aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler } 19583aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 19593aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler return res; 19603aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler} 19613aa57730e2aec451bb836918d936c6862598d8d6Jean Christophe Beyler 1962c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler/** 1963c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler * @brief Given a decoded instruction, it checks whether the instruction 1964c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler * sets a constant and if it does, more information is provided about the 1965c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler * constant being set. 1966c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler * @param ptr_value pointer to a 64-bit holder for the constant. 1967c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler * @param wide Updated by function whether a wide constant is being set by bytecode. 1968c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler * @return Returns false if the decoded instruction does not represent a constant bytecode. 1969c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler */ 1970c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beylerbool MIR::DecodedInstruction::GetConstant(int64_t* ptr_value, bool* wide) const { 1971c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler bool sets_const = true; 1972c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler int64_t value = vB; 1973c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler 1974c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler DCHECK(ptr_value != nullptr); 1975c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler DCHECK(wide != nullptr); 1976c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler 1977c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler switch (opcode) { 1978c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST_4: 1979c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST_16: 1980c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST: 1981c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler *wide = false; 1982c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value <<= 32; // In order to get the sign extend. 1983c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value >>= 32; 1984c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler break; 1985c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST_HIGH16: 1986c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler *wide = false; 1987c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value <<= 48; // In order to get the sign extend. 1988c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value >>= 32; 1989c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler break; 1990c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST_WIDE_16: 1991c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST_WIDE_32: 1992c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler *wide = true; 1993c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value <<= 32; // In order to get the sign extend. 1994c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value >>= 32; 1995c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler break; 1996c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST_WIDE: 1997c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler *wide = true; 1998c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value = vB_wide; 1999c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler break; 2000c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler case Instruction::CONST_WIDE_HIGH16: 2001c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler *wide = true; 2002c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler value <<= 48; // In order to get the sign extend. 2003c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler break; 2004c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler default: 2005c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler sets_const = false; 2006c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler break; 2007c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler } 2008c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler 2009c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler if (sets_const) { 2010c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler *ptr_value = value; 2011c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler } 2012c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler 2013c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler return sets_const; 2014c3db20b7e6f847339d6ecbd89846c173a7ccc967Jean Christophe Beyler} 20158512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20168512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::ResetOptimizationFlags(uint16_t reset_flags) { 20178512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Reset flags for all MIRs in bb. 20188512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (MIR* mir = first_mir_insn; mir != NULL; mir = mir->next) { 20198512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler mir->optimization_flags &= (~reset_flags); 20208512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20218512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 20228512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20238512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::Hide(CompilationUnit* c_unit) { 20248512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // First lets make it a dalvik bytecode block so it doesn't have any special meaning. 20258512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler block_type = kDalvikByteCode; 20268512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20278512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Mark it as hidden. 20288512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler hidden = true; 20298512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20308512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Detach it from its MIRs so we don't generate code for them. Also detached MIRs 20318512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // are updated to know that they no longer have a parent. 20328512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { 20338512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler mir->bb = NullBasicBlockId; 20348512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20358512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler first_mir_insn = nullptr; 20368512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_mir_insn = nullptr; 20378512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20388512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler GrowableArray<BasicBlockId>::Iterator iterator(predecessors); 20398512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20408512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler MIRGraph* mir_graph = c_unit->mir_graph.get(); 20418512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler while (true) { 20428512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* pred_bb = mir_graph->GetBasicBlock(iterator.Next()); 20438512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (pred_bb == nullptr) { 20448512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler break; 20458512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20468512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20478512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Sadly we have to go through the children by hand here. 20488512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler pred_bb->ReplaceChild(id, NullBasicBlockId); 20498512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20508512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20518512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Iterate through children of bb we are hiding. 20528512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler ChildBlockIterator successorChildIter(this, mir_graph); 20538512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20548512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (BasicBlock* childPtr = successorChildIter.Next(); childPtr != 0; childPtr = successorChildIter.Next()) { 20558512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Replace child with null child. 20568512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler childPtr->predecessors->Delete(id); 20578512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20588512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 20598512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20608512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylerbool BasicBlock::IsSSALiveOut(const CompilationUnit* c_unit, int ssa_reg) { 20618512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // In order to determine if the ssa reg is live out, we scan all the MIRs. We remember 20628512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // the last SSA number of the same dalvik register. At the end, if it is different than ssa_reg, 20638512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // then it is not live out of this BB. 20648512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler int dalvik_reg = c_unit->mir_graph->SRegToVReg(ssa_reg); 20658512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20668512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler int last_ssa_reg = -1; 20678512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20688512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Walk through the MIRs backwards. 20698512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { 20708512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Get ssa rep. 20718512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SSARepresentation *ssa_rep = mir->ssa_rep; 20728512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20738512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Go through the defines for this MIR. 20748512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler for (int i = 0; i < ssa_rep->num_defs; i++) { 20758512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler DCHECK(ssa_rep->defs != nullptr); 20768512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20778512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Get the ssa reg. 20788512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler int def_ssa_reg = ssa_rep->defs[i]; 20798512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20808512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Get dalvik reg. 20818512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler int def_dalvik_reg = c_unit->mir_graph->SRegToVReg(def_ssa_reg); 20828512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20838512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Compare dalvik regs. 20848512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (dalvik_reg == def_dalvik_reg) { 20858512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // We found a def of the register that we are being asked about. 20868512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Remember it. 20878512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler last_ssa_reg = def_ssa_reg; 20888512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20898512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20908512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20918512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20928512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (last_ssa_reg == -1) { 20938512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If we get to this point we couldn't find a define of register user asked about. 20948512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // Let's assume the user knows what he's doing so we can be safe and say that if we 20958512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // couldn't find a def, it is live out. 20968512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return true; 20978512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 20988512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 20998512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If it is not -1, we found a match, is it ssa_reg? 21008512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return (ssa_reg == last_ssa_reg); 21018512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 21028512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21038512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylerbool BasicBlock::ReplaceChild(BasicBlockId old_bb, BasicBlockId new_bb) { 21048512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // We need to check taken, fall_through, and successor_blocks to replace. 21058512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler bool found = false; 21068512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (taken == old_bb) { 21078512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler taken = new_bb; 21088512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler found = true; 21098512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21108512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21118512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (fall_through == old_bb) { 21128512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler fall_through = new_bb; 21138512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler found = true; 21148512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21158512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21168512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (successor_block_list_type != kNotUsed) { 21178512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks); 21188512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler while (true) { 21198512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler SuccessorBlockInfo* successor_block_info = iterator.Next(); 21208512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (successor_block_info == nullptr) { 21218512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler break; 21228512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21238512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (successor_block_info->block == old_bb) { 21248512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler successor_block_info->block = new_bb; 21258512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler found = true; 21268512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21278512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21288512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21298512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21308512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return found; 21318512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 21328512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21338512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beylervoid BasicBlock::UpdatePredecessor(BasicBlockId old_parent, BasicBlockId new_parent) { 21348512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler GrowableArray<BasicBlockId>::Iterator iterator(predecessors); 21358512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler bool found = false; 21368512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21378512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler while (true) { 21388512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlockId pred_bb_id = iterator.Next(); 21398512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21408512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (pred_bb_id == NullBasicBlockId) { 21418512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler break; 21428512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21438512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21448512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (pred_bb_id == old_parent) { 21458512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler size_t idx = iterator.GetIndex() - 1; 21468512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler predecessors->Put(idx, new_parent); 21478512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler found = true; 21488512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler break; 21498512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21508512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21518512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21528512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler // If not found, add it. 21538512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler if (found == false) { 21548512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler predecessors->Insert(new_parent); 21558512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler } 21568512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 21578512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21588512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler// Create a new basic block with block_id as num_blocks_ that is 21598512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler// post-incremented. 21608512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe BeylerBasicBlock* MIRGraph::CreateNewBB(BBType block_type) { 21618512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler BasicBlock* res = NewMemBB(block_type, num_blocks_++); 21628512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler block_list_.Insert(res); 21638512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler return res; 21648512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler} 21658512758d1208d3c32bf67db9c925b8fc6e077fd7Jean Christophe Beyler 21662469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beylervoid MIRGraph::CalculateBasicBlockInformation() { 21672469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler PassDriverMEPostOpt driver(cu_); 21682469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler driver.Launch(); 21692469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler} 21702469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler 21712469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beylervoid MIRGraph::InitializeBasicBlockData() { 21722469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler num_blocks_ = block_list_.Size(); 21732469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler} 21742469e60e6ff08c2a0b4cd1e209246c5d91027679Jean Christophe Beyler 21757934ac288acfb2552bb0b06ec1f61e5820d924a4Brian Carlstrom} // namespace art 2176