buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2013 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
Nicolas Geoffray | f3e2cc4 | 2014-02-18 18:37:26 +0000 | [diff] [blame] | 17 | #include "mir_graph.h" |
| 18 | |
| 19 | #include <inttypes.h> |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 20 | #include <queue> |
Nicolas Geoffray | f3e2cc4 | 2014-02-18 18:37:26 +0000 | [diff] [blame] | 21 | |
Ian Rogers | e77493c | 2014-08-20 15:08:45 -0700 | [diff] [blame] | 22 | #include "base/bit_vector-inl.h" |
Ian Rogers | 6282dc1 | 2013-04-18 15:54:02 -0700 | [diff] [blame] | 23 | #include "base/stl_util.h" |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 24 | #include "compiler_internals.h" |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 25 | #include "dex_file-inl.h" |
Ian Rogers | 29a2648 | 2014-05-02 15:27:29 -0700 | [diff] [blame] | 26 | #include "dex_instruction-inl.h" |
Vladimir Marko | 95a0597 | 2014-05-30 10:01:32 +0100 | [diff] [blame] | 27 | #include "dex/global_value_numbering.h" |
Vladimir Marko | 5816ed4 | 2013-11-27 17:04:20 +0000 | [diff] [blame] | 28 | #include "dex/quick/dex_file_to_method_inliner_map.h" |
| 29 | #include "dex/quick/dex_file_method_inliner.h" |
Nicolas Geoffray | f3e2cc4 | 2014-02-18 18:37:26 +0000 | [diff] [blame] | 30 | #include "leb128.h" |
Jean Christophe Beyler | 2469e60 | 2014-05-06 20:36:55 -0700 | [diff] [blame] | 31 | #include "pass_driver_me_post_opt.h" |
Andreas Gampe | 53c913b | 2014-08-12 23:19:23 -0700 | [diff] [blame] | 32 | #include "stack.h" |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 33 | #include "utils/scoped_arena_containers.h" |
Vladimir Marko | 5816ed4 | 2013-11-27 17:04:20 +0000 | [diff] [blame] | 34 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 35 | namespace art { |
| 36 | |
| 37 | #define MAX_PATTERN_LEN 5 |
| 38 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 39 | const char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { |
| 40 | "Phi", |
| 41 | "Copy", |
| 42 | "FusedCmplFloat", |
| 43 | "FusedCmpgFloat", |
| 44 | "FusedCmplDouble", |
| 45 | "FusedCmpgDouble", |
| 46 | "FusedCmpLong", |
| 47 | "Nop", |
| 48 | "OpNullCheck", |
| 49 | "OpRangeCheck", |
| 50 | "OpDivZeroCheck", |
| 51 | "Check1", |
| 52 | "Check2", |
| 53 | "Select", |
Mark Mendell | d65c51a | 2014-04-29 16:55:20 -0400 | [diff] [blame] | 54 | "ConstVector", |
| 55 | "MoveVector", |
| 56 | "PackedMultiply", |
| 57 | "PackedAddition", |
| 58 | "PackedSubtract", |
| 59 | "PackedShiftLeft", |
| 60 | "PackedSignedShiftRight", |
| 61 | "PackedUnsignedShiftRight", |
| 62 | "PackedAnd", |
| 63 | "PackedOr", |
| 64 | "PackedXor", |
| 65 | "PackedAddReduce", |
| 66 | "PackedReduce", |
| 67 | "PackedSet", |
Udayan Banerji | 60bfe7b | 2014-07-08 19:59:43 -0700 | [diff] [blame] | 68 | "ReserveVectorRegisters", |
| 69 | "ReturnVectorRegisters", |
Jean Christophe Beyler | b5bce7c | 2014-07-25 12:32:18 -0700 | [diff] [blame] | 70 | "MemBarrier", |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 71 | }; |
| 72 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 73 | MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 74 | : reg_location_(NULL), |
Vladimir Marko | 8081d2b | 2014-07-31 15:33:43 +0100 | [diff] [blame] | 75 | block_id_map_(std::less<unsigned int>(), arena->Adapter()), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 76 | cu_(cu), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 77 | ssa_base_vregs_(NULL), |
| 78 | ssa_subscripts_(NULL), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 79 | vreg_to_ssa_map_(NULL), |
| 80 | ssa_last_defs_(NULL), |
| 81 | is_constant_v_(NULL), |
| 82 | constant_values_(NULL), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 83 | use_counts_(arena, 256, kGrowableArrayMisc), |
| 84 | raw_use_counts_(arena, 256, kGrowableArrayMisc), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 85 | num_reachable_blocks_(0), |
Jean Christophe Beyler | 4896d7b | 2014-05-01 15:36:22 -0700 | [diff] [blame] | 86 | max_num_reachable_blocks_(0), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 87 | dfs_order_(NULL), |
| 88 | dfs_post_order_(NULL), |
| 89 | dom_post_order_traversal_(NULL), |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 90 | topological_order_(nullptr), |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 91 | topological_order_loop_ends_(nullptr), |
| 92 | topological_order_indexes_(nullptr), |
| 93 | topological_order_loop_head_stack_(nullptr), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 94 | i_dom_list_(NULL), |
| 95 | def_block_matrix_(NULL), |
Vladimir Marko | bfea9c2 | 2014-01-17 17:49:33 +0000 | [diff] [blame] | 96 | temp_scoped_alloc_(), |
| 97 | temp_insn_data_(nullptr), |
| 98 | temp_bit_vector_size_(0u), |
| 99 | temp_bit_vector_(nullptr), |
Vladimir Marko | 95a0597 | 2014-05-30 10:01:32 +0100 | [diff] [blame] | 100 | temp_gvn_(), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 101 | block_list_(arena, 100, kGrowableArrayBlockList), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 102 | try_block_addr_(NULL), |
| 103 | entry_block_(NULL), |
| 104 | exit_block_(NULL), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 105 | num_blocks_(0), |
| 106 | current_code_item_(NULL), |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 107 | dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), |
Vladimir Marko | 8081d2b | 2014-07-31 15:33:43 +0100 | [diff] [blame] | 108 | m_units_(arena->Adapter()), |
| 109 | method_stack_(arena->Adapter()), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 110 | current_method_(kInvalidEntry), |
| 111 | current_offset_(kInvalidEntry), |
| 112 | def_count_(0), |
| 113 | opcode_count_(NULL), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 114 | num_ssa_regs_(0), |
Vladimir Marko | 8081d2b | 2014-07-31 15:33:43 +0100 | [diff] [blame] | 115 | extended_basic_blocks_(arena->Adapter()), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 116 | method_sreg_(0), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 117 | attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. |
| 118 | checkstats_(NULL), |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 119 | arena_(arena), |
| 120 | backward_branches_(0), |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame] | 121 | forward_branches_(0), |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame] | 122 | num_non_special_compiler_temps_(0), |
Razvan A Lupusoru | 8d0d03e | 2014-06-06 17:04:52 -0700 | [diff] [blame] | 123 | max_available_special_compiler_temps_(1), // We only need the method ptr as a special temp for now. |
| 124 | requested_backend_temp_(false), |
| 125 | compiler_temps_committed_(false), |
Vladimir Marko | be0e546 | 2014-02-26 11:24:15 +0000 | [diff] [blame] | 126 | punt_to_interpreter_(false), |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 127 | merged_df_flags_(0u), |
Vladimir Marko | be0e546 | 2014-02-26 11:24:15 +0000 | [diff] [blame] | 128 | ifield_lowering_infos_(arena, 0u), |
Vladimir Marko | f096aad | 2014-01-23 15:51:58 +0000 | [diff] [blame] | 129 | sfield_lowering_infos_(arena, 0u), |
Wei Jin | 04f4d8a | 2014-05-29 18:04:29 -0700 | [diff] [blame] | 130 | method_lowering_infos_(arena, 0u), |
| 131 | gen_suspend_test_list_(arena, 0u) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 132 | try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); |
Razvan A Lupusoru | 8d0d03e | 2014-06-06 17:04:52 -0700 | [diff] [blame] | 133 | |
| 134 | |
| 135 | if (cu_->instruction_set == kX86 || cu_->instruction_set == kX86_64) { |
| 136 | // X86 requires a temp to keep track of the method address. |
| 137 | // TODO For x86_64, addressing can be done with RIP. When that is implemented, |
| 138 | // this needs to be updated to reserve 0 temps for BE. |
| 139 | max_available_non_special_compiler_temps_ = cu_->target64 ? 2 : 1; |
| 140 | reserved_temps_for_backend_ = max_available_non_special_compiler_temps_; |
| 141 | } else { |
| 142 | // Other architectures do not have a known lower bound for non-special temps. |
| 143 | // We allow the update of the max to happen at BE initialization stage and simply set 0 for now. |
| 144 | max_available_non_special_compiler_temps_ = 0; |
| 145 | reserved_temps_for_backend_ = 0; |
| 146 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 147 | } |
| 148 | |
Ian Rogers | 6282dc1 | 2013-04-18 15:54:02 -0700 | [diff] [blame] | 149 | MIRGraph::~MIRGraph() { |
| 150 | STLDeleteElements(&m_units_); |
| 151 | } |
| 152 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 153 | /* |
| 154 | * Parse an instruction, return the length of the instruction |
| 155 | */ |
Ian Rogers | 29a2648 | 2014-05-02 15:27:29 -0700 | [diff] [blame] | 156 | int MIRGraph::ParseInsn(const uint16_t* code_ptr, MIR::DecodedInstruction* decoded_instruction) { |
| 157 | const Instruction* inst = Instruction::At(code_ptr); |
| 158 | decoded_instruction->opcode = inst->Opcode(); |
| 159 | decoded_instruction->vA = inst->HasVRegA() ? inst->VRegA() : 0; |
| 160 | decoded_instruction->vB = inst->HasVRegB() ? inst->VRegB() : 0; |
| 161 | decoded_instruction->vB_wide = inst->HasWideVRegB() ? inst->WideVRegB() : 0; |
| 162 | decoded_instruction->vC = inst->HasVRegC() ? inst->VRegC() : 0; |
| 163 | if (inst->HasVarArgs()) { |
| 164 | inst->GetVarArgs(decoded_instruction->arg); |
| 165 | } |
| 166 | return inst->SizeInCodeUnits(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 167 | } |
| 168 | |
| 169 | |
| 170 | /* Split an existing block from the specified code offset into two */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 171 | BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 172 | BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 173 | DCHECK_GT(code_offset, orig_block->start_offset); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 174 | MIR* insn = orig_block->first_mir_insn; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 175 | MIR* prev = NULL; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 176 | while (insn) { |
| 177 | if (insn->offset == code_offset) break; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 178 | prev = insn; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 179 | insn = insn->next; |
| 180 | } |
| 181 | if (insn == NULL) { |
| 182 | LOG(FATAL) << "Break split failed"; |
| 183 | } |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 184 | BasicBlock* bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 185 | block_list_.Insert(bottom_block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 186 | |
| 187 | bottom_block->start_offset = code_offset; |
| 188 | bottom_block->first_mir_insn = insn; |
| 189 | bottom_block->last_mir_insn = orig_block->last_mir_insn; |
| 190 | |
Junmo Park | 90223cc | 2014-08-04 18:51:21 +0900 | [diff] [blame] | 191 | /* If this block was terminated by a return, conditional branch or throw, |
| 192 | * the flag needs to go with the bottom block |
| 193 | */ |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 194 | bottom_block->terminated_by_return = orig_block->terminated_by_return; |
| 195 | orig_block->terminated_by_return = false; |
| 196 | |
Junmo Park | 90223cc | 2014-08-04 18:51:21 +0900 | [diff] [blame] | 197 | bottom_block->conditional_branch = orig_block->conditional_branch; |
| 198 | orig_block->conditional_branch = false; |
| 199 | |
| 200 | bottom_block->explicit_throw = orig_block->explicit_throw; |
| 201 | orig_block->explicit_throw = false; |
| 202 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 203 | /* Handle the taken path */ |
| 204 | bottom_block->taken = orig_block->taken; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 205 | if (bottom_block->taken != NullBasicBlockId) { |
| 206 | orig_block->taken = NullBasicBlockId; |
| 207 | BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); |
| 208 | bb_taken->predecessors->Delete(orig_block->id); |
| 209 | bb_taken->predecessors->Insert(bottom_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 210 | } |
| 211 | |
| 212 | /* Handle the fallthrough path */ |
| 213 | bottom_block->fall_through = orig_block->fall_through; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 214 | orig_block->fall_through = bottom_block->id; |
| 215 | bottom_block->predecessors->Insert(orig_block->id); |
| 216 | if (bottom_block->fall_through != NullBasicBlockId) { |
| 217 | BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); |
| 218 | bb_fall_through->predecessors->Delete(orig_block->id); |
| 219 | bb_fall_through->predecessors->Insert(bottom_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 220 | } |
| 221 | |
| 222 | /* Handle the successor list */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 223 | if (orig_block->successor_block_list_type != kNotUsed) { |
| 224 | bottom_block->successor_block_list_type = orig_block->successor_block_list_type; |
| 225 | bottom_block->successor_blocks = orig_block->successor_blocks; |
| 226 | orig_block->successor_block_list_type = kNotUsed; |
Niranjan Kumar | 989367a | 2014-06-12 12:15:48 -0700 | [diff] [blame] | 227 | orig_block->successor_blocks = nullptr; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 228 | GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 229 | while (true) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 230 | SuccessorBlockInfo* successor_block_info = iterator.Next(); |
Niranjan Kumar | 989367a | 2014-06-12 12:15:48 -0700 | [diff] [blame] | 231 | if (successor_block_info == nullptr) break; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 232 | BasicBlock* bb = GetBasicBlock(successor_block_info->block); |
Niranjan Kumar | 989367a | 2014-06-12 12:15:48 -0700 | [diff] [blame] | 233 | if (bb != nullptr) { |
| 234 | bb->predecessors->Delete(orig_block->id); |
| 235 | bb->predecessors->Insert(bottom_block->id); |
| 236 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 237 | } |
| 238 | } |
| 239 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 240 | orig_block->last_mir_insn = prev; |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 241 | prev->next = nullptr; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 242 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 243 | /* |
| 244 | * Update the immediate predecessor block pointer so that outgoing edges |
| 245 | * can be applied to the proper block. |
| 246 | */ |
| 247 | if (immed_pred_block_p) { |
| 248 | DCHECK_EQ(*immed_pred_block_p, orig_block); |
| 249 | *immed_pred_block_p = bottom_block; |
| 250 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 251 | |
| 252 | // Associate dex instructions in the bottom block with the new container. |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 253 | DCHECK(insn != nullptr); |
| 254 | DCHECK(insn != orig_block->first_mir_insn); |
| 255 | DCHECK(insn == bottom_block->first_mir_insn); |
| 256 | DCHECK_EQ(insn->offset, bottom_block->start_offset); |
| 257 | DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || |
Jean Christophe Beyler | 2ab40eb | 2014-06-02 09:03:14 -0700 | [diff] [blame] | 258 | !MIR::DecodedInstruction::IsPseudoMirOp(insn->dalvikInsn.opcode)); |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 259 | DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); |
| 260 | MIR* p = insn; |
| 261 | dex_pc_to_block_map_.Put(p->offset, bottom_block->id); |
| 262 | while (p != bottom_block->last_mir_insn) { |
| 263 | p = p->next; |
| 264 | DCHECK(p != nullptr); |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 265 | p->bb = bottom_block->id; |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 266 | int opcode = p->dalvikInsn.opcode; |
| 267 | /* |
| 268 | * Some messiness here to ensure that we only enter real opcodes and only the |
| 269 | * first half of a potentially throwing instruction that has been split into |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 270 | * CHECK and work portions. Since the 2nd half of a split operation is always |
| 271 | * the first in a BasicBlock, we can't hit it here. |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 272 | */ |
Jean Christophe Beyler | 2ab40eb | 2014-06-02 09:03:14 -0700 | [diff] [blame] | 273 | if ((opcode == kMirOpCheck) || !MIR::DecodedInstruction::IsPseudoMirOp(opcode)) { |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 274 | DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 275 | dex_pc_to_block_map_.Put(p->offset, bottom_block->id); |
| 276 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 277 | } |
| 278 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 279 | return bottom_block; |
| 280 | } |
| 281 | |
| 282 | /* |
| 283 | * Given a code offset, find out the block that starts with it. If the offset |
| 284 | * is in the middle of an existing block, split it into two. If immed_pred_block_p |
| 285 | * is not non-null and is the block being split, update *immed_pred_block_p to |
| 286 | * point to the bottom block so that outgoing edges can be set up properly |
| 287 | * (by the caller) |
| 288 | * Utilizes a map for fast lookup of the typical cases. |
| 289 | */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 290 | BasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 291 | BasicBlock** immed_pred_block_p) { |
Razvan A Lupusoru | 09ae022 | 2014-07-07 16:29:37 -0700 | [diff] [blame] | 292 | if (code_offset >= current_code_item_->insns_size_in_code_units_) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 293 | return NULL; |
| 294 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 295 | |
| 296 | int block_id = dex_pc_to_block_map_.Get(code_offset); |
| 297 | BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); |
| 298 | |
| 299 | if ((bb != NULL) && (bb->start_offset == code_offset)) { |
| 300 | // Does this containing block start with the desired instruction? |
buzbee | bd663de | 2013-09-10 15:41:31 -0700 | [diff] [blame] | 301 | return bb; |
| 302 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 303 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 304 | // No direct hit. |
| 305 | if (!create) { |
| 306 | return NULL; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 307 | } |
| 308 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 309 | if (bb != NULL) { |
| 310 | // The target exists somewhere in an existing block. |
| 311 | return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : NULL); |
| 312 | } |
| 313 | |
| 314 | // Create a new block. |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 315 | bb = NewMemBB(kDalvikByteCode, num_blocks_++); |
| 316 | block_list_.Insert(bb); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 317 | bb->start_offset = code_offset; |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 318 | dex_pc_to_block_map_.Put(bb->start_offset, bb->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 319 | return bb; |
| 320 | } |
| 321 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 322 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 323 | /* Identify code range in try blocks and set up the empty catch blocks */ |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 324 | void MIRGraph::ProcessTryCatchBlocks() { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 325 | int tries_size = current_code_item_->tries_size_; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 326 | DexOffset offset; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 327 | |
| 328 | if (tries_size == 0) { |
| 329 | return; |
| 330 | } |
| 331 | |
| 332 | for (int i = 0; i < tries_size; i++) { |
| 333 | const DexFile::TryItem* pTry = |
| 334 | DexFile::GetTryItems(*current_code_item_, i); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 335 | DexOffset start_offset = pTry->start_addr_; |
| 336 | DexOffset end_offset = start_offset + pTry->insn_count_; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 337 | for (offset = start_offset; offset < end_offset; offset++) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 338 | try_block_addr_->SetBit(offset); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 339 | } |
| 340 | } |
| 341 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 342 | // Iterate over each of the handlers to enqueue the empty Catch blocks. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 343 | const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); |
| 344 | uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); |
| 345 | for (uint32_t idx = 0; idx < handlers_size; idx++) { |
| 346 | CatchHandlerIterator iterator(handlers_ptr); |
| 347 | for (; iterator.HasNext(); iterator.Next()) { |
| 348 | uint32_t address = iterator.GetHandlerAddress(); |
| 349 | FindBlock(address, false /* split */, true /*create*/, |
| 350 | /* immed_pred_block_p */ NULL); |
| 351 | } |
| 352 | handlers_ptr = iterator.EndDataPointer(); |
| 353 | } |
| 354 | } |
| 355 | |
Vladimir Marko | e8ae814 | 2014-07-08 18:06:45 +0100 | [diff] [blame] | 356 | bool MIRGraph::IsBadMonitorExitCatch(NarrowDexOffset monitor_exit_offset, |
| 357 | NarrowDexOffset catch_offset) { |
| 358 | // Catches for monitor-exit during stack unwinding have the pattern |
| 359 | // move-exception (move)* (goto)? monitor-exit throw |
| 360 | // In the currently generated dex bytecode we see these catching a bytecode range including |
| 361 | // either its own or an identical monitor-exit, http://b/15745363 . This function checks if |
| 362 | // it's the case for a given monitor-exit and catch block so that we can ignore it. |
| 363 | // (We don't want to ignore all monitor-exit catches since one could enclose a synchronized |
| 364 | // block in a try-block and catch the NPE, Error or Throwable and we should let it through; |
| 365 | // even though a throwing monitor-exit certainly indicates a bytecode error.) |
Razvan A Lupusoru | 09ae022 | 2014-07-07 16:29:37 -0700 | [diff] [blame] | 366 | const Instruction* monitor_exit = Instruction::At(current_code_item_->insns_ + monitor_exit_offset); |
Vladimir Marko | e8ae814 | 2014-07-08 18:06:45 +0100 | [diff] [blame] | 367 | DCHECK(monitor_exit->Opcode() == Instruction::MONITOR_EXIT); |
| 368 | int monitor_reg = monitor_exit->VRegA_11x(); |
Razvan A Lupusoru | 09ae022 | 2014-07-07 16:29:37 -0700 | [diff] [blame] | 369 | const Instruction* check_insn = Instruction::At(current_code_item_->insns_ + catch_offset); |
Vladimir Marko | e8ae814 | 2014-07-08 18:06:45 +0100 | [diff] [blame] | 370 | DCHECK(check_insn->Opcode() == Instruction::MOVE_EXCEPTION); |
| 371 | if (check_insn->VRegA_11x() == monitor_reg) { |
| 372 | // Unexpected move-exception to the same register. Probably not the pattern we're looking for. |
| 373 | return false; |
| 374 | } |
| 375 | check_insn = check_insn->Next(); |
| 376 | while (true) { |
| 377 | int dest = -1; |
| 378 | bool wide = false; |
| 379 | switch (check_insn->Opcode()) { |
| 380 | case Instruction::MOVE_WIDE: |
| 381 | wide = true; |
| 382 | // Intentional fall-through. |
| 383 | case Instruction::MOVE_OBJECT: |
| 384 | case Instruction::MOVE: |
| 385 | dest = check_insn->VRegA_12x(); |
| 386 | break; |
| 387 | |
| 388 | case Instruction::MOVE_WIDE_FROM16: |
| 389 | wide = true; |
| 390 | // Intentional fall-through. |
| 391 | case Instruction::MOVE_OBJECT_FROM16: |
| 392 | case Instruction::MOVE_FROM16: |
| 393 | dest = check_insn->VRegA_22x(); |
| 394 | break; |
| 395 | |
| 396 | case Instruction::MOVE_WIDE_16: |
| 397 | wide = true; |
| 398 | // Intentional fall-through. |
| 399 | case Instruction::MOVE_OBJECT_16: |
| 400 | case Instruction::MOVE_16: |
| 401 | dest = check_insn->VRegA_32x(); |
| 402 | break; |
| 403 | |
| 404 | case Instruction::GOTO: |
| 405 | case Instruction::GOTO_16: |
| 406 | case Instruction::GOTO_32: |
| 407 | check_insn = check_insn->RelativeAt(check_insn->GetTargetOffset()); |
| 408 | // Intentional fall-through. |
| 409 | default: |
| 410 | return check_insn->Opcode() == Instruction::MONITOR_EXIT && |
| 411 | check_insn->VRegA_11x() == monitor_reg; |
| 412 | } |
| 413 | |
| 414 | if (dest == monitor_reg || (wide && dest + 1 == monitor_reg)) { |
| 415 | return false; |
| 416 | } |
| 417 | |
| 418 | check_insn = check_insn->Next(); |
| 419 | } |
| 420 | } |
| 421 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 422 | /* Process instructions with the kBranch flag */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 423 | BasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, |
| 424 | int width, int flags, const uint16_t* code_ptr, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 425 | const uint16_t* code_end) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 426 | DexOffset target = cur_offset; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 427 | switch (insn->dalvikInsn.opcode) { |
| 428 | case Instruction::GOTO: |
| 429 | case Instruction::GOTO_16: |
| 430 | case Instruction::GOTO_32: |
| 431 | target += insn->dalvikInsn.vA; |
| 432 | break; |
| 433 | case Instruction::IF_EQ: |
| 434 | case Instruction::IF_NE: |
| 435 | case Instruction::IF_LT: |
| 436 | case Instruction::IF_GE: |
| 437 | case Instruction::IF_GT: |
| 438 | case Instruction::IF_LE: |
| 439 | cur_block->conditional_branch = true; |
| 440 | target += insn->dalvikInsn.vC; |
| 441 | break; |
| 442 | case Instruction::IF_EQZ: |
| 443 | case Instruction::IF_NEZ: |
| 444 | case Instruction::IF_LTZ: |
| 445 | case Instruction::IF_GEZ: |
| 446 | case Instruction::IF_GTZ: |
| 447 | case Instruction::IF_LEZ: |
| 448 | cur_block->conditional_branch = true; |
| 449 | target += insn->dalvikInsn.vB; |
| 450 | break; |
| 451 | default: |
| 452 | LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; |
| 453 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 454 | CountBranch(target); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 455 | BasicBlock* taken_block = FindBlock(target, /* split */ true, /* create */ true, |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 456 | /* immed_pred_block_p */ &cur_block); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 457 | cur_block->taken = taken_block->id; |
| 458 | taken_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 459 | |
| 460 | /* Always terminate the current block for conditional branches */ |
| 461 | if (flags & Instruction::kContinue) { |
Jean Christophe Beyler | 2469e60 | 2014-05-06 20:36:55 -0700 | [diff] [blame] | 462 | BasicBlock* fallthrough_block = FindBlock(cur_offset + width, |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 463 | /* |
| 464 | * If the method is processed |
| 465 | * in sequential order from the |
| 466 | * beginning, we don't need to |
| 467 | * specify split for continue |
| 468 | * blocks. However, this |
| 469 | * routine can be called by |
| 470 | * compileLoop, which starts |
| 471 | * parsing the method from an |
| 472 | * arbitrary address in the |
| 473 | * method body. |
| 474 | */ |
| 475 | true, |
| 476 | /* create */ |
| 477 | true, |
| 478 | /* immed_pred_block_p */ |
| 479 | &cur_block); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 480 | cur_block->fall_through = fallthrough_block->id; |
| 481 | fallthrough_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 482 | } else if (code_ptr < code_end) { |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 483 | FindBlock(cur_offset + width, /* split */ false, /* create */ true, |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 484 | /* immed_pred_block_p */ NULL); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 485 | } |
| 486 | return cur_block; |
| 487 | } |
| 488 | |
| 489 | /* Process instructions with the kSwitch flag */ |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 490 | BasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, |
| 491 | int width, int flags) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 492 | const uint16_t* switch_data = |
| 493 | reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); |
| 494 | int size; |
| 495 | const int* keyTable; |
| 496 | const int* target_table; |
| 497 | int i; |
| 498 | int first_key; |
| 499 | |
| 500 | /* |
| 501 | * Packed switch data format: |
| 502 | * ushort ident = 0x0100 magic value |
| 503 | * ushort size number of entries in the table |
| 504 | * int first_key first (and lowest) switch case value |
| 505 | * int targets[size] branch targets, relative to switch opcode |
| 506 | * |
| 507 | * Total size is (4+size*2) 16-bit code units. |
| 508 | */ |
| 509 | if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { |
| 510 | DCHECK_EQ(static_cast<int>(switch_data[0]), |
| 511 | static_cast<int>(Instruction::kPackedSwitchSignature)); |
| 512 | size = switch_data[1]; |
| 513 | first_key = switch_data[2] | (switch_data[3] << 16); |
| 514 | target_table = reinterpret_cast<const int*>(&switch_data[4]); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 515 | keyTable = NULL; // Make the compiler happy. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 516 | /* |
| 517 | * Sparse switch data format: |
| 518 | * ushort ident = 0x0200 magic value |
| 519 | * ushort size number of entries in the table; > 0 |
| 520 | * int keys[size] keys, sorted low-to-high; 32-bit aligned |
| 521 | * int targets[size] branch targets, relative to switch opcode |
| 522 | * |
| 523 | * Total size is (2+size*4) 16-bit code units. |
| 524 | */ |
| 525 | } else { |
| 526 | DCHECK_EQ(static_cast<int>(switch_data[0]), |
| 527 | static_cast<int>(Instruction::kSparseSwitchSignature)); |
| 528 | size = switch_data[1]; |
| 529 | keyTable = reinterpret_cast<const int*>(&switch_data[2]); |
| 530 | target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 531 | first_key = 0; // To make the compiler happy. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 532 | } |
| 533 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 534 | if (cur_block->successor_block_list_type != kNotUsed) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 535 | LOG(FATAL) << "Successor block list already in use: " |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 536 | << static_cast<int>(cur_block->successor_block_list_type); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 537 | } |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 538 | cur_block->successor_block_list_type = |
| 539 | (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; |
| 540 | cur_block->successor_blocks = |
Brian Carlstrom | df62950 | 2013-07-17 22:39:56 -0700 | [diff] [blame] | 541 | new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 542 | |
| 543 | for (i = 0; i < size; i++) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 544 | BasicBlock* case_block = FindBlock(cur_offset + target_table[i], /* split */ true, |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 545 | /* create */ true, /* immed_pred_block_p */ &cur_block); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 546 | SuccessorBlockInfo* successor_block_info = |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 547 | static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 548 | kArenaAllocSuccessor)); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 549 | successor_block_info->block = case_block->id; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 550 | successor_block_info->key = |
| 551 | (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? |
| 552 | first_key + i : keyTable[i]; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 553 | cur_block->successor_blocks->Insert(successor_block_info); |
| 554 | case_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 555 | } |
| 556 | |
| 557 | /* Fall-through case */ |
Brian Carlstrom | df62950 | 2013-07-17 22:39:56 -0700 | [diff] [blame] | 558 | BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, |
| 559 | /* create */ true, /* immed_pred_block_p */ NULL); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 560 | cur_block->fall_through = fallthrough_block->id; |
| 561 | fallthrough_block->predecessors->Insert(cur_block->id); |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 562 | return cur_block; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 563 | } |
| 564 | |
| 565 | /* Process instructions with the kThrow flag */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 566 | BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, |
| 567 | int width, int flags, ArenaBitVector* try_block_addr, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 568 | const uint16_t* code_ptr, const uint16_t* code_end) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 569 | bool in_try_block = try_block_addr->IsBitSet(cur_offset); |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 570 | bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); |
| 571 | bool build_all_edges = |
| 572 | (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 573 | |
| 574 | /* In try block */ |
| 575 | if (in_try_block) { |
| 576 | CatchHandlerIterator iterator(*current_code_item_, cur_offset); |
| 577 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 578 | if (cur_block->successor_block_list_type != kNotUsed) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 579 | LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); |
| 580 | LOG(FATAL) << "Successor block list already in use: " |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 581 | << static_cast<int>(cur_block->successor_block_list_type); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 582 | } |
| 583 | |
Brian Carlstrom | 02c8cc6 | 2013-07-18 15:54:44 -0700 | [diff] [blame] | 584 | for (; iterator.HasNext(); iterator.Next()) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 585 | BasicBlock* catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 586 | false /* creat */, NULL /* immed_pred_block_p */); |
Vladimir Marko | e8ae814 | 2014-07-08 18:06:45 +0100 | [diff] [blame] | 587 | if (insn->dalvikInsn.opcode == Instruction::MONITOR_EXIT && |
| 588 | IsBadMonitorExitCatch(insn->offset, catch_block->start_offset)) { |
| 589 | // Don't allow monitor-exit to catch its own exception, http://b/15745363 . |
| 590 | continue; |
| 591 | } |
| 592 | if (cur_block->successor_block_list_type == kNotUsed) { |
| 593 | cur_block->successor_block_list_type = kCatch; |
| 594 | cur_block->successor_blocks = new (arena_) GrowableArray<SuccessorBlockInfo*>( |
| 595 | arena_, 2, kGrowableArraySuccessorBlocks); |
| 596 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 597 | catch_block->catch_entry = true; |
| 598 | if (kIsDebugBuild) { |
| 599 | catches_.insert(catch_block->start_offset); |
| 600 | } |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 601 | SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 602 | (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 603 | successor_block_info->block = catch_block->id; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 604 | successor_block_info->key = iterator.GetHandlerTypeIndex(); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 605 | cur_block->successor_blocks->Insert(successor_block_info); |
| 606 | catch_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 607 | } |
Vladimir Marko | e8ae814 | 2014-07-08 18:06:45 +0100 | [diff] [blame] | 608 | in_try_block = (cur_block->successor_block_list_type != kNotUsed); |
| 609 | } |
| 610 | if (!in_try_block && build_all_edges) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 611 | BasicBlock* eh_block = NewMemBB(kExceptionHandling, num_blocks_++); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 612 | cur_block->taken = eh_block->id; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 613 | block_list_.Insert(eh_block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 614 | eh_block->start_offset = cur_offset; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 615 | eh_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 616 | } |
| 617 | |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 618 | if (is_throw) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 619 | cur_block->explicit_throw = true; |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 620 | if (code_ptr < code_end) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 621 | // Force creation of new block following THROW via side-effect. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 622 | FindBlock(cur_offset + width, /* split */ false, /* create */ true, |
| 623 | /* immed_pred_block_p */ NULL); |
| 624 | } |
| 625 | if (!in_try_block) { |
| 626 | // Don't split a THROW that can't rethrow - we're done. |
| 627 | return cur_block; |
| 628 | } |
| 629 | } |
| 630 | |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 631 | if (!build_all_edges) { |
| 632 | /* |
| 633 | * Even though there is an exception edge here, control cannot return to this |
| 634 | * method. Thus, for the purposes of dataflow analysis and optimization, we can |
| 635 | * ignore the edge. Doing this reduces compile time, and increases the scope |
| 636 | * of the basic-block level optimization pass. |
| 637 | */ |
| 638 | return cur_block; |
| 639 | } |
| 640 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 641 | /* |
| 642 | * Split the potentially-throwing instruction into two parts. |
| 643 | * The first half will be a pseudo-op that captures the exception |
| 644 | * edges and terminates the basic block. It always falls through. |
| 645 | * Then, create a new basic block that begins with the throwing instruction |
| 646 | * (minus exceptions). Note: this new basic block must NOT be entered into |
| 647 | * the block_map. If the potentially-throwing instruction is the target of a |
| 648 | * future branch, we need to find the check psuedo half. The new |
| 649 | * basic block containing the work portion of the instruction should |
| 650 | * only be entered via fallthrough from the block containing the |
| 651 | * pseudo exception edge MIR. Note also that this new block is |
| 652 | * not automatically terminated after the work portion, and may |
| 653 | * contain following instructions. |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 654 | * |
| 655 | * Note also that the dex_pc_to_block_map_ entry for the potentially |
| 656 | * throwing instruction will refer to the original basic block. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 657 | */ |
Jean Christophe Beyler | 2469e60 | 2014-05-06 20:36:55 -0700 | [diff] [blame] | 658 | BasicBlock* new_block = NewMemBB(kDalvikByteCode, num_blocks_++); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 659 | block_list_.Insert(new_block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 660 | new_block->start_offset = insn->offset; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 661 | cur_block->fall_through = new_block->id; |
| 662 | new_block->predecessors->Insert(cur_block->id); |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 663 | MIR* new_insn = NewMIR(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 664 | *new_insn = *insn; |
buzbee | 35ba7f3 | 2014-05-31 08:59:01 -0700 | [diff] [blame] | 665 | insn->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpCheck); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 666 | // Associate the two halves. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 667 | insn->meta.throw_insn = new_insn; |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 668 | new_block->AppendMIR(new_insn); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 669 | return new_block; |
| 670 | } |
| 671 | |
| 672 | /* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ |
| 673 | void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, |
Ian Rogers | 8b2c0b9 | 2013-09-19 02:56:49 -0700 | [diff] [blame] | 674 | InvokeType invoke_type, uint16_t class_def_idx, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 675 | uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 676 | current_code_item_ = code_item; |
| 677 | method_stack_.push_back(std::make_pair(current_method_, current_offset_)); |
| 678 | current_method_ = m_units_.size(); |
| 679 | current_offset_ = 0; |
| 680 | // TODO: will need to snapshot stack image and use that as the mir context identification. |
| 681 | m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), |
Vladimir Marko | 2730db0 | 2014-01-27 11:15:17 +0000 | [diff] [blame] | 682 | dex_file, current_code_item_, class_def_idx, method_idx, access_flags, |
| 683 | cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 684 | const uint16_t* code_ptr = current_code_item_->insns_; |
| 685 | const uint16_t* code_end = |
| 686 | current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; |
| 687 | |
| 688 | // TODO: need to rework expansion of block list & try_block_addr when inlining activated. |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 689 | // TUNING: use better estimate of basic blocks for following resize. |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 690 | block_list_.Resize(block_list_.Size() + current_code_item_->insns_size_in_code_units_); |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 691 | dex_pc_to_block_map_.SetSize(dex_pc_to_block_map_.Size() + current_code_item_->insns_size_in_code_units_); |
buzbee | bd663de | 2013-09-10 15:41:31 -0700 | [diff] [blame] | 692 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 693 | // TODO: replace with explicit resize routine. Using automatic extension side effect for now. |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 694 | try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); |
| 695 | try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 696 | |
| 697 | // If this is the first method, set up default entry and exit blocks. |
| 698 | if (current_method_ == 0) { |
| 699 | DCHECK(entry_block_ == NULL); |
| 700 | DCHECK(exit_block_ == NULL); |
Andreas Gampe | 4439596 | 2014-06-13 13:44:40 -0700 | [diff] [blame] | 701 | DCHECK_EQ(num_blocks_, 0U); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 702 | // Use id 0 to represent a null block. |
| 703 | BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); |
| 704 | DCHECK_EQ(null_block->id, NullBasicBlockId); |
| 705 | null_block->hidden = true; |
| 706 | block_list_.Insert(null_block); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 707 | entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 708 | block_list_.Insert(entry_block_); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 709 | exit_block_ = NewMemBB(kExitBlock, num_blocks_++); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 710 | block_list_.Insert(exit_block_); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 711 | // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. |
| 712 | cu_->dex_file = &dex_file; |
| 713 | cu_->class_def_idx = class_def_idx; |
| 714 | cu_->method_idx = method_idx; |
| 715 | cu_->access_flags = access_flags; |
| 716 | cu_->invoke_type = invoke_type; |
| 717 | cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 718 | cu_->code_item = current_code_item_; |
| 719 | } else { |
| 720 | UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; |
| 721 | /* |
| 722 | * Will need to manage storage for ins & outs, push prevous state and update |
| 723 | * insert point. |
| 724 | */ |
| 725 | } |
| 726 | |
| 727 | /* Current block to record parsed instructions */ |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 728 | BasicBlock* cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 729 | DCHECK_EQ(current_offset_, 0U); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 730 | cur_block->start_offset = current_offset_; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 731 | block_list_.Insert(cur_block); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 732 | // TODO: for inlining support, insert at the insert point rather than entry block. |
| 733 | entry_block_->fall_through = cur_block->id; |
| 734 | cur_block->predecessors->Insert(entry_block_->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 735 | |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 736 | /* Identify code range in try blocks and set up the empty catch blocks */ |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 737 | ProcessTryCatchBlocks(); |
| 738 | |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 739 | uint64_t merged_df_flags = 0u; |
| 740 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 741 | /* Parse all instructions and put them into containing basic blocks */ |
| 742 | while (code_ptr < code_end) { |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 743 | MIR *insn = NewMIR(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 744 | insn->offset = current_offset_; |
| 745 | insn->m_unit_index = current_method_; |
| 746 | int width = ParseInsn(code_ptr, &insn->dalvikInsn); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 747 | Instruction::Code opcode = insn->dalvikInsn.opcode; |
| 748 | if (opcode_count_ != NULL) { |
| 749 | opcode_count_[static_cast<int>(opcode)]++; |
| 750 | } |
| 751 | |
Jean Christophe Beyler | fb0ea2d | 2014-07-29 13:20:42 -0700 | [diff] [blame] | 752 | int flags = insn->dalvikInsn.FlagsOf(); |
buzbee | b1f1d64 | 2014-02-27 12:55:32 -0800 | [diff] [blame] | 753 | int verify_flags = Instruction::VerifyFlagsOf(insn->dalvikInsn.opcode); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 754 | |
Jean Christophe Beyler | cc794c3 | 2014-05-02 09:34:13 -0700 | [diff] [blame] | 755 | uint64_t df_flags = GetDataFlowAttributes(insn); |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 756 | merged_df_flags |= df_flags; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 757 | |
| 758 | if (df_flags & DF_HAS_DEFS) { |
| 759 | def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; |
| 760 | } |
| 761 | |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 762 | if (df_flags & DF_LVN) { |
| 763 | cur_block->use_lvn = true; // Run local value numbering on this basic block. |
| 764 | } |
| 765 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 766 | // Check for inline data block signatures. |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 767 | if (opcode == Instruction::NOP) { |
| 768 | // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. |
| 769 | if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { |
| 770 | // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. |
| 771 | uint16_t following_raw_instruction = code_ptr[1]; |
| 772 | if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || |
| 773 | (following_raw_instruction == Instruction::kPackedSwitchSignature) || |
| 774 | (following_raw_instruction == Instruction::kArrayDataSignature)) { |
| 775 | width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); |
| 776 | } |
| 777 | } |
| 778 | if (width == 1) { |
| 779 | // It is a simple nop - treat normally. |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 780 | cur_block->AppendMIR(insn); |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 781 | } else { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 782 | DCHECK(cur_block->fall_through == NullBasicBlockId); |
| 783 | DCHECK(cur_block->taken == NullBasicBlockId); |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 784 | // Unreachable instruction, mark for no continuation. |
| 785 | flags &= ~Instruction::kContinue; |
| 786 | } |
| 787 | } else { |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 788 | cur_block->AppendMIR(insn); |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 789 | } |
| 790 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 791 | // Associate the starting dex_pc for this opcode with its containing basic block. |
| 792 | dex_pc_to_block_map_.Put(insn->offset, cur_block->id); |
| 793 | |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 794 | code_ptr += width; |
| 795 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 796 | if (flags & Instruction::kBranch) { |
| 797 | cur_block = ProcessCanBranch(cur_block, insn, current_offset_, |
| 798 | width, flags, code_ptr, code_end); |
| 799 | } else if (flags & Instruction::kReturn) { |
| 800 | cur_block->terminated_by_return = true; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 801 | cur_block->fall_through = exit_block_->id; |
| 802 | exit_block_->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 803 | /* |
| 804 | * Terminate the current block if there are instructions |
| 805 | * afterwards. |
| 806 | */ |
| 807 | if (code_ptr < code_end) { |
| 808 | /* |
| 809 | * Create a fallthrough block for real instructions |
| 810 | * (incl. NOP). |
| 811 | */ |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 812 | FindBlock(current_offset_ + width, /* split */ false, /* create */ true, |
| 813 | /* immed_pred_block_p */ NULL); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 814 | } |
| 815 | } else if (flags & Instruction::kThrow) { |
| 816 | cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, |
| 817 | code_ptr, code_end); |
| 818 | } else if (flags & Instruction::kSwitch) { |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 819 | cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 820 | } |
Alexei Zavjalov | 688e7c5 | 2014-07-16 02:17:58 +0700 | [diff] [blame] | 821 | if (verify_flags & Instruction::kVerifyVarArgRange || |
| 822 | verify_flags & Instruction::kVerifyVarArgRangeNonZero) { |
buzbee | b1f1d64 | 2014-02-27 12:55:32 -0800 | [diff] [blame] | 823 | /* |
| 824 | * The Quick backend's runtime model includes a gap between a method's |
| 825 | * argument ("in") vregs and the rest of its vregs. Handling a range instruction |
| 826 | * which spans the gap is somewhat complicated, and should not happen |
| 827 | * in normal usage of dx. Punt to the interpreter. |
| 828 | */ |
| 829 | int first_reg_in_range = insn->dalvikInsn.vC; |
| 830 | int last_reg_in_range = first_reg_in_range + insn->dalvikInsn.vA - 1; |
| 831 | if (IsInVReg(first_reg_in_range) != IsInVReg(last_reg_in_range)) { |
| 832 | punt_to_interpreter_ = true; |
| 833 | } |
| 834 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 835 | current_offset_ += width; |
Jean Christophe Beyler | 2469e60 | 2014-05-06 20:36:55 -0700 | [diff] [blame] | 836 | BasicBlock* next_block = FindBlock(current_offset_, /* split */ false, /* create */ |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 837 | false, /* immed_pred_block_p */ NULL); |
| 838 | if (next_block) { |
| 839 | /* |
| 840 | * The next instruction could be the target of a previously parsed |
| 841 | * forward branch so a block is already created. If the current |
| 842 | * instruction is not an unconditional branch, connect them through |
| 843 | * the fall-through link. |
| 844 | */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 845 | DCHECK(cur_block->fall_through == NullBasicBlockId || |
| 846 | GetBasicBlock(cur_block->fall_through) == next_block || |
| 847 | GetBasicBlock(cur_block->fall_through) == exit_block_); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 848 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 849 | if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { |
| 850 | cur_block->fall_through = next_block->id; |
| 851 | next_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 852 | } |
| 853 | cur_block = next_block; |
| 854 | } |
| 855 | } |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 856 | merged_df_flags_ = merged_df_flags; |
Vladimir Marko | 5816ed4 | 2013-11-27 17:04:20 +0000 | [diff] [blame] | 857 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 858 | if (cu_->enable_debug & (1 << kDebugDumpCFG)) { |
| 859 | DumpCFG("/sdcard/1_post_parse_cfg/", true); |
| 860 | } |
| 861 | |
| 862 | if (cu_->verbose) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 863 | DumpMIRGraph(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 864 | } |
| 865 | } |
| 866 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 867 | void MIRGraph::ShowOpcodeStats() { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 868 | DCHECK(opcode_count_ != NULL); |
| 869 | LOG(INFO) << "Opcode Count"; |
| 870 | for (int i = 0; i < kNumPackedOpcodes; i++) { |
| 871 | if (opcode_count_[i] != 0) { |
| 872 | LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) |
| 873 | << " " << opcode_count_[i]; |
| 874 | } |
| 875 | } |
| 876 | } |
| 877 | |
Jean Christophe Beyler | cc794c3 | 2014-05-02 09:34:13 -0700 | [diff] [blame] | 878 | uint64_t MIRGraph::GetDataFlowAttributes(Instruction::Code opcode) { |
| 879 | DCHECK_LT((size_t) opcode, (sizeof(oat_data_flow_attributes_) / sizeof(oat_data_flow_attributes_[0]))); |
| 880 | return oat_data_flow_attributes_[opcode]; |
| 881 | } |
| 882 | |
| 883 | uint64_t MIRGraph::GetDataFlowAttributes(MIR* mir) { |
| 884 | DCHECK(mir != nullptr); |
| 885 | Instruction::Code opcode = mir->dalvikInsn.opcode; |
| 886 | return GetDataFlowAttributes(opcode); |
| 887 | } |
| 888 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 889 | // TODO: use a configurable base prefix, and adjust callers to supply pass name. |
| 890 | /* Dump the CFG into a DOT graph */ |
Jean Christophe Beyler | d0a5155 | 2014-01-10 14:18:31 -0800 | [diff] [blame] | 891 | void MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 892 | FILE* file; |
Jean Christophe Beyler | a8869e6 | 2014-06-19 09:34:51 -0700 | [diff] [blame] | 893 | static AtomicInteger cnt(0); |
| 894 | |
| 895 | // Increment counter to get a unique file number. |
| 896 | cnt++; |
| 897 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 898 | std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); |
| 899 | ReplaceSpecialChars(fname); |
Jean Christophe Beyler | a8869e6 | 2014-06-19 09:34:51 -0700 | [diff] [blame] | 900 | fname = StringPrintf("%s%s%x%s_%d.dot", dir_prefix, fname.c_str(), |
Jean Christophe Beyler | d0a5155 | 2014-01-10 14:18:31 -0800 | [diff] [blame] | 901 | GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, |
Jean Christophe Beyler | a8869e6 | 2014-06-19 09:34:51 -0700 | [diff] [blame] | 902 | suffix == nullptr ? "" : suffix, |
| 903 | cnt.LoadRelaxed()); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 904 | file = fopen(fname.c_str(), "w"); |
| 905 | if (file == NULL) { |
| 906 | return; |
| 907 | } |
| 908 | fprintf(file, "digraph G {\n"); |
| 909 | |
| 910 | fprintf(file, " rankdir=TB\n"); |
| 911 | |
| 912 | int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; |
| 913 | int idx; |
| 914 | |
| 915 | for (idx = 0; idx < num_blocks; idx++) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 916 | int block_idx = all_blocks ? idx : dfs_order_->Get(idx); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 917 | BasicBlock* bb = GetBasicBlock(block_idx); |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 918 | if (bb == NULL) continue; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 919 | if (bb->block_type == kDead) continue; |
Jean Christophe Beyler | a8869e6 | 2014-06-19 09:34:51 -0700 | [diff] [blame] | 920 | if (bb->hidden) continue; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 921 | if (bb->block_type == kEntryBlock) { |
| 922 | fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); |
| 923 | } else if (bb->block_type == kExitBlock) { |
| 924 | fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); |
| 925 | } else if (bb->block_type == kDalvikByteCode) { |
| 926 | fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", |
| 927 | bb->start_offset, bb->id); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 928 | const MIR* mir; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 929 | fprintf(file, " {block id %d\\l}%s\\\n", bb->id, |
| 930 | bb->first_mir_insn ? " | " : " "); |
| 931 | for (mir = bb->first_mir_insn; mir; mir = mir->next) { |
| 932 | int opcode = mir->dalvikInsn.opcode; |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 933 | fprintf(file, " {%04x %s %s %s %s %s %s %s\\l}%s\\\n", mir->offset, |
Mark Mendell | d65c51a | 2014-04-29 16:55:20 -0400 | [diff] [blame] | 934 | mir->ssa_rep ? GetDalvikDisassembly(mir) : |
Jean Christophe Beyler | 2ab40eb | 2014-06-02 09:03:14 -0700 | [diff] [blame] | 935 | !MIR::DecodedInstruction::IsPseudoMirOp(opcode) ? |
| 936 | Instruction::Name(mir->dalvikInsn.opcode) : |
Mark Mendell | d65c51a | 2014-04-29 16:55:20 -0400 | [diff] [blame] | 937 | extended_mir_op_names_[opcode - kMirOpFirst], |
| 938 | (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", |
| 939 | (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", |
Udayan Banerji | 60bfe7b | 2014-07-08 19:59:43 -0700 | [diff] [blame] | 940 | (mir->optimization_flags & MIR_IGNORE_SUSPEND_CHECK) != 0 ? " no_suspendcheck" : " ", |
Jean Christophe Beyler | b5bce7c | 2014-07-25 12:32:18 -0700 | [diff] [blame] | 941 | (mir->optimization_flags & MIR_STORE_NON_TEMPORAL) != 0 ? " non_temporal" : " ", |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 942 | (mir->optimization_flags & MIR_CALLEE) != 0 ? " inlined" : " ", |
| 943 | (mir->optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0 ? " no_clinit" : " ", |
Mark Mendell | d65c51a | 2014-04-29 16:55:20 -0400 | [diff] [blame] | 944 | mir->next ? " | " : " "); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 945 | } |
| 946 | fprintf(file, " }\"];\n\n"); |
| 947 | } else if (bb->block_type == kExceptionHandling) { |
| 948 | char block_name[BLOCK_NAME_LEN]; |
| 949 | |
| 950 | GetBlockName(bb, block_name); |
| 951 | fprintf(file, " %s [shape=invhouse];\n", block_name); |
| 952 | } |
| 953 | |
| 954 | char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; |
| 955 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 956 | if (bb->taken != NullBasicBlockId) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 957 | GetBlockName(bb, block_name1); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 958 | GetBlockName(GetBasicBlock(bb->taken), block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 959 | fprintf(file, " %s:s -> %s:n [style=dotted]\n", |
| 960 | block_name1, block_name2); |
| 961 | } |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 962 | if (bb->fall_through != NullBasicBlockId) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 963 | GetBlockName(bb, block_name1); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 964 | GetBlockName(GetBasicBlock(bb->fall_through), block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 965 | fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); |
| 966 | } |
| 967 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 968 | if (bb->successor_block_list_type != kNotUsed) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 969 | fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", |
| 970 | bb->start_offset, bb->id, |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 971 | (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); |
| 972 | GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 973 | SuccessorBlockInfo* successor_block_info = iterator.Next(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 974 | |
| 975 | int succ_id = 0; |
| 976 | while (true) { |
| 977 | if (successor_block_info == NULL) break; |
| 978 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 979 | BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 980 | SuccessorBlockInfo *next_successor_block_info = iterator.Next(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 981 | |
| 982 | fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", |
| 983 | succ_id++, |
| 984 | successor_block_info->key, |
| 985 | dest_block->start_offset, |
| 986 | (next_successor_block_info != NULL) ? " | " : " "); |
| 987 | |
| 988 | successor_block_info = next_successor_block_info; |
| 989 | } |
| 990 | fprintf(file, " }\"];\n\n"); |
| 991 | |
| 992 | GetBlockName(bb, block_name1); |
| 993 | fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", |
| 994 | block_name1, bb->start_offset, bb->id); |
| 995 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 996 | // Link the successor pseudo-block with all of its potential targets. |
| 997 | GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 998 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 999 | succ_id = 0; |
| 1000 | while (true) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1001 | SuccessorBlockInfo* successor_block_info = iter.Next(); |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 1002 | if (successor_block_info == NULL) break; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 1003 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 1004 | BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 1005 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 1006 | GetBlockName(dest_block, block_name2); |
| 1007 | fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, |
| 1008 | bb->id, succ_id++, block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 1009 | } |
| 1010 | } |
| 1011 | fprintf(file, "\n"); |
| 1012 | |
| 1013 | if (cu_->verbose) { |
| 1014 | /* Display the dominator tree */ |
| 1015 | GetBlockName(bb, block_name1); |
| 1016 | fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", |
| 1017 | block_name1, block_name1); |
| 1018 | if (bb->i_dom) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1019 | GetBlockName(GetBasicBlock(bb->i_dom), block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 1020 | fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); |
| 1021 | } |
| 1022 | } |
| 1023 | } |
| 1024 | fprintf(file, "}\n"); |
| 1025 | fclose(file); |
| 1026 | } |
| 1027 | |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1028 | /* Insert an MIR instruction to the end of a basic block. */ |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 1029 | void BasicBlock::AppendMIR(MIR* mir) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1030 | // Insert it after the last MIR. |
| 1031 | InsertMIRListAfter(last_mir_insn, mir, mir); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1032 | } |
| 1033 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1034 | void BasicBlock::AppendMIRList(MIR* first_list_mir, MIR* last_list_mir) { |
| 1035 | // Insert it after the last MIR. |
| 1036 | InsertMIRListAfter(last_mir_insn, first_list_mir, last_list_mir); |
| 1037 | } |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1038 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1039 | void BasicBlock::AppendMIRList(const std::vector<MIR*>& insns) { |
| 1040 | for (std::vector<MIR*>::const_iterator it = insns.begin(); it != insns.end(); it++) { |
| 1041 | MIR* new_mir = *it; |
| 1042 | |
| 1043 | // Add a copy of each MIR. |
| 1044 | InsertMIRListAfter(last_mir_insn, new_mir, new_mir); |
| 1045 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1046 | } |
| 1047 | |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1048 | /* Insert a MIR instruction after the specified MIR. */ |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 1049 | void BasicBlock::InsertMIRAfter(MIR* current_mir, MIR* new_mir) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1050 | InsertMIRListAfter(current_mir, new_mir, new_mir); |
| 1051 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1052 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1053 | void BasicBlock::InsertMIRListAfter(MIR* insert_after, MIR* first_list_mir, MIR* last_list_mir) { |
| 1054 | // If no MIR, we are done. |
| 1055 | if (first_list_mir == nullptr || last_list_mir == nullptr) { |
| 1056 | return; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1057 | } |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1058 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1059 | // If insert_after is null, assume BB is empty. |
| 1060 | if (insert_after == nullptr) { |
| 1061 | first_mir_insn = first_list_mir; |
| 1062 | last_mir_insn = last_list_mir; |
| 1063 | last_list_mir->next = nullptr; |
| 1064 | } else { |
| 1065 | MIR* after_list = insert_after->next; |
| 1066 | insert_after->next = first_list_mir; |
| 1067 | last_list_mir->next = after_list; |
| 1068 | if (after_list == nullptr) { |
| 1069 | last_mir_insn = last_list_mir; |
| 1070 | } |
| 1071 | } |
| 1072 | |
| 1073 | // Set this BB to be the basic block of the MIRs. |
| 1074 | MIR* last = last_list_mir->next; |
| 1075 | for (MIR* mir = first_list_mir; mir != last; mir = mir->next) { |
| 1076 | mir->bb = id; |
| 1077 | } |
| 1078 | } |
| 1079 | |
| 1080 | /* Insert an MIR instruction to the head of a basic block. */ |
| 1081 | void BasicBlock::PrependMIR(MIR* mir) { |
| 1082 | InsertMIRListBefore(first_mir_insn, mir, mir); |
| 1083 | } |
| 1084 | |
| 1085 | void BasicBlock::PrependMIRList(MIR* first_list_mir, MIR* last_list_mir) { |
| 1086 | // Insert it before the first MIR. |
| 1087 | InsertMIRListBefore(first_mir_insn, first_list_mir, last_list_mir); |
| 1088 | } |
| 1089 | |
| 1090 | void BasicBlock::PrependMIRList(const std::vector<MIR*>& to_add) { |
| 1091 | for (std::vector<MIR*>::const_iterator it = to_add.begin(); it != to_add.end(); it++) { |
| 1092 | MIR* mir = *it; |
| 1093 | |
| 1094 | InsertMIRListBefore(first_mir_insn, mir, mir); |
| 1095 | } |
| 1096 | } |
| 1097 | |
| 1098 | /* Insert a MIR instruction before the specified MIR. */ |
| 1099 | void BasicBlock::InsertMIRBefore(MIR* current_mir, MIR* new_mir) { |
| 1100 | // Insert as a single element list. |
| 1101 | return InsertMIRListBefore(current_mir, new_mir, new_mir); |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1102 | } |
| 1103 | |
| 1104 | MIR* BasicBlock::FindPreviousMIR(MIR* mir) { |
| 1105 | MIR* current = first_mir_insn; |
| 1106 | |
| 1107 | while (current != nullptr) { |
| 1108 | MIR* next = current->next; |
| 1109 | |
| 1110 | if (next == mir) { |
| 1111 | return current; |
| 1112 | } |
| 1113 | |
| 1114 | current = next; |
| 1115 | } |
| 1116 | |
| 1117 | return nullptr; |
| 1118 | } |
| 1119 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1120 | void BasicBlock::InsertMIRListBefore(MIR* insert_before, MIR* first_list_mir, MIR* last_list_mir) { |
| 1121 | // If no MIR, we are done. |
| 1122 | if (first_list_mir == nullptr || last_list_mir == nullptr) { |
| 1123 | return; |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1124 | } |
| 1125 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1126 | // If insert_before is null, assume BB is empty. |
| 1127 | if (insert_before == nullptr) { |
| 1128 | first_mir_insn = first_list_mir; |
| 1129 | last_mir_insn = last_list_mir; |
| 1130 | last_list_mir->next = nullptr; |
| 1131 | } else { |
| 1132 | if (first_mir_insn == insert_before) { |
| 1133 | last_list_mir->next = first_mir_insn; |
| 1134 | first_mir_insn = first_list_mir; |
| 1135 | } else { |
| 1136 | // Find the preceding MIR. |
| 1137 | MIR* before_list = FindPreviousMIR(insert_before); |
| 1138 | DCHECK(before_list != nullptr); |
| 1139 | before_list->next = first_list_mir; |
| 1140 | last_list_mir->next = insert_before; |
| 1141 | } |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1142 | } |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1143 | |
| 1144 | // Set this BB to be the basic block of the MIRs. |
| 1145 | for (MIR* mir = first_list_mir; mir != last_list_mir->next; mir = mir->next) { |
| 1146 | mir->bb = id; |
| 1147 | } |
| 1148 | } |
| 1149 | |
| 1150 | bool BasicBlock::RemoveMIR(MIR* mir) { |
| 1151 | // Remove as a single element list. |
| 1152 | return RemoveMIRList(mir, mir); |
| 1153 | } |
| 1154 | |
| 1155 | bool BasicBlock::RemoveMIRList(MIR* first_list_mir, MIR* last_list_mir) { |
| 1156 | if (first_list_mir == nullptr) { |
| 1157 | return false; |
| 1158 | } |
| 1159 | |
| 1160 | // Try to find the MIR. |
| 1161 | MIR* before_list = nullptr; |
| 1162 | MIR* after_list = nullptr; |
| 1163 | |
| 1164 | // If we are removing from the beginning of the MIR list. |
| 1165 | if (first_mir_insn == first_list_mir) { |
| 1166 | before_list = nullptr; |
| 1167 | } else { |
| 1168 | before_list = FindPreviousMIR(first_list_mir); |
| 1169 | if (before_list == nullptr) { |
| 1170 | // We did not find the mir. |
| 1171 | return false; |
| 1172 | } |
| 1173 | } |
| 1174 | |
Jean Christophe Beyler | a4307ac | 2014-06-02 09:04:32 -0700 | [diff] [blame] | 1175 | // Remove the BB information and also find the after_list. |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1176 | for (MIR* mir = first_list_mir; mir != last_list_mir; mir = mir->next) { |
| 1177 | mir->bb = NullBasicBlockId; |
| 1178 | } |
| 1179 | |
| 1180 | after_list = last_list_mir->next; |
| 1181 | |
Jean Christophe Beyler | a4307ac | 2014-06-02 09:04:32 -0700 | [diff] [blame] | 1182 | // If there is nothing before the list, after_list is the first_mir. |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1183 | if (before_list == nullptr) { |
| 1184 | first_mir_insn = after_list; |
Jean Christophe Beyler | a4307ac | 2014-06-02 09:04:32 -0700 | [diff] [blame] | 1185 | } else { |
| 1186 | before_list->next = after_list; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1187 | } |
| 1188 | |
Jean Christophe Beyler | a4307ac | 2014-06-02 09:04:32 -0700 | [diff] [blame] | 1189 | // If there is nothing after the list, before_list is last_mir. |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1190 | if (after_list == nullptr) { |
| 1191 | last_mir_insn = before_list; |
| 1192 | } |
| 1193 | |
| 1194 | return true; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1195 | } |
| 1196 | |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 1197 | MIR* BasicBlock::GetNextUnconditionalMir(MIRGraph* mir_graph, MIR* current) { |
Razvan A Lupusoru | 3bc0174 | 2014-02-06 13:18:43 -0800 | [diff] [blame] | 1198 | MIR* next_mir = nullptr; |
| 1199 | |
| 1200 | if (current != nullptr) { |
| 1201 | next_mir = current->next; |
| 1202 | } |
| 1203 | |
| 1204 | if (next_mir == nullptr) { |
| 1205 | // Only look for next MIR that follows unconditionally. |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 1206 | if ((taken == NullBasicBlockId) && (fall_through != NullBasicBlockId)) { |
| 1207 | next_mir = mir_graph->GetBasicBlock(fall_through)->first_mir_insn; |
Razvan A Lupusoru | 3bc0174 | 2014-02-06 13:18:43 -0800 | [diff] [blame] | 1208 | } |
| 1209 | } |
| 1210 | |
| 1211 | return next_mir; |
| 1212 | } |
| 1213 | |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1214 | static void FillTypeSizeString(uint32_t type_size, std::string* decoded_mir) { |
| 1215 | DCHECK(decoded_mir != nullptr); |
| 1216 | OpSize type = static_cast<OpSize>(type_size >> 16); |
| 1217 | uint16_t vect_size = (type_size & 0xFFFF); |
| 1218 | |
| 1219 | // Now print the type and vector size. |
| 1220 | std::stringstream ss; |
| 1221 | ss << " (type:"; |
| 1222 | ss << type; |
| 1223 | ss << " vectsize:"; |
| 1224 | ss << vect_size; |
| 1225 | ss << ")"; |
| 1226 | |
| 1227 | decoded_mir->append(ss.str()); |
| 1228 | } |
| 1229 | |
| 1230 | void MIRGraph::DisassembleExtendedInstr(const MIR* mir, std::string* decoded_mir) { |
| 1231 | DCHECK(decoded_mir != nullptr); |
| 1232 | int opcode = mir->dalvikInsn.opcode; |
| 1233 | SSARepresentation* ssa_rep = mir->ssa_rep; |
| 1234 | int defs = (ssa_rep != nullptr) ? ssa_rep->num_defs : 0; |
| 1235 | int uses = (ssa_rep != nullptr) ? ssa_rep->num_uses : 0; |
| 1236 | |
| 1237 | decoded_mir->append(extended_mir_op_names_[opcode - kMirOpFirst]); |
| 1238 | |
| 1239 | switch (opcode) { |
| 1240 | case kMirOpPhi: { |
| 1241 | if (defs > 0 && uses > 0) { |
| 1242 | BasicBlockId* incoming = mir->meta.phi_incoming; |
| 1243 | decoded_mir->append(StringPrintf(" %s = (%s", |
| 1244 | GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), |
| 1245 | GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); |
| 1246 | decoded_mir->append(StringPrintf(":%d", incoming[0])); |
| 1247 | for (int i = 1; i < uses; i++) { |
| 1248 | decoded_mir->append(StringPrintf(", %s:%d", GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), incoming[i])); |
| 1249 | } |
| 1250 | decoded_mir->append(")"); |
| 1251 | } |
| 1252 | break; |
| 1253 | } |
| 1254 | case kMirOpCopy: |
| 1255 | if (ssa_rep != nullptr) { |
| 1256 | decoded_mir->append(" "); |
| 1257 | decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[0], false)); |
| 1258 | if (defs > 1) { |
| 1259 | decoded_mir->append(", "); |
| 1260 | decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[1], false)); |
| 1261 | } |
| 1262 | decoded_mir->append(" = "); |
| 1263 | decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[0], false)); |
| 1264 | if (uses > 1) { |
| 1265 | decoded_mir->append(", "); |
| 1266 | decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[1], false)); |
| 1267 | } |
| 1268 | } else { |
| 1269 | decoded_mir->append(StringPrintf(" v%d = v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1270 | } |
| 1271 | break; |
| 1272 | case kMirOpFusedCmplFloat: |
| 1273 | case kMirOpFusedCmpgFloat: |
| 1274 | case kMirOpFusedCmplDouble: |
| 1275 | case kMirOpFusedCmpgDouble: |
| 1276 | case kMirOpFusedCmpLong: |
| 1277 | if (ssa_rep != nullptr) { |
| 1278 | decoded_mir->append(" "); |
| 1279 | decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[0], false)); |
| 1280 | for (int i = 1; i < uses; i++) { |
| 1281 | decoded_mir->append(", "); |
| 1282 | decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[i], false)); |
| 1283 | } |
| 1284 | } else { |
| 1285 | decoded_mir->append(StringPrintf(" v%d, v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1286 | } |
| 1287 | break; |
| 1288 | case kMirOpMoveVector: |
| 1289 | decoded_mir->append(StringPrintf(" vect%d = vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1290 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1291 | break; |
| 1292 | case kMirOpPackedAddition: |
| 1293 | decoded_mir->append(StringPrintf(" vect%d = vect%d + vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1294 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1295 | break; |
| 1296 | case kMirOpPackedMultiply: |
| 1297 | decoded_mir->append(StringPrintf(" vect%d = vect%d * vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1298 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1299 | break; |
| 1300 | case kMirOpPackedSubtract: |
| 1301 | decoded_mir->append(StringPrintf(" vect%d = vect%d - vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1302 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1303 | break; |
| 1304 | case kMirOpPackedAnd: |
| 1305 | decoded_mir->append(StringPrintf(" vect%d = vect%d & vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1306 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1307 | break; |
| 1308 | case kMirOpPackedOr: |
| 1309 | decoded_mir->append(StringPrintf(" vect%d = vect%d \\| vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1310 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1311 | break; |
| 1312 | case kMirOpPackedXor: |
| 1313 | decoded_mir->append(StringPrintf(" vect%d = vect%d ^ vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1314 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1315 | break; |
| 1316 | case kMirOpPackedShiftLeft: |
| 1317 | decoded_mir->append(StringPrintf(" vect%d = vect%d \\<\\< %d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1318 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1319 | break; |
| 1320 | case kMirOpPackedUnsignedShiftRight: |
| 1321 | decoded_mir->append(StringPrintf(" vect%d = vect%d \\>\\>\\> %d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1322 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1323 | break; |
| 1324 | case kMirOpPackedSignedShiftRight: |
| 1325 | decoded_mir->append(StringPrintf(" vect%d = vect%d \\>\\> %d", mir->dalvikInsn.vA, mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1326 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1327 | break; |
| 1328 | case kMirOpConstVector: |
| 1329 | decoded_mir->append(StringPrintf(" vect%d = %x, %x, %x, %x", mir->dalvikInsn.vA, mir->dalvikInsn.arg[0], |
| 1330 | mir->dalvikInsn.arg[1], mir->dalvikInsn.arg[2], mir->dalvikInsn.arg[3])); |
| 1331 | break; |
| 1332 | case kMirOpPackedSet: |
| 1333 | if (ssa_rep != nullptr) { |
| 1334 | decoded_mir->append(StringPrintf(" vect%d = %s", mir->dalvikInsn.vA, |
| 1335 | GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); |
| 1336 | if (uses > 1) { |
| 1337 | decoded_mir->append(", "); |
| 1338 | decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[1], false)); |
| 1339 | } |
| 1340 | } else { |
| 1341 | decoded_mir->append(StringPrintf(" vect%d = v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1342 | } |
| 1343 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1344 | break; |
| 1345 | case kMirOpPackedAddReduce: |
| 1346 | if (ssa_rep != nullptr) { |
| 1347 | decoded_mir->append(" "); |
| 1348 | decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[0], false)); |
| 1349 | if (defs > 1) { |
| 1350 | decoded_mir->append(", "); |
| 1351 | decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[1], false)); |
| 1352 | } |
| 1353 | decoded_mir->append(StringPrintf(" = vect%d + %s", mir->dalvikInsn.vB, |
| 1354 | GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); |
| 1355 | if (uses > 1) { |
| 1356 | decoded_mir->append(", "); |
| 1357 | decoded_mir->append(GetSSANameWithConst(ssa_rep->uses[1], false)); |
| 1358 | } |
| 1359 | } else { |
| 1360 | decoded_mir->append(StringPrintf("v%d = vect%d + v%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB, mir->dalvikInsn.vA)); |
| 1361 | } |
| 1362 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1363 | break; |
| 1364 | case kMirOpPackedReduce: |
| 1365 | if (ssa_rep != nullptr) { |
| 1366 | decoded_mir->append(" "); |
| 1367 | decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[0], false)); |
| 1368 | if (defs > 1) { |
| 1369 | decoded_mir->append(", "); |
| 1370 | decoded_mir->append(GetSSANameWithConst(ssa_rep->defs[1], false)); |
| 1371 | } |
| 1372 | decoded_mir->append(StringPrintf(" = vect%d", mir->dalvikInsn.vB)); |
| 1373 | } else { |
| 1374 | decoded_mir->append(StringPrintf(" v%d = vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1375 | } |
| 1376 | FillTypeSizeString(mir->dalvikInsn.vC, decoded_mir); |
| 1377 | break; |
| 1378 | case kMirOpReserveVectorRegisters: |
| 1379 | case kMirOpReturnVectorRegisters: |
| 1380 | decoded_mir->append(StringPrintf(" vect%d - vect%d", mir->dalvikInsn.vA, mir->dalvikInsn.vB)); |
| 1381 | break; |
| 1382 | case kMirOpMemBarrier: { |
| 1383 | decoded_mir->append(" type:"); |
| 1384 | std::stringstream ss; |
| 1385 | ss << static_cast<MemBarrierKind>(mir->dalvikInsn.vA); |
| 1386 | decoded_mir->append(ss.str()); |
| 1387 | break; |
| 1388 | } |
| 1389 | default: |
| 1390 | break; |
| 1391 | } |
| 1392 | } |
| 1393 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1394 | char* MIRGraph::GetDalvikDisassembly(const MIR* mir) { |
Ian Rogers | 29a2648 | 2014-05-02 15:27:29 -0700 | [diff] [blame] | 1395 | MIR::DecodedInstruction insn = mir->dalvikInsn; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1396 | std::string str; |
| 1397 | int flags = 0; |
| 1398 | int opcode = insn.opcode; |
| 1399 | char* ret; |
| 1400 | bool nop = false; |
| 1401 | SSARepresentation* ssa_rep = mir->ssa_rep; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1402 | Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1403 | |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1404 | // Handle special cases that recover the original dalvik instruction. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1405 | if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { |
| 1406 | str.append(extended_mir_op_names_[opcode - kMirOpFirst]); |
| 1407 | str.append(": "); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1408 | // Recover the original Dex instruction. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1409 | insn = mir->meta.throw_insn->dalvikInsn; |
| 1410 | ssa_rep = mir->meta.throw_insn->ssa_rep; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1411 | opcode = insn.opcode; |
| 1412 | } else if (opcode == kMirOpNop) { |
| 1413 | str.append("["); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1414 | // Recover original opcode. |
| 1415 | insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); |
| 1416 | opcode = insn.opcode; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1417 | nop = true; |
| 1418 | } |
Serguei Katkov | 0f3e498 | 2014-08-21 16:43:54 +0700 | [diff] [blame] | 1419 | int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; |
| 1420 | int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1421 | |
Jean Christophe Beyler | 2ab40eb | 2014-06-02 09:03:14 -0700 | [diff] [blame] | 1422 | if (MIR::DecodedInstruction::IsPseudoMirOp(opcode)) { |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1423 | // Note that this does not check the MIR's opcode in all cases. In cases where it |
| 1424 | // recovered dalvik instruction, it uses opcode of that instead of the extended one. |
| 1425 | DisassembleExtendedInstr(mir, &str); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1426 | } else { |
| 1427 | dalvik_format = Instruction::FormatOf(insn.opcode); |
Jean Christophe Beyler | fb0ea2d | 2014-07-29 13:20:42 -0700 | [diff] [blame] | 1428 | flags = insn.FlagsOf(); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1429 | str.append(Instruction::Name(insn.opcode)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1430 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1431 | // For invokes-style formats, treat wide regs as a pair of singles. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1432 | bool show_singles = ((dalvik_format == Instruction::k35c) || |
| 1433 | (dalvik_format == Instruction::k3rc)); |
| 1434 | if (defs != 0) { |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1435 | str.append(" "); |
| 1436 | str.append(GetSSANameWithConst(ssa_rep->defs[0], false)); |
| 1437 | if (defs > 1) { |
| 1438 | str.append(", "); |
| 1439 | str.append(GetSSANameWithConst(ssa_rep->defs[1], false)); |
| 1440 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1441 | if (uses != 0) { |
| 1442 | str.append(", "); |
| 1443 | } |
| 1444 | } |
| 1445 | for (int i = 0; i < uses; i++) { |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1446 | str.append(" "); |
| 1447 | str.append(GetSSANameWithConst(ssa_rep->uses[i], show_singles)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1448 | if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { |
| 1449 | // For the listing, skip the high sreg. |
| 1450 | i++; |
| 1451 | } |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1452 | if (i != (uses - 1)) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1453 | str.append(","); |
| 1454 | } |
| 1455 | } |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1456 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1457 | switch (dalvik_format) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1458 | case Instruction::k11n: // Add one immediate from vB. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1459 | case Instruction::k21s: |
| 1460 | case Instruction::k31i: |
| 1461 | case Instruction::k21h: |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1462 | str.append(StringPrintf(", #0x%x", insn.vB)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1463 | break; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1464 | case Instruction::k51l: // Add one wide immediate. |
Ian Rogers | 23b03b5 | 2014-01-24 11:10:03 -0800 | [diff] [blame] | 1465 | str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1466 | break; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1467 | case Instruction::k21c: // One register, one string/type/method index. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1468 | case Instruction::k31c: |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1469 | str.append(StringPrintf(", index #0x%x", insn.vB)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1470 | break; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1471 | case Instruction::k22c: // Two registers, one string/type/method index. |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1472 | str.append(StringPrintf(", index #0x%x", insn.vC)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1473 | break; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1474 | case Instruction::k22s: // Add one immediate from vC. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1475 | case Instruction::k22b: |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1476 | str.append(StringPrintf(", #0x%x", insn.vC)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1477 | break; |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1478 | default: |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1479 | // Nothing left to print. |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1480 | break; |
Brian Carlstrom | 02c8cc6 | 2013-07-18 15:54:44 -0700 | [diff] [blame] | 1481 | } |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1482 | |
Serguei Katkov | 0f3e498 | 2014-08-21 16:43:54 +0700 | [diff] [blame] | 1483 | if ((flags & Instruction::kBranch) != 0) { |
| 1484 | // For branches, decode the instructions to print out the branch targets. |
| 1485 | int offset = 0; |
| 1486 | switch (dalvik_format) { |
| 1487 | case Instruction::k21t: |
| 1488 | offset = insn.vB; |
| 1489 | break; |
| 1490 | case Instruction::k22t: |
| 1491 | offset = insn.vC; |
| 1492 | break; |
| 1493 | case Instruction::k10t: |
| 1494 | case Instruction::k20t: |
| 1495 | case Instruction::k30t: |
| 1496 | offset = insn.vA; |
| 1497 | break; |
| 1498 | default: |
| 1499 | LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1500 | break; |
Serguei Katkov | 0f3e498 | 2014-08-21 16:43:54 +0700 | [diff] [blame] | 1501 | } |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1502 | str.append(StringPrintf(", 0x%x (%c%x)", mir->offset + offset, |
Serguei Katkov | 0f3e498 | 2014-08-21 16:43:54 +0700 | [diff] [blame] | 1503 | offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); |
| 1504 | } |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1505 | |
| 1506 | if (nop) { |
| 1507 | str.append("]--optimized away"); |
| 1508 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1509 | } |
| 1510 | int length = str.length() + 1; |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1511 | ret = static_cast<char*>(arena_->Alloc(length, kArenaAllocDFInfo)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1512 | strncpy(ret, str.c_str(), length); |
| 1513 | return ret; |
| 1514 | } |
| 1515 | |
| 1516 | /* Turn method name into a legal Linux file name */ |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1517 | void MIRGraph::ReplaceSpecialChars(std::string& str) { |
Brian Carlstrom | 9b7085a | 2013-07-18 15:15:21 -0700 | [diff] [blame] | 1518 | static const struct { const char before; const char after; } match[] = { |
| 1519 | {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, |
| 1520 | {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} |
| 1521 | }; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1522 | for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { |
| 1523 | std::replace(str.begin(), str.end(), match[i].before, match[i].after); |
| 1524 | } |
| 1525 | } |
| 1526 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1527 | std::string MIRGraph::GetSSAName(int ssa_reg) { |
Ian Rogers | 39ebcb8 | 2013-05-30 16:57:23 -0700 | [diff] [blame] | 1528 | // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to |
| 1529 | // the arena. We should be smarter and just place straight into the arena, or compute the |
| 1530 | // value more lazily. |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1531 | int vreg = SRegToVReg(ssa_reg); |
| 1532 | if (vreg >= static_cast<int>(GetFirstTempVR())) { |
| 1533 | return StringPrintf("t%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); |
| 1534 | } else { |
| 1535 | return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); |
| 1536 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1537 | } |
| 1538 | |
| 1539 | // Similar to GetSSAName, but if ssa name represents an immediate show that as well. |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1540 | std::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1541 | if (reg_location_ == NULL) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1542 | // Pre-SSA - just use the standard name. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1543 | return GetSSAName(ssa_reg); |
| 1544 | } |
| 1545 | if (IsConst(reg_location_[ssa_reg])) { |
| 1546 | if (!singles_only && reg_location_[ssa_reg].wide) { |
Ian Rogers | 23b03b5 | 2014-01-24 11:10:03 -0800 | [diff] [blame] | 1547 | return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1548 | ConstantValueWide(reg_location_[ssa_reg])); |
| 1549 | } else { |
Brian Carlstrom | b1eba21 | 2013-07-17 18:07:19 -0700 | [diff] [blame] | 1550 | return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1551 | ConstantValue(reg_location_[ssa_reg])); |
| 1552 | } |
| 1553 | } else { |
Razvan A Lupusoru | 1500e6f | 2014-08-22 15:39:50 -0700 | [diff] [blame^] | 1554 | int vreg = SRegToVReg(ssa_reg); |
| 1555 | if (vreg >= static_cast<int>(GetFirstTempVR())) { |
| 1556 | return StringPrintf("t%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); |
| 1557 | } else { |
| 1558 | return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); |
| 1559 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1560 | } |
| 1561 | } |
| 1562 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1563 | void MIRGraph::GetBlockName(BasicBlock* bb, char* name) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1564 | switch (bb->block_type) { |
| 1565 | case kEntryBlock: |
| 1566 | snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); |
| 1567 | break; |
| 1568 | case kExitBlock: |
| 1569 | snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); |
| 1570 | break; |
| 1571 | case kDalvikByteCode: |
| 1572 | snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); |
| 1573 | break; |
| 1574 | case kExceptionHandling: |
| 1575 | snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, |
| 1576 | bb->id); |
| 1577 | break; |
| 1578 | default: |
| 1579 | snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); |
| 1580 | break; |
| 1581 | } |
| 1582 | } |
| 1583 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1584 | const char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1585 | // TODO: for inlining support, use current code unit. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1586 | const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); |
| 1587 | return cu_->dex_file->GetShorty(method_id.proto_idx_); |
| 1588 | } |
| 1589 | |
| 1590 | /* Debug Utility - dump a compilation unit */ |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1591 | void MIRGraph::DumpMIRGraph() { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1592 | BasicBlock* bb; |
| 1593 | const char* block_type_names[] = { |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 1594 | "Null Block", |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1595 | "Entry Block", |
| 1596 | "Code Block", |
| 1597 | "Exit Block", |
| 1598 | "Exception Handling", |
| 1599 | "Catch Block" |
| 1600 | }; |
| 1601 | |
| 1602 | LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); |
Razvan A Lupusoru | 8d0d03e | 2014-06-06 17:04:52 -0700 | [diff] [blame] | 1603 | LOG(INFO) << GetInsns(0) << " insns"; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1604 | LOG(INFO) << GetNumBlocks() << " blocks in total"; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1605 | GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1606 | |
| 1607 | while (true) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1608 | bb = iterator.Next(); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1609 | if (bb == NULL) break; |
| 1610 | LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", |
| 1611 | bb->id, |
| 1612 | block_type_names[bb->block_type], |
| 1613 | bb->start_offset, |
| 1614 | bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, |
| 1615 | bb->last_mir_insn ? "" : " empty"); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1616 | if (bb->taken != NullBasicBlockId) { |
| 1617 | LOG(INFO) << " Taken branch: block " << bb->taken |
| 1618 | << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1619 | } |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1620 | if (bb->fall_through != NullBasicBlockId) { |
| 1621 | LOG(INFO) << " Fallthrough : block " << bb->fall_through |
| 1622 | << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1623 | } |
| 1624 | } |
| 1625 | } |
| 1626 | |
| 1627 | /* |
| 1628 | * Build an array of location records for the incoming arguments. |
| 1629 | * Note: one location record per word of arguments, with dummy |
| 1630 | * high-word loc for wide arguments. Also pull up any following |
| 1631 | * MOVE_RESULT and incorporate it into the invoke. |
| 1632 | */ |
| 1633 | CallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1634 | bool is_range) { |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 1635 | CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1636 | kArenaAllocMisc)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1637 | MIR* move_result_mir = FindMoveResult(bb, mir); |
| 1638 | if (move_result_mir == NULL) { |
| 1639 | info->result.location = kLocInvalid; |
| 1640 | } else { |
| 1641 | info->result = GetRawDest(move_result_mir); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1642 | move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); |
| 1643 | } |
| 1644 | info->num_arg_words = mir->ssa_rep->num_uses; |
| 1645 | info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1646 | (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, kArenaAllocMisc)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1647 | for (int i = 0; i < info->num_arg_words; i++) { |
| 1648 | info->args[i] = GetRawSrc(mir, i); |
| 1649 | } |
| 1650 | info->opt_flags = mir->optimization_flags; |
| 1651 | info->type = type; |
| 1652 | info->is_range = is_range; |
| 1653 | info->index = mir->dalvikInsn.vB; |
| 1654 | info->offset = mir->offset; |
Vladimir Marko | f096aad | 2014-01-23 15:51:58 +0000 | [diff] [blame] | 1655 | info->mir = mir; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1656 | return info; |
| 1657 | } |
| 1658 | |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 1659 | // Allocate a new MIR. |
| 1660 | MIR* MIRGraph::NewMIR() { |
| 1661 | MIR* mir = new (arena_) MIR(); |
| 1662 | return mir; |
| 1663 | } |
| 1664 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1665 | // Allocate a new basic block. |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1666 | BasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1667 | BasicBlock* bb = new (arena_) BasicBlock(); |
| 1668 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1669 | bb->block_type = block_type; |
| 1670 | bb->id = block_id; |
| 1671 | // TUNING: better estimate of the exit block predecessors? |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1672 | bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, |
Brian Carlstrom | df62950 | 2013-07-17 22:39:56 -0700 | [diff] [blame] | 1673 | (block_type == kExitBlock) ? 2048 : 2, |
| 1674 | kGrowableArrayPredecessors); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1675 | bb->successor_block_list_type = kNotUsed; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1676 | block_id_map_.Put(block_id, block_id); |
| 1677 | return bb; |
| 1678 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1679 | |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1680 | void MIRGraph::InitializeConstantPropagation() { |
| 1681 | is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1682 | constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), kArenaAllocDFInfo)); |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1683 | } |
| 1684 | |
| 1685 | void MIRGraph::InitializeMethodUses() { |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1686 | // The gate starts by initializing the use counts. |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1687 | int num_ssa_regs = GetNumSSARegs(); |
| 1688 | use_counts_.Resize(num_ssa_regs + 32); |
| 1689 | raw_use_counts_.Resize(num_ssa_regs + 32); |
Razvan A Lupusoru | 8d0d03e | 2014-06-06 17:04:52 -0700 | [diff] [blame] | 1690 | // Resize does not actually reset the number of used, so reset before initialization. |
| 1691 | use_counts_.Reset(); |
| 1692 | raw_use_counts_.Reset(); |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 1693 | // Initialize list. |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1694 | for (int i = 0; i < num_ssa_regs; i++) { |
| 1695 | use_counts_.Insert(0); |
| 1696 | raw_use_counts_.Insert(0); |
| 1697 | } |
| 1698 | } |
| 1699 | |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 1700 | void MIRGraph::SSATransformationStart() { |
| 1701 | DCHECK(temp_scoped_alloc_.get() == nullptr); |
| 1702 | temp_scoped_alloc_.reset(ScopedArenaAllocator::Create(&cu_->arena_stack)); |
Razvan A Lupusoru | 8d0d03e | 2014-06-06 17:04:52 -0700 | [diff] [blame] | 1703 | temp_bit_vector_size_ = GetNumOfCodeAndTempVRs(); |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 1704 | temp_bit_vector_ = new (temp_scoped_alloc_.get()) ArenaBitVector( |
| 1705 | temp_scoped_alloc_.get(), temp_bit_vector_size_, false, kBitMapRegisterV); |
| 1706 | |
Jean Christophe Beyler | 4896d7b | 2014-05-01 15:36:22 -0700 | [diff] [blame] | 1707 | // Update the maximum number of reachable blocks. |
| 1708 | max_num_reachable_blocks_ = num_reachable_blocks_; |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1709 | } |
| 1710 | |
Vladimir Marko | a5b8fde | 2014-05-23 15:16:44 +0100 | [diff] [blame] | 1711 | void MIRGraph::SSATransformationEnd() { |
| 1712 | // Verify the dataflow information after the pass. |
| 1713 | if (cu_->enable_debug & (1 << kDebugVerifyDataflow)) { |
| 1714 | VerifyDataflow(); |
| 1715 | } |
| 1716 | |
| 1717 | temp_bit_vector_size_ = 0u; |
| 1718 | temp_bit_vector_ = nullptr; |
| 1719 | DCHECK(temp_scoped_alloc_.get() != nullptr); |
| 1720 | temp_scoped_alloc_.reset(); |
| 1721 | } |
| 1722 | |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1723 | static BasicBlock* SelectTopologicalSortOrderFallBack( |
| 1724 | MIRGraph* mir_graph, const ArenaBitVector* current_loop, |
| 1725 | const ScopedArenaVector<size_t>* visited_cnt_values, ScopedArenaAllocator* allocator, |
| 1726 | ScopedArenaVector<BasicBlockId>* tmp_stack) { |
| 1727 | // No true loop head has been found but there may be true loop heads after the mess we need |
| 1728 | // to resolve. To avoid taking one of those, pick the candidate with the highest number of |
| 1729 | // reachable unvisited nodes. That candidate will surely be a part of a loop. |
| 1730 | BasicBlock* fall_back = nullptr; |
| 1731 | size_t fall_back_num_reachable = 0u; |
| 1732 | // Reuse the same bit vector for each candidate to mark reachable unvisited blocks. |
| 1733 | ArenaBitVector candidate_reachable(allocator, mir_graph->GetNumBlocks(), false, kBitMapMisc); |
| 1734 | AllNodesIterator iter(mir_graph); |
| 1735 | for (BasicBlock* candidate = iter.Next(); candidate != nullptr; candidate = iter.Next()) { |
| 1736 | if (candidate->hidden || // Hidden, or |
| 1737 | candidate->visited || // already processed, or |
| 1738 | (*visited_cnt_values)[candidate->id] == 0u || // no processed predecessors, or |
| 1739 | (current_loop != nullptr && // outside current loop. |
| 1740 | !current_loop->IsBitSet(candidate->id))) { |
| 1741 | continue; |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1742 | } |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1743 | DCHECK(tmp_stack->empty()); |
| 1744 | tmp_stack->push_back(candidate->id); |
| 1745 | candidate_reachable.ClearAllBits(); |
| 1746 | size_t num_reachable = 0u; |
| 1747 | while (!tmp_stack->empty()) { |
| 1748 | BasicBlockId current_id = tmp_stack->back(); |
| 1749 | tmp_stack->pop_back(); |
| 1750 | BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id); |
| 1751 | DCHECK(current_bb != nullptr); |
| 1752 | ChildBlockIterator child_iter(current_bb, mir_graph); |
| 1753 | BasicBlock* child_bb = child_iter.Next(); |
| 1754 | for ( ; child_bb != nullptr; child_bb = child_iter.Next()) { |
| 1755 | DCHECK(!child_bb->hidden); |
| 1756 | if (child_bb->visited || // Already processed, or |
| 1757 | (current_loop != nullptr && // outside current loop. |
| 1758 | !current_loop->IsBitSet(child_bb->id))) { |
| 1759 | continue; |
| 1760 | } |
| 1761 | if (!candidate_reachable.IsBitSet(child_bb->id)) { |
| 1762 | candidate_reachable.SetBit(child_bb->id); |
| 1763 | tmp_stack->push_back(child_bb->id); |
| 1764 | num_reachable += 1u; |
| 1765 | } |
| 1766 | } |
| 1767 | } |
| 1768 | if (fall_back_num_reachable < num_reachable) { |
| 1769 | fall_back_num_reachable = num_reachable; |
| 1770 | fall_back = candidate; |
| 1771 | } |
| 1772 | } |
| 1773 | return fall_back; |
| 1774 | } |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1775 | |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1776 | // Compute from which unvisited blocks is bb_id reachable through unvisited blocks. |
| 1777 | static void ComputeUnvisitedReachableFrom(MIRGraph* mir_graph, BasicBlockId bb_id, |
| 1778 | ArenaBitVector* reachable, |
| 1779 | ScopedArenaVector<BasicBlockId>* tmp_stack) { |
| 1780 | // NOTE: Loop heads indicated by the "visited" flag. |
| 1781 | DCHECK(tmp_stack->empty()); |
| 1782 | reachable->ClearAllBits(); |
| 1783 | tmp_stack->push_back(bb_id); |
| 1784 | while (!tmp_stack->empty()) { |
| 1785 | BasicBlockId current_id = tmp_stack->back(); |
| 1786 | tmp_stack->pop_back(); |
| 1787 | BasicBlock* current_bb = mir_graph->GetBasicBlock(current_id); |
| 1788 | DCHECK(current_bb != nullptr); |
| 1789 | GrowableArray<BasicBlockId>::Iterator iter(current_bb->predecessors); |
| 1790 | BasicBlock* pred_bb = mir_graph->GetBasicBlock(iter.Next()); |
| 1791 | for ( ; pred_bb != nullptr; pred_bb = mir_graph->GetBasicBlock(iter.Next())) { |
| 1792 | if (!pred_bb->visited && !reachable->IsBitSet(pred_bb->id)) { |
| 1793 | reachable->SetBit(pred_bb->id); |
| 1794 | tmp_stack->push_back(pred_bb->id); |
| 1795 | } |
| 1796 | } |
| 1797 | } |
| 1798 | } |
| 1799 | |
| 1800 | void MIRGraph::ComputeTopologicalSortOrder() { |
| 1801 | ScopedArenaAllocator allocator(&cu_->arena_stack); |
| 1802 | unsigned int num_blocks = GetNumBlocks(); |
| 1803 | |
| 1804 | ScopedArenaQueue<BasicBlock*> q(allocator.Adapter()); |
| 1805 | ScopedArenaVector<size_t> visited_cnt_values(num_blocks, 0u, allocator.Adapter()); |
| 1806 | ScopedArenaVector<BasicBlockId> loop_head_stack(allocator.Adapter()); |
| 1807 | size_t max_nested_loops = 0u; |
| 1808 | ArenaBitVector loop_exit_blocks(&allocator, num_blocks, false, kBitMapMisc); |
| 1809 | loop_exit_blocks.ClearAllBits(); |
| 1810 | |
| 1811 | // Count the number of blocks to process and add the entry block(s). |
| 1812 | GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); |
| 1813 | unsigned int num_blocks_to_process = 0u; |
| 1814 | for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1815 | if (bb->hidden == true) { |
| 1816 | continue; |
| 1817 | } |
| 1818 | |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1819 | num_blocks_to_process += 1u; |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1820 | |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1821 | if (bb->predecessors->Size() == 0u) { |
| 1822 | // Add entry block to the queue. |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1823 | q.push(bb); |
| 1824 | } |
| 1825 | } |
| 1826 | |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1827 | // Create the topological order if need be. |
| 1828 | if (topological_order_ == nullptr) { |
| 1829 | topological_order_ = new (arena_) GrowableArray<BasicBlockId>(arena_, num_blocks); |
| 1830 | topological_order_loop_ends_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks); |
| 1831 | topological_order_indexes_ = new (arena_) GrowableArray<uint16_t>(arena_, num_blocks); |
| 1832 | } |
| 1833 | topological_order_->Reset(); |
| 1834 | topological_order_loop_ends_->Reset(); |
| 1835 | topological_order_indexes_->Reset(); |
| 1836 | topological_order_loop_ends_->Resize(num_blocks); |
| 1837 | topological_order_indexes_->Resize(num_blocks); |
| 1838 | for (BasicBlockId i = 0; i != num_blocks; ++i) { |
| 1839 | topological_order_loop_ends_->Insert(0u); |
| 1840 | topological_order_indexes_->Insert(static_cast<uint16_t>(-1)); |
| 1841 | } |
| 1842 | |
| 1843 | // Mark all blocks as unvisited. |
| 1844 | ClearAllVisitedFlags(); |
| 1845 | |
| 1846 | // For loop heads, keep track from which blocks they are reachable not going through other |
| 1847 | // loop heads. Other loop heads are excluded to detect the heads of nested loops. The children |
| 1848 | // in this set go into the loop body, the other children are jumping over the loop. |
| 1849 | ScopedArenaVector<ArenaBitVector*> loop_head_reachable_from(allocator.Adapter()); |
| 1850 | loop_head_reachable_from.resize(num_blocks, nullptr); |
| 1851 | // Reuse the same temp stack whenever calculating a loop_head_reachable_from[loop_head_id]. |
| 1852 | ScopedArenaVector<BasicBlockId> tmp_stack(allocator.Adapter()); |
| 1853 | |
| 1854 | while (num_blocks_to_process != 0u) { |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1855 | BasicBlock* bb = nullptr; |
| 1856 | if (!q.empty()) { |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1857 | num_blocks_to_process -= 1u; |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1858 | // Get top. |
| 1859 | bb = q.front(); |
| 1860 | q.pop(); |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1861 | if (bb->visited) { |
| 1862 | // Loop head: it was already processed, mark end and copy exit blocks to the queue. |
| 1863 | DCHECK(q.empty()) << PrettyMethod(cu_->method_idx, *cu_->dex_file); |
| 1864 | uint16_t idx = static_cast<uint16_t>(topological_order_->Size()); |
| 1865 | topological_order_loop_ends_->Put(topological_order_indexes_->Get(bb->id), idx); |
| 1866 | DCHECK_EQ(loop_head_stack.back(), bb->id); |
| 1867 | loop_head_stack.pop_back(); |
| 1868 | ArenaBitVector* reachable = |
| 1869 | loop_head_stack.empty() ? nullptr : loop_head_reachable_from[loop_head_stack.back()]; |
| 1870 | for (BasicBlockId candidate_id : loop_exit_blocks.Indexes()) { |
| 1871 | if (reachable == nullptr || reachable->IsBitSet(candidate_id)) { |
| 1872 | q.push(GetBasicBlock(candidate_id)); |
| 1873 | // NOTE: The BitVectorSet::IndexIterator will not check the pointed-to bit again, |
| 1874 | // so clearing the bit has no effect on the iterator. |
| 1875 | loop_exit_blocks.ClearBit(candidate_id); |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1876 | } |
| 1877 | } |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1878 | continue; |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1879 | } |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1880 | } else { |
| 1881 | // Find the new loop head. |
| 1882 | AllNodesIterator iter(this); |
| 1883 | while (true) { |
| 1884 | BasicBlock* candidate = iter.Next(); |
| 1885 | if (candidate == nullptr) { |
| 1886 | // We did not find a true loop head, fall back to a reachable block in any loop. |
| 1887 | ArenaBitVector* current_loop = |
| 1888 | loop_head_stack.empty() ? nullptr : loop_head_reachable_from[loop_head_stack.back()]; |
| 1889 | bb = SelectTopologicalSortOrderFallBack(this, current_loop, &visited_cnt_values, |
| 1890 | &allocator, &tmp_stack); |
| 1891 | DCHECK(bb != nullptr) << PrettyMethod(cu_->method_idx, *cu_->dex_file); |
| 1892 | if (kIsDebugBuild && cu_->dex_file != nullptr) { |
| 1893 | LOG(INFO) << "Topological sort order: Using fall-back in " |
| 1894 | << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " BB #" << bb->id |
| 1895 | << " @0x" << std::hex << bb->start_offset |
| 1896 | << ", num_blocks = " << std::dec << num_blocks; |
| 1897 | } |
| 1898 | break; |
| 1899 | } |
| 1900 | if (candidate->hidden || // Hidden, or |
| 1901 | candidate->visited || // already processed, or |
| 1902 | visited_cnt_values[candidate->id] == 0u || // no processed predecessors, or |
| 1903 | (!loop_head_stack.empty() && // outside current loop. |
| 1904 | !loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(candidate->id))) { |
| 1905 | continue; |
| 1906 | } |
| 1907 | |
| 1908 | GrowableArray<BasicBlockId>::Iterator pred_iter(candidate->predecessors); |
| 1909 | BasicBlock* pred_bb = GetBasicBlock(pred_iter.Next()); |
| 1910 | for ( ; pred_bb != nullptr; pred_bb = GetBasicBlock(pred_iter.Next())) { |
| 1911 | if (pred_bb != candidate && !pred_bb->visited && |
| 1912 | !pred_bb->dominators->IsBitSet(candidate->id)) { |
| 1913 | break; // Keep non-null pred_bb to indicate failure. |
| 1914 | } |
| 1915 | } |
| 1916 | if (pred_bb == nullptr) { |
| 1917 | bb = candidate; |
| 1918 | break; |
| 1919 | } |
| 1920 | } |
| 1921 | // Compute blocks from which the loop head is reachable and process those blocks first. |
| 1922 | ArenaBitVector* reachable = |
| 1923 | new (&allocator) ArenaBitVector(&allocator, num_blocks, false, kBitMapMisc); |
| 1924 | loop_head_reachable_from[bb->id] = reachable; |
| 1925 | ComputeUnvisitedReachableFrom(this, bb->id, reachable, &tmp_stack); |
| 1926 | // Now mark as loop head. (Even if it's only a fall back when we don't find a true loop.) |
| 1927 | loop_head_stack.push_back(bb->id); |
| 1928 | max_nested_loops = std::max(max_nested_loops, loop_head_stack.size()); |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1929 | } |
| 1930 | |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1931 | DCHECK_EQ(bb->hidden, false); |
| 1932 | DCHECK_EQ(bb->visited, false); |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1933 | bb->visited = true; |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1934 | |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1935 | // Now add the basic block. |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1936 | uint16_t idx = static_cast<uint16_t>(topological_order_->Size()); |
| 1937 | topological_order_indexes_->Put(bb->id, idx); |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1938 | topological_order_->Insert(bb->id); |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1939 | |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1940 | // Update visited_cnt_values for children. |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1941 | ChildBlockIterator succIter(bb, this); |
| 1942 | BasicBlock* successor = succIter.Next(); |
| 1943 | for ( ; successor != nullptr; successor = succIter.Next()) { |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1944 | if (successor->hidden) { |
Vladimir Marko | 622bdbe | 2014-06-19 14:59:05 +0100 | [diff] [blame] | 1945 | continue; |
| 1946 | } |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1947 | |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1948 | // One more predecessor was visited. |
| 1949 | visited_cnt_values[successor->id] += 1u; |
| 1950 | if (visited_cnt_values[successor->id] == successor->predecessors->Size()) { |
| 1951 | if (loop_head_stack.empty() || |
| 1952 | loop_head_reachable_from[loop_head_stack.back()]->IsBitSet(successor->id)) { |
| 1953 | q.push(successor); |
| 1954 | } else { |
| 1955 | DCHECK(!loop_exit_blocks.IsBitSet(successor->id)); |
| 1956 | loop_exit_blocks.SetBit(successor->id); |
| 1957 | } |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1958 | } |
| 1959 | } |
| 1960 | } |
Vladimir Marko | 55fff04 | 2014-07-10 12:42:52 +0100 | [diff] [blame] | 1961 | |
| 1962 | // Prepare the loop head stack for iteration. |
| 1963 | topological_order_loop_head_stack_ = |
| 1964 | new (arena_) GrowableArray<std::pair<uint16_t, bool>>(arena_, max_nested_loops); |
Jean Christophe Beyler | 44e5bde | 2014-04-29 14:40:41 -0700 | [diff] [blame] | 1965 | } |
| 1966 | |
| 1967 | bool BasicBlock::IsExceptionBlock() const { |
| 1968 | if (block_type == kExceptionHandling) { |
| 1969 | return true; |
| 1970 | } |
| 1971 | return false; |
| 1972 | } |
| 1973 | |
Wei Jin | 04f4d8a | 2014-05-29 18:04:29 -0700 | [diff] [blame] | 1974 | bool MIRGraph::HasSuspendTestBetween(BasicBlock* source, BasicBlockId target_id) { |
| 1975 | BasicBlock* target = GetBasicBlock(target_id); |
| 1976 | |
| 1977 | if (source == nullptr || target == nullptr) |
| 1978 | return false; |
| 1979 | |
| 1980 | int idx; |
| 1981 | for (idx = gen_suspend_test_list_.Size() - 1; idx >= 0; idx--) { |
| 1982 | BasicBlock* bb = gen_suspend_test_list_.Get(idx); |
| 1983 | if (bb == source) |
| 1984 | return true; // The block has been inserted by a suspend check before. |
| 1985 | if (source->dominators->IsBitSet(bb->id) && bb->dominators->IsBitSet(target_id)) |
| 1986 | return true; |
| 1987 | } |
| 1988 | |
| 1989 | return false; |
| 1990 | } |
| 1991 | |
Jean Christophe Beyler | f8c762b | 2014-05-02 12:54:37 -0700 | [diff] [blame] | 1992 | ChildBlockIterator::ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph) |
| 1993 | : basic_block_(bb), mir_graph_(mir_graph), visited_fallthrough_(false), |
| 1994 | visited_taken_(false), have_successors_(false) { |
| 1995 | // Check if we actually do have successors. |
| 1996 | if (basic_block_ != 0 && basic_block_->successor_block_list_type != kNotUsed) { |
| 1997 | have_successors_ = true; |
| 1998 | successor_iter_.Reset(basic_block_->successor_blocks); |
| 1999 | } |
| 2000 | } |
| 2001 | |
| 2002 | BasicBlock* ChildBlockIterator::Next() { |
| 2003 | // We check if we have a basic block. If we don't we cannot get next child. |
| 2004 | if (basic_block_ == nullptr) { |
| 2005 | return nullptr; |
| 2006 | } |
| 2007 | |
| 2008 | // If we haven't visited fallthrough, return that. |
| 2009 | if (visited_fallthrough_ == false) { |
| 2010 | visited_fallthrough_ = true; |
| 2011 | |
| 2012 | BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->fall_through); |
| 2013 | if (result != nullptr) { |
| 2014 | return result; |
| 2015 | } |
| 2016 | } |
| 2017 | |
| 2018 | // If we haven't visited taken, return that. |
| 2019 | if (visited_taken_ == false) { |
| 2020 | visited_taken_ = true; |
| 2021 | |
| 2022 | BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->taken); |
| 2023 | if (result != nullptr) { |
| 2024 | return result; |
| 2025 | } |
| 2026 | } |
| 2027 | |
| 2028 | // We visited both taken and fallthrough. Now check if we have successors we need to visit. |
| 2029 | if (have_successors_ == true) { |
| 2030 | // Get information about next successor block. |
Niranjan Kumar | 989367a | 2014-06-12 12:15:48 -0700 | [diff] [blame] | 2031 | for (SuccessorBlockInfo* successor_block_info = successor_iter_.Next(); |
| 2032 | successor_block_info != nullptr; |
| 2033 | successor_block_info = successor_iter_.Next()) { |
| 2034 | // If block was replaced by zero block, take next one. |
| 2035 | if (successor_block_info->block != NullBasicBlockId) { |
| 2036 | return mir_graph_->GetBasicBlock(successor_block_info->block); |
| 2037 | } |
Jean Christophe Beyler | f8c762b | 2014-05-02 12:54:37 -0700 | [diff] [blame] | 2038 | } |
| 2039 | } |
| 2040 | |
| 2041 | // We do not have anything. |
| 2042 | return nullptr; |
| 2043 | } |
| 2044 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2045 | BasicBlock* BasicBlock::Copy(CompilationUnit* c_unit) { |
| 2046 | MIRGraph* mir_graph = c_unit->mir_graph.get(); |
| 2047 | return Copy(mir_graph); |
| 2048 | } |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2049 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2050 | BasicBlock* BasicBlock::Copy(MIRGraph* mir_graph) { |
| 2051 | BasicBlock* result_bb = mir_graph->CreateNewBB(block_type); |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2052 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2053 | // We don't do a memcpy style copy here because it would lead to a lot of things |
| 2054 | // to clean up. Let us do it by hand instead. |
| 2055 | // Copy in taken and fallthrough. |
| 2056 | result_bb->fall_through = fall_through; |
| 2057 | result_bb->taken = taken; |
| 2058 | |
| 2059 | // Copy successor links if needed. |
| 2060 | ArenaAllocator* arena = mir_graph->GetArena(); |
| 2061 | |
| 2062 | result_bb->successor_block_list_type = successor_block_list_type; |
| 2063 | if (result_bb->successor_block_list_type != kNotUsed) { |
| 2064 | size_t size = successor_blocks->Size(); |
| 2065 | result_bb->successor_blocks = new (arena) GrowableArray<SuccessorBlockInfo*>(arena, size, kGrowableArraySuccessorBlocks); |
| 2066 | GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks); |
| 2067 | while (true) { |
| 2068 | SuccessorBlockInfo* sbi_old = iterator.Next(); |
| 2069 | if (sbi_old == nullptr) { |
| 2070 | break; |
| 2071 | } |
| 2072 | SuccessorBlockInfo* sbi_new = static_cast<SuccessorBlockInfo*>(arena->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); |
| 2073 | memcpy(sbi_new, sbi_old, sizeof(SuccessorBlockInfo)); |
| 2074 | result_bb->successor_blocks->Insert(sbi_new); |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2075 | } |
| 2076 | } |
| 2077 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2078 | // Copy offset, method. |
| 2079 | result_bb->start_offset = start_offset; |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2080 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2081 | // Now copy instructions. |
| 2082 | for (MIR* mir = first_mir_insn; mir != 0; mir = mir->next) { |
| 2083 | // Get a copy first. |
| 2084 | MIR* copy = mir->Copy(mir_graph); |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2085 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2086 | // Append it. |
| 2087 | result_bb->AppendMIR(copy); |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2088 | } |
| 2089 | |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2090 | return result_bb; |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2091 | } |
| 2092 | |
| 2093 | MIR* MIR::Copy(MIRGraph* mir_graph) { |
| 2094 | MIR* res = mir_graph->NewMIR(); |
| 2095 | *res = *this; |
| 2096 | |
| 2097 | // Remove links |
| 2098 | res->next = nullptr; |
| 2099 | res->bb = NullBasicBlockId; |
| 2100 | res->ssa_rep = nullptr; |
| 2101 | |
| 2102 | return res; |
| 2103 | } |
| 2104 | |
| 2105 | MIR* MIR::Copy(CompilationUnit* c_unit) { |
| 2106 | return Copy(c_unit->mir_graph.get()); |
| 2107 | } |
| 2108 | |
| 2109 | uint32_t SSARepresentation::GetStartUseIndex(Instruction::Code opcode) { |
| 2110 | // Default result. |
| 2111 | int res = 0; |
| 2112 | |
| 2113 | // We are basically setting the iputs to their igets counterparts. |
| 2114 | switch (opcode) { |
| 2115 | case Instruction::IPUT: |
| 2116 | case Instruction::IPUT_OBJECT: |
| 2117 | case Instruction::IPUT_BOOLEAN: |
| 2118 | case Instruction::IPUT_BYTE: |
| 2119 | case Instruction::IPUT_CHAR: |
| 2120 | case Instruction::IPUT_SHORT: |
| 2121 | case Instruction::IPUT_QUICK: |
| 2122 | case Instruction::IPUT_OBJECT_QUICK: |
Fred Shih | 37f05ef | 2014-07-16 18:38:08 -0700 | [diff] [blame] | 2123 | case Instruction::IPUT_BOOLEAN_QUICK: |
| 2124 | case Instruction::IPUT_BYTE_QUICK: |
| 2125 | case Instruction::IPUT_CHAR_QUICK: |
| 2126 | case Instruction::IPUT_SHORT_QUICK: |
Jean Christophe Beyler | 3aa5773 | 2014-04-17 12:47:24 -0700 | [diff] [blame] | 2127 | case Instruction::APUT: |
| 2128 | case Instruction::APUT_OBJECT: |
| 2129 | case Instruction::APUT_BOOLEAN: |
| 2130 | case Instruction::APUT_BYTE: |
| 2131 | case Instruction::APUT_CHAR: |
| 2132 | case Instruction::APUT_SHORT: |
| 2133 | case Instruction::SPUT: |
| 2134 | case Instruction::SPUT_OBJECT: |
| 2135 | case Instruction::SPUT_BOOLEAN: |
| 2136 | case Instruction::SPUT_BYTE: |
| 2137 | case Instruction::SPUT_CHAR: |
| 2138 | case Instruction::SPUT_SHORT: |
| 2139 | // Skip the VR containing what to store. |
| 2140 | res = 1; |
| 2141 | break; |
| 2142 | case Instruction::IPUT_WIDE: |
| 2143 | case Instruction::IPUT_WIDE_QUICK: |
| 2144 | case Instruction::APUT_WIDE: |
| 2145 | case Instruction::SPUT_WIDE: |
| 2146 | // Skip the two VRs containing what to store. |
| 2147 | res = 2; |
| 2148 | break; |
| 2149 | default: |
| 2150 | // Do nothing in the general case. |
| 2151 | break; |
| 2152 | } |
| 2153 | |
| 2154 | return res; |
| 2155 | } |
| 2156 | |
Jean Christophe Beyler | c3db20b | 2014-05-05 21:09:40 -0700 | [diff] [blame] | 2157 | /** |
| 2158 | * @brief Given a decoded instruction, it checks whether the instruction |
| 2159 | * sets a constant and if it does, more information is provided about the |
| 2160 | * constant being set. |
| 2161 | * @param ptr_value pointer to a 64-bit holder for the constant. |
| 2162 | * @param wide Updated by function whether a wide constant is being set by bytecode. |
| 2163 | * @return Returns false if the decoded instruction does not represent a constant bytecode. |
| 2164 | */ |
| 2165 | bool MIR::DecodedInstruction::GetConstant(int64_t* ptr_value, bool* wide) const { |
| 2166 | bool sets_const = true; |
| 2167 | int64_t value = vB; |
| 2168 | |
| 2169 | DCHECK(ptr_value != nullptr); |
| 2170 | DCHECK(wide != nullptr); |
| 2171 | |
| 2172 | switch (opcode) { |
| 2173 | case Instruction::CONST_4: |
| 2174 | case Instruction::CONST_16: |
| 2175 | case Instruction::CONST: |
| 2176 | *wide = false; |
| 2177 | value <<= 32; // In order to get the sign extend. |
| 2178 | value >>= 32; |
| 2179 | break; |
| 2180 | case Instruction::CONST_HIGH16: |
| 2181 | *wide = false; |
| 2182 | value <<= 48; // In order to get the sign extend. |
| 2183 | value >>= 32; |
| 2184 | break; |
| 2185 | case Instruction::CONST_WIDE_16: |
| 2186 | case Instruction::CONST_WIDE_32: |
| 2187 | *wide = true; |
| 2188 | value <<= 32; // In order to get the sign extend. |
| 2189 | value >>= 32; |
| 2190 | break; |
| 2191 | case Instruction::CONST_WIDE: |
| 2192 | *wide = true; |
| 2193 | value = vB_wide; |
| 2194 | break; |
| 2195 | case Instruction::CONST_WIDE_HIGH16: |
| 2196 | *wide = true; |
| 2197 | value <<= 48; // In order to get the sign extend. |
| 2198 | break; |
| 2199 | default: |
| 2200 | sets_const = false; |
| 2201 | break; |
| 2202 | } |
| 2203 | |
| 2204 | if (sets_const) { |
| 2205 | *ptr_value = value; |
| 2206 | } |
| 2207 | |
| 2208 | return sets_const; |
| 2209 | } |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2210 | |
| 2211 | void BasicBlock::ResetOptimizationFlags(uint16_t reset_flags) { |
| 2212 | // Reset flags for all MIRs in bb. |
| 2213 | for (MIR* mir = first_mir_insn; mir != NULL; mir = mir->next) { |
| 2214 | mir->optimization_flags &= (~reset_flags); |
| 2215 | } |
| 2216 | } |
| 2217 | |
| 2218 | void BasicBlock::Hide(CompilationUnit* c_unit) { |
| 2219 | // First lets make it a dalvik bytecode block so it doesn't have any special meaning. |
| 2220 | block_type = kDalvikByteCode; |
| 2221 | |
| 2222 | // Mark it as hidden. |
| 2223 | hidden = true; |
| 2224 | |
| 2225 | // Detach it from its MIRs so we don't generate code for them. Also detached MIRs |
| 2226 | // are updated to know that they no longer have a parent. |
| 2227 | for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { |
| 2228 | mir->bb = NullBasicBlockId; |
| 2229 | } |
| 2230 | first_mir_insn = nullptr; |
| 2231 | last_mir_insn = nullptr; |
| 2232 | |
| 2233 | GrowableArray<BasicBlockId>::Iterator iterator(predecessors); |
| 2234 | |
| 2235 | MIRGraph* mir_graph = c_unit->mir_graph.get(); |
| 2236 | while (true) { |
| 2237 | BasicBlock* pred_bb = mir_graph->GetBasicBlock(iterator.Next()); |
| 2238 | if (pred_bb == nullptr) { |
| 2239 | break; |
| 2240 | } |
| 2241 | |
| 2242 | // Sadly we have to go through the children by hand here. |
| 2243 | pred_bb->ReplaceChild(id, NullBasicBlockId); |
| 2244 | } |
| 2245 | |
| 2246 | // Iterate through children of bb we are hiding. |
| 2247 | ChildBlockIterator successorChildIter(this, mir_graph); |
| 2248 | |
| 2249 | for (BasicBlock* childPtr = successorChildIter.Next(); childPtr != 0; childPtr = successorChildIter.Next()) { |
| 2250 | // Replace child with null child. |
| 2251 | childPtr->predecessors->Delete(id); |
| 2252 | } |
Jean Christophe Beyler | f588b50 | 2014-06-18 14:14:15 -0700 | [diff] [blame] | 2253 | |
| 2254 | // Remove link to children. |
| 2255 | taken = NullBasicBlockId; |
| 2256 | fall_through = NullBasicBlockId; |
| 2257 | successor_block_list_type = kNotUsed; |
Jean Christophe Beyler | 8512758 | 2014-05-11 23:36:41 -0700 | [diff] [blame] | 2258 | } |
| 2259 | |
| 2260 | bool BasicBlock::IsSSALiveOut(const CompilationUnit* c_unit, int ssa_reg) { |
| 2261 | // In order to determine if the ssa reg is live out, we scan all the MIRs. We remember |
| 2262 | // the last SSA number of the same dalvik register. At the end, if it is different than ssa_reg, |
| 2263 | // then it is not live out of this BB. |
| 2264 | int dalvik_reg = c_unit->mir_graph->SRegToVReg(ssa_reg); |
| 2265 | |
| 2266 | int last_ssa_reg = -1; |
| 2267 | |
| 2268 | // Walk through the MIRs backwards. |
| 2269 | for (MIR* mir = first_mir_insn; mir != nullptr; mir = mir->next) { |
| 2270 | // Get ssa rep. |
| 2271 | SSARepresentation *ssa_rep = mir->ssa_rep; |
| 2272 | |
| 2273 | // Go through the defines for this MIR. |
| 2274 | for (int i = 0; i < ssa_rep->num_defs; i++) { |
| 2275 | DCHECK(ssa_rep->defs != nullptr); |
| 2276 | |
| 2277 | // Get the ssa reg. |
| 2278 | int def_ssa_reg = ssa_rep->defs[i]; |
| 2279 | |
| 2280 | // Get dalvik reg. |
| 2281 | int def_dalvik_reg = c_unit->mir_graph->SRegToVReg(def_ssa_reg); |
| 2282 | |
| 2283 | // Compare dalvik regs. |
| 2284 | if (dalvik_reg == def_dalvik_reg) { |
| 2285 | // We found a def of the register that we are being asked about. |
| 2286 | // Remember it. |
| 2287 | last_ssa_reg = def_ssa_reg; |
| 2288 | } |
| 2289 | } |
| 2290 | } |
| 2291 | |
| 2292 | if (last_ssa_reg == -1) { |
| 2293 | // If we get to this point we couldn't find a define of register user asked about. |
| 2294 | // Let's assume the user knows what he's doing so we can be safe and say that if we |
| 2295 | // couldn't find a def, it is live out. |
| 2296 | return true; |
| 2297 | } |
| 2298 | |
| 2299 | // If it is not -1, we found a match, is it ssa_reg? |
| 2300 | return (ssa_reg == last_ssa_reg); |
| 2301 | } |
| 2302 | |
| 2303 | bool BasicBlock::ReplaceChild(BasicBlockId old_bb, BasicBlockId new_bb) { |
| 2304 | // We need to check taken, fall_through, and successor_blocks to replace. |
| 2305 | bool found = false; |
| 2306 | if (taken == old_bb) { |
| 2307 | taken = new_bb; |
| 2308 | found = true; |
| 2309 | } |
| 2310 | |
| 2311 | if (fall_through == old_bb) { |
| 2312 | fall_through = new_bb; |
| 2313 | found = true; |
| 2314 | } |
| 2315 | |
| 2316 | if (successor_block_list_type != kNotUsed) { |
| 2317 | GrowableArray<SuccessorBlockInfo*>::Iterator iterator(successor_blocks); |
| 2318 | while (true) { |
| 2319 | SuccessorBlockInfo* successor_block_info = iterator.Next(); |
| 2320 | if (successor_block_info == nullptr) { |
| 2321 | break; |
| 2322 | } |
| 2323 | if (successor_block_info->block == old_bb) { |
| 2324 | successor_block_info->block = new_bb; |
| 2325 | found = true; |
| 2326 | } |
| 2327 | } |
| 2328 | } |
| 2329 | |
| 2330 | return found; |
| 2331 | } |
| 2332 | |
| 2333 | void BasicBlock::UpdatePredecessor(BasicBlockId old_parent, BasicBlockId new_parent) { |
| 2334 | GrowableArray<BasicBlockId>::Iterator iterator(predecessors); |
| 2335 | bool found = false; |
| 2336 | |
| 2337 | while (true) { |
| 2338 | BasicBlockId pred_bb_id = iterator.Next(); |
| 2339 | |
| 2340 | if (pred_bb_id == NullBasicBlockId) { |
| 2341 | break; |
| 2342 | } |
| 2343 | |
| 2344 | if (pred_bb_id == old_parent) { |
| 2345 | size_t idx = iterator.GetIndex() - 1; |
| 2346 | predecessors->Put(idx, new_parent); |
| 2347 | found = true; |
| 2348 | break; |
| 2349 | } |
| 2350 | } |
| 2351 | |
| 2352 | // If not found, add it. |
| 2353 | if (found == false) { |
| 2354 | predecessors->Insert(new_parent); |
| 2355 | } |
| 2356 | } |
| 2357 | |
| 2358 | // Create a new basic block with block_id as num_blocks_ that is |
| 2359 | // post-incremented. |
| 2360 | BasicBlock* MIRGraph::CreateNewBB(BBType block_type) { |
| 2361 | BasicBlock* res = NewMemBB(block_type, num_blocks_++); |
| 2362 | block_list_.Insert(res); |
| 2363 | return res; |
| 2364 | } |
| 2365 | |
Jean Christophe Beyler | 2469e60 | 2014-05-06 20:36:55 -0700 | [diff] [blame] | 2366 | void MIRGraph::CalculateBasicBlockInformation() { |
| 2367 | PassDriverMEPostOpt driver(cu_); |
| 2368 | driver.Launch(); |
| 2369 | } |
| 2370 | |
| 2371 | void MIRGraph::InitializeBasicBlockData() { |
| 2372 | num_blocks_ = block_list_.Size(); |
| 2373 | } |
| 2374 | |
Jean Christophe Beyler | fb0ea2d | 2014-07-29 13:20:42 -0700 | [diff] [blame] | 2375 | int MIR::DecodedInstruction::FlagsOf() const { |
| 2376 | // Calculate new index. |
| 2377 | int idx = static_cast<int>(opcode) - kNumPackedOpcodes; |
| 2378 | |
| 2379 | // Check if it is an extended or not. |
| 2380 | if (idx < 0) { |
| 2381 | return Instruction::FlagsOf(opcode); |
| 2382 | } |
| 2383 | |
| 2384 | // For extended, we use a switch. |
| 2385 | switch (static_cast<int>(opcode)) { |
| 2386 | case kMirOpPhi: |
| 2387 | return Instruction::kContinue; |
| 2388 | case kMirOpCopy: |
| 2389 | return Instruction::kContinue; |
| 2390 | case kMirOpFusedCmplFloat: |
| 2391 | return Instruction::kContinue | Instruction::kBranch; |
| 2392 | case kMirOpFusedCmpgFloat: |
| 2393 | return Instruction::kContinue | Instruction::kBranch; |
| 2394 | case kMirOpFusedCmplDouble: |
| 2395 | return Instruction::kContinue | Instruction::kBranch; |
| 2396 | case kMirOpFusedCmpgDouble: |
| 2397 | return Instruction::kContinue | Instruction::kBranch; |
| 2398 | case kMirOpFusedCmpLong: |
| 2399 | return Instruction::kContinue | Instruction::kBranch; |
| 2400 | case kMirOpNop: |
| 2401 | return Instruction::kContinue; |
| 2402 | case kMirOpNullCheck: |
| 2403 | return Instruction::kContinue | Instruction::kThrow; |
| 2404 | case kMirOpRangeCheck: |
| 2405 | return Instruction::kContinue | Instruction::kThrow; |
| 2406 | case kMirOpDivZeroCheck: |
| 2407 | return Instruction::kContinue | Instruction::kThrow; |
| 2408 | case kMirOpCheck: |
| 2409 | return 0; |
| 2410 | case kMirOpCheckPart2: |
| 2411 | return 0; |
| 2412 | case kMirOpSelect: |
| 2413 | return Instruction::kContinue; |
| 2414 | case kMirOpConstVector: |
| 2415 | return Instruction::kContinue; |
| 2416 | case kMirOpMoveVector: |
| 2417 | return Instruction::kContinue; |
| 2418 | case kMirOpPackedMultiply: |
| 2419 | return Instruction::kContinue; |
| 2420 | case kMirOpPackedAddition: |
| 2421 | return Instruction::kContinue; |
| 2422 | case kMirOpPackedSubtract: |
| 2423 | return Instruction::kContinue; |
| 2424 | case kMirOpPackedShiftLeft: |
| 2425 | return Instruction::kContinue; |
| 2426 | case kMirOpPackedSignedShiftRight: |
| 2427 | return Instruction::kContinue; |
| 2428 | case kMirOpPackedUnsignedShiftRight: |
| 2429 | return Instruction::kContinue; |
| 2430 | case kMirOpPackedAnd: |
| 2431 | return Instruction::kContinue; |
| 2432 | case kMirOpPackedOr: |
| 2433 | return Instruction::kContinue; |
| 2434 | case kMirOpPackedXor: |
| 2435 | return Instruction::kContinue; |
| 2436 | case kMirOpPackedAddReduce: |
| 2437 | return Instruction::kContinue; |
| 2438 | case kMirOpPackedReduce: |
| 2439 | return Instruction::kContinue; |
| 2440 | case kMirOpPackedSet: |
| 2441 | return Instruction::kContinue; |
| 2442 | case kMirOpReserveVectorRegisters: |
| 2443 | return Instruction::kContinue; |
| 2444 | case kMirOpReturnVectorRegisters: |
| 2445 | return Instruction::kContinue; |
| 2446 | default: |
| 2447 | LOG(WARNING) << "ExtendedFlagsOf: Unhandled case: " << static_cast<int> (opcode); |
| 2448 | return 0; |
| 2449 | } |
| 2450 | } |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 2451 | } // namespace art |