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> |
| 20 | |
Ian Rogers | 6282dc1 | 2013-04-18 15:54:02 -0700 | [diff] [blame] | 21 | #include "base/stl_util.h" |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 22 | #include "compiler_internals.h" |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 23 | #include "dex_file-inl.h" |
Ian Rogers | 29a2648 | 2014-05-02 15:27:29 -0700 | [diff] [blame] | 24 | #include "dex_instruction-inl.h" |
Vladimir Marko | 5816ed4 | 2013-11-27 17:04:20 +0000 | [diff] [blame] | 25 | #include "dex/quick/dex_file_to_method_inliner_map.h" |
| 26 | #include "dex/quick/dex_file_method_inliner.h" |
Nicolas Geoffray | f3e2cc4 | 2014-02-18 18:37:26 +0000 | [diff] [blame] | 27 | #include "leb128.h" |
Vladimir Marko | 5816ed4 | 2013-11-27 17:04:20 +0000 | [diff] [blame] | 28 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 29 | namespace art { |
| 30 | |
| 31 | #define MAX_PATTERN_LEN 5 |
| 32 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 33 | const char* MIRGraph::extended_mir_op_names_[kMirOpLast - kMirOpFirst] = { |
| 34 | "Phi", |
| 35 | "Copy", |
| 36 | "FusedCmplFloat", |
| 37 | "FusedCmpgFloat", |
| 38 | "FusedCmplDouble", |
| 39 | "FusedCmpgDouble", |
| 40 | "FusedCmpLong", |
| 41 | "Nop", |
| 42 | "OpNullCheck", |
| 43 | "OpRangeCheck", |
| 44 | "OpDivZeroCheck", |
| 45 | "Check1", |
| 46 | "Check2", |
| 47 | "Select", |
| 48 | }; |
| 49 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 50 | MIRGraph::MIRGraph(CompilationUnit* cu, ArenaAllocator* arena) |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 51 | : reg_location_(NULL), |
| 52 | cu_(cu), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 53 | ssa_base_vregs_(NULL), |
| 54 | ssa_subscripts_(NULL), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 55 | vreg_to_ssa_map_(NULL), |
| 56 | ssa_last_defs_(NULL), |
| 57 | is_constant_v_(NULL), |
| 58 | constant_values_(NULL), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 59 | use_counts_(arena, 256, kGrowableArrayMisc), |
| 60 | raw_use_counts_(arena, 256, kGrowableArrayMisc), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 61 | num_reachable_blocks_(0), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 62 | dfs_order_(NULL), |
| 63 | dfs_post_order_(NULL), |
| 64 | dom_post_order_traversal_(NULL), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 65 | i_dom_list_(NULL), |
| 66 | def_block_matrix_(NULL), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 67 | temp_dalvik_register_v_(NULL), |
Vladimir Marko | bfea9c2 | 2014-01-17 17:49:33 +0000 | [diff] [blame] | 68 | temp_scoped_alloc_(), |
| 69 | temp_insn_data_(nullptr), |
| 70 | temp_bit_vector_size_(0u), |
| 71 | temp_bit_vector_(nullptr), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 72 | block_list_(arena, 100, kGrowableArrayBlockList), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 73 | try_block_addr_(NULL), |
| 74 | entry_block_(NULL), |
| 75 | exit_block_(NULL), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 76 | num_blocks_(0), |
| 77 | current_code_item_(NULL), |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 78 | dex_pc_to_block_map_(arena, 0, kGrowableArrayMisc), |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 79 | current_method_(kInvalidEntry), |
| 80 | current_offset_(kInvalidEntry), |
| 81 | def_count_(0), |
| 82 | opcode_count_(NULL), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 83 | num_ssa_regs_(0), |
| 84 | method_sreg_(0), |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 85 | attributes_(METHOD_IS_LEAF), // Start with leaf assumption, change on encountering invoke. |
| 86 | checkstats_(NULL), |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 87 | arena_(arena), |
| 88 | backward_branches_(0), |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame] | 89 | forward_branches_(0), |
| 90 | compiler_temps_(arena, 6, kGrowableArrayMisc), |
| 91 | num_non_special_compiler_temps_(0), |
buzbee | b1f1d64 | 2014-02-27 12:55:32 -0800 | [diff] [blame] | 92 | max_available_non_special_compiler_temps_(0), |
Vladimir Marko | be0e546 | 2014-02-26 11:24:15 +0000 | [diff] [blame] | 93 | punt_to_interpreter_(false), |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 94 | merged_df_flags_(0u), |
Vladimir Marko | be0e546 | 2014-02-26 11:24:15 +0000 | [diff] [blame] | 95 | ifield_lowering_infos_(arena, 0u), |
Vladimir Marko | f096aad | 2014-01-23 15:51:58 +0000 | [diff] [blame] | 96 | sfield_lowering_infos_(arena, 0u), |
| 97 | method_lowering_infos_(arena, 0u) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 98 | try_block_addr_ = new (arena_) ArenaBitVector(arena_, 0, true /* expandable */); |
Razvan A Lupusoru | da7a69b | 2014-01-08 15:09:50 -0800 | [diff] [blame] | 99 | max_available_special_compiler_temps_ = std::abs(static_cast<int>(kVRegNonSpecialTempBaseReg)) |
| 100 | - std::abs(static_cast<int>(kVRegTempBaseReg)); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 101 | } |
| 102 | |
Ian Rogers | 6282dc1 | 2013-04-18 15:54:02 -0700 | [diff] [blame] | 103 | MIRGraph::~MIRGraph() { |
| 104 | STLDeleteElements(&m_units_); |
| 105 | } |
| 106 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 107 | /* |
| 108 | * Parse an instruction, return the length of the instruction |
| 109 | */ |
Ian Rogers | 29a2648 | 2014-05-02 15:27:29 -0700 | [diff] [blame] | 110 | int MIRGraph::ParseInsn(const uint16_t* code_ptr, MIR::DecodedInstruction* decoded_instruction) { |
| 111 | const Instruction* inst = Instruction::At(code_ptr); |
| 112 | decoded_instruction->opcode = inst->Opcode(); |
| 113 | decoded_instruction->vA = inst->HasVRegA() ? inst->VRegA() : 0; |
| 114 | decoded_instruction->vB = inst->HasVRegB() ? inst->VRegB() : 0; |
| 115 | decoded_instruction->vB_wide = inst->HasWideVRegB() ? inst->WideVRegB() : 0; |
| 116 | decoded_instruction->vC = inst->HasVRegC() ? inst->VRegC() : 0; |
| 117 | if (inst->HasVarArgs()) { |
| 118 | inst->GetVarArgs(decoded_instruction->arg); |
| 119 | } |
| 120 | return inst->SizeInCodeUnits(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 121 | } |
| 122 | |
| 123 | |
| 124 | /* Split an existing block from the specified code offset into two */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 125 | BasicBlock* MIRGraph::SplitBlock(DexOffset code_offset, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 126 | BasicBlock* orig_block, BasicBlock** immed_pred_block_p) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 127 | DCHECK_GT(code_offset, orig_block->start_offset); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 128 | MIR* insn = orig_block->first_mir_insn; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 129 | MIR* prev = NULL; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 130 | while (insn) { |
| 131 | if (insn->offset == code_offset) break; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 132 | prev = insn; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 133 | insn = insn->next; |
| 134 | } |
| 135 | if (insn == NULL) { |
| 136 | LOG(FATAL) << "Break split failed"; |
| 137 | } |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 138 | BasicBlock *bottom_block = NewMemBB(kDalvikByteCode, num_blocks_++); |
| 139 | block_list_.Insert(bottom_block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 140 | |
| 141 | bottom_block->start_offset = code_offset; |
| 142 | bottom_block->first_mir_insn = insn; |
| 143 | bottom_block->last_mir_insn = orig_block->last_mir_insn; |
| 144 | |
| 145 | /* If this block was terminated by a return, the flag needs to go with the bottom block */ |
| 146 | bottom_block->terminated_by_return = orig_block->terminated_by_return; |
| 147 | orig_block->terminated_by_return = false; |
| 148 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 149 | /* Handle the taken path */ |
| 150 | bottom_block->taken = orig_block->taken; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 151 | if (bottom_block->taken != NullBasicBlockId) { |
| 152 | orig_block->taken = NullBasicBlockId; |
| 153 | BasicBlock* bb_taken = GetBasicBlock(bottom_block->taken); |
| 154 | bb_taken->predecessors->Delete(orig_block->id); |
| 155 | bb_taken->predecessors->Insert(bottom_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 156 | } |
| 157 | |
| 158 | /* Handle the fallthrough path */ |
| 159 | bottom_block->fall_through = orig_block->fall_through; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 160 | orig_block->fall_through = bottom_block->id; |
| 161 | bottom_block->predecessors->Insert(orig_block->id); |
| 162 | if (bottom_block->fall_through != NullBasicBlockId) { |
| 163 | BasicBlock* bb_fall_through = GetBasicBlock(bottom_block->fall_through); |
| 164 | bb_fall_through->predecessors->Delete(orig_block->id); |
| 165 | bb_fall_through->predecessors->Insert(bottom_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 166 | } |
| 167 | |
| 168 | /* Handle the successor list */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 169 | if (orig_block->successor_block_list_type != kNotUsed) { |
| 170 | bottom_block->successor_block_list_type = orig_block->successor_block_list_type; |
| 171 | bottom_block->successor_blocks = orig_block->successor_blocks; |
| 172 | orig_block->successor_block_list_type = kNotUsed; |
| 173 | orig_block->successor_blocks = NULL; |
| 174 | GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bottom_block->successor_blocks); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 175 | while (true) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 176 | SuccessorBlockInfo *successor_block_info = iterator.Next(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 177 | if (successor_block_info == NULL) break; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 178 | BasicBlock *bb = GetBasicBlock(successor_block_info->block); |
| 179 | bb->predecessors->Delete(orig_block->id); |
| 180 | bb->predecessors->Insert(bottom_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 181 | } |
| 182 | } |
| 183 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 184 | orig_block->last_mir_insn = prev; |
| 185 | prev->next = NULL; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 186 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 187 | /* |
| 188 | * Update the immediate predecessor block pointer so that outgoing edges |
| 189 | * can be applied to the proper block. |
| 190 | */ |
| 191 | if (immed_pred_block_p) { |
| 192 | DCHECK_EQ(*immed_pred_block_p, orig_block); |
| 193 | *immed_pred_block_p = bottom_block; |
| 194 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 195 | |
| 196 | // Associate dex instructions in the bottom block with the new container. |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 197 | DCHECK(insn != nullptr); |
| 198 | DCHECK(insn != orig_block->first_mir_insn); |
| 199 | DCHECK(insn == bottom_block->first_mir_insn); |
| 200 | DCHECK_EQ(insn->offset, bottom_block->start_offset); |
| 201 | DCHECK(static_cast<int>(insn->dalvikInsn.opcode) == kMirOpCheck || |
| 202 | !IsPseudoMirOp(insn->dalvikInsn.opcode)); |
| 203 | DCHECK_EQ(dex_pc_to_block_map_.Get(insn->offset), orig_block->id); |
| 204 | MIR* p = insn; |
| 205 | dex_pc_to_block_map_.Put(p->offset, bottom_block->id); |
| 206 | while (p != bottom_block->last_mir_insn) { |
| 207 | p = p->next; |
| 208 | DCHECK(p != nullptr); |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 209 | int opcode = p->dalvikInsn.opcode; |
| 210 | /* |
| 211 | * Some messiness here to ensure that we only enter real opcodes and only the |
| 212 | * first half of a potentially throwing instruction that has been split into |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 213 | * CHECK and work portions. Since the 2nd half of a split operation is always |
| 214 | * the first in a BasicBlock, we can't hit it here. |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 215 | */ |
Vladimir Marko | 4376c87 | 2014-01-23 12:39:29 +0000 | [diff] [blame] | 216 | if ((opcode == kMirOpCheck) || !IsPseudoMirOp(opcode)) { |
| 217 | DCHECK_EQ(dex_pc_to_block_map_.Get(p->offset), orig_block->id); |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 218 | dex_pc_to_block_map_.Put(p->offset, bottom_block->id); |
| 219 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 220 | } |
| 221 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 222 | return bottom_block; |
| 223 | } |
| 224 | |
| 225 | /* |
| 226 | * Given a code offset, find out the block that starts with it. If the offset |
| 227 | * is in the middle of an existing block, split it into two. If immed_pred_block_p |
| 228 | * is not non-null and is the block being split, update *immed_pred_block_p to |
| 229 | * point to the bottom block so that outgoing edges can be set up properly |
| 230 | * (by the caller) |
| 231 | * Utilizes a map for fast lookup of the typical cases. |
| 232 | */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 233 | BasicBlock* MIRGraph::FindBlock(DexOffset code_offset, bool split, bool create, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 234 | BasicBlock** immed_pred_block_p) { |
buzbee | bd663de | 2013-09-10 15:41:31 -0700 | [diff] [blame] | 235 | if (code_offset >= cu_->code_item->insns_size_in_code_units_) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 236 | return NULL; |
| 237 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 238 | |
| 239 | int block_id = dex_pc_to_block_map_.Get(code_offset); |
| 240 | BasicBlock* bb = (block_id == 0) ? NULL : block_list_.Get(block_id); |
| 241 | |
| 242 | if ((bb != NULL) && (bb->start_offset == code_offset)) { |
| 243 | // Does this containing block start with the desired instruction? |
buzbee | bd663de | 2013-09-10 15:41:31 -0700 | [diff] [blame] | 244 | return bb; |
| 245 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 246 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 247 | // No direct hit. |
| 248 | if (!create) { |
| 249 | return NULL; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 250 | } |
| 251 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 252 | if (bb != NULL) { |
| 253 | // The target exists somewhere in an existing block. |
| 254 | return SplitBlock(code_offset, bb, bb == *immed_pred_block_p ? immed_pred_block_p : NULL); |
| 255 | } |
| 256 | |
| 257 | // Create a new block. |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 258 | bb = NewMemBB(kDalvikByteCode, num_blocks_++); |
| 259 | block_list_.Insert(bb); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 260 | bb->start_offset = code_offset; |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 261 | dex_pc_to_block_map_.Put(bb->start_offset, bb->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 262 | return bb; |
| 263 | } |
| 264 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 265 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 266 | /* 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] | 267 | void MIRGraph::ProcessTryCatchBlocks() { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 268 | int tries_size = current_code_item_->tries_size_; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 269 | DexOffset offset; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 270 | |
| 271 | if (tries_size == 0) { |
| 272 | return; |
| 273 | } |
| 274 | |
| 275 | for (int i = 0; i < tries_size; i++) { |
| 276 | const DexFile::TryItem* pTry = |
| 277 | DexFile::GetTryItems(*current_code_item_, i); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 278 | DexOffset start_offset = pTry->start_addr_; |
| 279 | DexOffset end_offset = start_offset + pTry->insn_count_; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 280 | for (offset = start_offset; offset < end_offset; offset++) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 281 | try_block_addr_->SetBit(offset); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 282 | } |
| 283 | } |
| 284 | |
| 285 | // Iterate over each of the handlers to enqueue the empty Catch blocks |
| 286 | const byte* handlers_ptr = DexFile::GetCatchHandlerData(*current_code_item_, 0); |
| 287 | uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr); |
| 288 | for (uint32_t idx = 0; idx < handlers_size; idx++) { |
| 289 | CatchHandlerIterator iterator(handlers_ptr); |
| 290 | for (; iterator.HasNext(); iterator.Next()) { |
| 291 | uint32_t address = iterator.GetHandlerAddress(); |
| 292 | FindBlock(address, false /* split */, true /*create*/, |
| 293 | /* immed_pred_block_p */ NULL); |
| 294 | } |
| 295 | handlers_ptr = iterator.EndDataPointer(); |
| 296 | } |
| 297 | } |
| 298 | |
| 299 | /* Process instructions with the kBranch flag */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 300 | BasicBlock* MIRGraph::ProcessCanBranch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, |
| 301 | int width, int flags, const uint16_t* code_ptr, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 302 | const uint16_t* code_end) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 303 | DexOffset target = cur_offset; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 304 | switch (insn->dalvikInsn.opcode) { |
| 305 | case Instruction::GOTO: |
| 306 | case Instruction::GOTO_16: |
| 307 | case Instruction::GOTO_32: |
| 308 | target += insn->dalvikInsn.vA; |
| 309 | break; |
| 310 | case Instruction::IF_EQ: |
| 311 | case Instruction::IF_NE: |
| 312 | case Instruction::IF_LT: |
| 313 | case Instruction::IF_GE: |
| 314 | case Instruction::IF_GT: |
| 315 | case Instruction::IF_LE: |
| 316 | cur_block->conditional_branch = true; |
| 317 | target += insn->dalvikInsn.vC; |
| 318 | break; |
| 319 | case Instruction::IF_EQZ: |
| 320 | case Instruction::IF_NEZ: |
| 321 | case Instruction::IF_LTZ: |
| 322 | case Instruction::IF_GEZ: |
| 323 | case Instruction::IF_GTZ: |
| 324 | case Instruction::IF_LEZ: |
| 325 | cur_block->conditional_branch = true; |
| 326 | target += insn->dalvikInsn.vB; |
| 327 | break; |
| 328 | default: |
| 329 | LOG(FATAL) << "Unexpected opcode(" << insn->dalvikInsn.opcode << ") with kBranch set"; |
| 330 | } |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 331 | CountBranch(target); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 332 | BasicBlock *taken_block = FindBlock(target, /* split */ true, /* create */ true, |
| 333 | /* immed_pred_block_p */ &cur_block); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 334 | cur_block->taken = taken_block->id; |
| 335 | taken_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 336 | |
| 337 | /* Always terminate the current block for conditional branches */ |
| 338 | if (flags & Instruction::kContinue) { |
| 339 | BasicBlock *fallthrough_block = FindBlock(cur_offset + width, |
| 340 | /* |
| 341 | * If the method is processed |
| 342 | * in sequential order from the |
| 343 | * beginning, we don't need to |
| 344 | * specify split for continue |
| 345 | * blocks. However, this |
| 346 | * routine can be called by |
| 347 | * compileLoop, which starts |
| 348 | * parsing the method from an |
| 349 | * arbitrary address in the |
| 350 | * method body. |
| 351 | */ |
| 352 | true, |
| 353 | /* create */ |
| 354 | true, |
| 355 | /* immed_pred_block_p */ |
| 356 | &cur_block); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 357 | cur_block->fall_through = fallthrough_block->id; |
| 358 | fallthrough_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 359 | } else if (code_ptr < code_end) { |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 360 | FindBlock(cur_offset + width, /* split */ false, /* create */ true, |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 361 | /* immed_pred_block_p */ NULL); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 362 | } |
| 363 | return cur_block; |
| 364 | } |
| 365 | |
| 366 | /* Process instructions with the kSwitch flag */ |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 367 | BasicBlock* MIRGraph::ProcessCanSwitch(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, |
| 368 | int width, int flags) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 369 | const uint16_t* switch_data = |
| 370 | reinterpret_cast<const uint16_t*>(GetCurrentInsns() + cur_offset + insn->dalvikInsn.vB); |
| 371 | int size; |
| 372 | const int* keyTable; |
| 373 | const int* target_table; |
| 374 | int i; |
| 375 | int first_key; |
| 376 | |
| 377 | /* |
| 378 | * Packed switch data format: |
| 379 | * ushort ident = 0x0100 magic value |
| 380 | * ushort size number of entries in the table |
| 381 | * int first_key first (and lowest) switch case value |
| 382 | * int targets[size] branch targets, relative to switch opcode |
| 383 | * |
| 384 | * Total size is (4+size*2) 16-bit code units. |
| 385 | */ |
| 386 | if (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) { |
| 387 | DCHECK_EQ(static_cast<int>(switch_data[0]), |
| 388 | static_cast<int>(Instruction::kPackedSwitchSignature)); |
| 389 | size = switch_data[1]; |
| 390 | first_key = switch_data[2] | (switch_data[3] << 16); |
| 391 | target_table = reinterpret_cast<const int*>(&switch_data[4]); |
| 392 | keyTable = NULL; // Make the compiler happy |
| 393 | /* |
| 394 | * Sparse switch data format: |
| 395 | * ushort ident = 0x0200 magic value |
| 396 | * ushort size number of entries in the table; > 0 |
| 397 | * int keys[size] keys, sorted low-to-high; 32-bit aligned |
| 398 | * int targets[size] branch targets, relative to switch opcode |
| 399 | * |
| 400 | * Total size is (2+size*4) 16-bit code units. |
| 401 | */ |
| 402 | } else { |
| 403 | DCHECK_EQ(static_cast<int>(switch_data[0]), |
| 404 | static_cast<int>(Instruction::kSparseSwitchSignature)); |
| 405 | size = switch_data[1]; |
| 406 | keyTable = reinterpret_cast<const int*>(&switch_data[2]); |
| 407 | target_table = reinterpret_cast<const int*>(&switch_data[2 + size*2]); |
| 408 | first_key = 0; // To make the compiler happy |
| 409 | } |
| 410 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 411 | if (cur_block->successor_block_list_type != kNotUsed) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 412 | LOG(FATAL) << "Successor block list already in use: " |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 413 | << static_cast<int>(cur_block->successor_block_list_type); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 414 | } |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 415 | cur_block->successor_block_list_type = |
| 416 | (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? kPackedSwitch : kSparseSwitch; |
| 417 | cur_block->successor_blocks = |
Brian Carlstrom | df62950 | 2013-07-17 22:39:56 -0700 | [diff] [blame] | 418 | new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, size, kGrowableArraySuccessorBlocks); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 419 | |
| 420 | for (i = 0; i < size; i++) { |
| 421 | BasicBlock *case_block = FindBlock(cur_offset + target_table[i], /* split */ true, |
| 422 | /* create */ true, /* immed_pred_block_p */ &cur_block); |
| 423 | SuccessorBlockInfo *successor_block_info = |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 424 | static_cast<SuccessorBlockInfo*>(arena_->Alloc(sizeof(SuccessorBlockInfo), |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 425 | kArenaAllocSuccessor)); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 426 | successor_block_info->block = case_block->id; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 427 | successor_block_info->key = |
| 428 | (insn->dalvikInsn.opcode == Instruction::PACKED_SWITCH) ? |
| 429 | first_key + i : keyTable[i]; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 430 | cur_block->successor_blocks->Insert(successor_block_info); |
| 431 | case_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 432 | } |
| 433 | |
| 434 | /* Fall-through case */ |
Brian Carlstrom | df62950 | 2013-07-17 22:39:56 -0700 | [diff] [blame] | 435 | BasicBlock* fallthrough_block = FindBlock(cur_offset + width, /* split */ false, |
| 436 | /* create */ true, /* immed_pred_block_p */ NULL); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 437 | cur_block->fall_through = fallthrough_block->id; |
| 438 | fallthrough_block->predecessors->Insert(cur_block->id); |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 439 | return cur_block; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 440 | } |
| 441 | |
| 442 | /* Process instructions with the kThrow flag */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 443 | BasicBlock* MIRGraph::ProcessCanThrow(BasicBlock* cur_block, MIR* insn, DexOffset cur_offset, |
| 444 | int width, int flags, ArenaBitVector* try_block_addr, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 445 | const uint16_t* code_ptr, const uint16_t* code_end) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 446 | bool in_try_block = try_block_addr->IsBitSet(cur_offset); |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 447 | bool is_throw = (insn->dalvikInsn.opcode == Instruction::THROW); |
| 448 | bool build_all_edges = |
| 449 | (cu_->disable_opt & (1 << kSuppressExceptionEdges)) || is_throw || in_try_block; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 450 | |
| 451 | /* In try block */ |
| 452 | if (in_try_block) { |
| 453 | CatchHandlerIterator iterator(*current_code_item_, cur_offset); |
| 454 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 455 | if (cur_block->successor_block_list_type != kNotUsed) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 456 | LOG(INFO) << PrettyMethod(cu_->method_idx, *cu_->dex_file); |
| 457 | LOG(FATAL) << "Successor block list already in use: " |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 458 | << static_cast<int>(cur_block->successor_block_list_type); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 459 | } |
| 460 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 461 | cur_block->successor_block_list_type = kCatch; |
| 462 | cur_block->successor_blocks = |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 463 | new (arena_) GrowableArray<SuccessorBlockInfo*>(arena_, 2, kGrowableArraySuccessorBlocks); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 464 | |
Brian Carlstrom | 02c8cc6 | 2013-07-18 15:54:44 -0700 | [diff] [blame] | 465 | for (; iterator.HasNext(); iterator.Next()) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 466 | BasicBlock *catch_block = FindBlock(iterator.GetHandlerAddress(), false /* split*/, |
| 467 | false /* creat */, NULL /* immed_pred_block_p */); |
| 468 | catch_block->catch_entry = true; |
| 469 | if (kIsDebugBuild) { |
| 470 | catches_.insert(catch_block->start_offset); |
| 471 | } |
| 472 | SuccessorBlockInfo *successor_block_info = reinterpret_cast<SuccessorBlockInfo*> |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 473 | (arena_->Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 474 | successor_block_info->block = catch_block->id; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 475 | successor_block_info->key = iterator.GetHandlerTypeIndex(); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 476 | cur_block->successor_blocks->Insert(successor_block_info); |
| 477 | catch_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 478 | } |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 479 | } else if (build_all_edges) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 480 | BasicBlock *eh_block = NewMemBB(kExceptionHandling, num_blocks_++); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 481 | cur_block->taken = eh_block->id; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 482 | block_list_.Insert(eh_block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 483 | eh_block->start_offset = cur_offset; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 484 | eh_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 485 | } |
| 486 | |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 487 | if (is_throw) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 488 | cur_block->explicit_throw = true; |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 489 | if (code_ptr < code_end) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 490 | // Force creation of new block following THROW via side-effect |
| 491 | FindBlock(cur_offset + width, /* split */ false, /* create */ true, |
| 492 | /* immed_pred_block_p */ NULL); |
| 493 | } |
| 494 | if (!in_try_block) { |
| 495 | // Don't split a THROW that can't rethrow - we're done. |
| 496 | return cur_block; |
| 497 | } |
| 498 | } |
| 499 | |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 500 | if (!build_all_edges) { |
| 501 | /* |
| 502 | * Even though there is an exception edge here, control cannot return to this |
| 503 | * method. Thus, for the purposes of dataflow analysis and optimization, we can |
| 504 | * ignore the edge. Doing this reduces compile time, and increases the scope |
| 505 | * of the basic-block level optimization pass. |
| 506 | */ |
| 507 | return cur_block; |
| 508 | } |
| 509 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 510 | /* |
| 511 | * Split the potentially-throwing instruction into two parts. |
| 512 | * The first half will be a pseudo-op that captures the exception |
| 513 | * edges and terminates the basic block. It always falls through. |
| 514 | * Then, create a new basic block that begins with the throwing instruction |
| 515 | * (minus exceptions). Note: this new basic block must NOT be entered into |
| 516 | * the block_map. If the potentially-throwing instruction is the target of a |
| 517 | * future branch, we need to find the check psuedo half. The new |
| 518 | * basic block containing the work portion of the instruction should |
| 519 | * only be entered via fallthrough from the block containing the |
| 520 | * pseudo exception edge MIR. Note also that this new block is |
| 521 | * not automatically terminated after the work portion, and may |
| 522 | * contain following instructions. |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 523 | * |
| 524 | * Note also that the dex_pc_to_block_map_ entry for the potentially |
| 525 | * throwing instruction will refer to the original basic block. |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 526 | */ |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 527 | BasicBlock *new_block = NewMemBB(kDalvikByteCode, num_blocks_++); |
| 528 | block_list_.Insert(new_block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 529 | new_block->start_offset = insn->offset; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 530 | cur_block->fall_through = new_block->id; |
| 531 | new_block->predecessors->Insert(cur_block->id); |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 532 | MIR* new_insn = static_cast<MIR*>(arena_->Alloc(sizeof(MIR), kArenaAllocMIR)); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 533 | *new_insn = *insn; |
| 534 | insn->dalvikInsn.opcode = |
| 535 | static_cast<Instruction::Code>(kMirOpCheck); |
| 536 | // Associate the two halves |
| 537 | insn->meta.throw_insn = new_insn; |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 538 | new_block->AppendMIR(new_insn); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 539 | return new_block; |
| 540 | } |
| 541 | |
| 542 | /* Parse a Dex method and insert it into the MIRGraph at the current insert point. */ |
| 543 | void MIRGraph::InlineMethod(const DexFile::CodeItem* code_item, uint32_t access_flags, |
Ian Rogers | 8b2c0b9 | 2013-09-19 02:56:49 -0700 | [diff] [blame] | 544 | InvokeType invoke_type, uint16_t class_def_idx, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 545 | uint32_t method_idx, jobject class_loader, const DexFile& dex_file) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 546 | current_code_item_ = code_item; |
| 547 | method_stack_.push_back(std::make_pair(current_method_, current_offset_)); |
| 548 | current_method_ = m_units_.size(); |
| 549 | current_offset_ = 0; |
| 550 | // TODO: will need to snapshot stack image and use that as the mir context identification. |
| 551 | m_units_.push_back(new DexCompilationUnit(cu_, class_loader, Runtime::Current()->GetClassLinker(), |
Vladimir Marko | 2730db0 | 2014-01-27 11:15:17 +0000 | [diff] [blame] | 552 | dex_file, current_code_item_, class_def_idx, method_idx, access_flags, |
| 553 | cu_->compiler_driver->GetVerifiedMethod(&dex_file, method_idx))); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 554 | const uint16_t* code_ptr = current_code_item_->insns_; |
| 555 | const uint16_t* code_end = |
| 556 | current_code_item_->insns_ + current_code_item_->insns_size_in_code_units_; |
| 557 | |
| 558 | // 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] | 559 | // TUNING: use better estimate of basic blocks for following resize. |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 560 | 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] | 561 | 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] | 562 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 563 | // TODO: replace with explicit resize routine. Using automatic extension side effect for now. |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 564 | try_block_addr_->SetBit(current_code_item_->insns_size_in_code_units_); |
| 565 | try_block_addr_->ClearBit(current_code_item_->insns_size_in_code_units_); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 566 | |
| 567 | // If this is the first method, set up default entry and exit blocks. |
| 568 | if (current_method_ == 0) { |
| 569 | DCHECK(entry_block_ == NULL); |
| 570 | DCHECK(exit_block_ == NULL); |
Brian Carlstrom | 4274889 | 2013-07-18 18:04:08 -0700 | [diff] [blame] | 571 | DCHECK_EQ(num_blocks_, 0); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 572 | // Use id 0 to represent a null block. |
| 573 | BasicBlock* null_block = NewMemBB(kNullBlock, num_blocks_++); |
| 574 | DCHECK_EQ(null_block->id, NullBasicBlockId); |
| 575 | null_block->hidden = true; |
| 576 | block_list_.Insert(null_block); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 577 | entry_block_ = NewMemBB(kEntryBlock, num_blocks_++); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 578 | block_list_.Insert(entry_block_); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 579 | exit_block_ = NewMemBB(kExitBlock, num_blocks_++); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 580 | block_list_.Insert(exit_block_); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 581 | // TODO: deprecate all "cu->" fields; move what's left to wherever CompilationUnit is allocated. |
| 582 | cu_->dex_file = &dex_file; |
| 583 | cu_->class_def_idx = class_def_idx; |
| 584 | cu_->method_idx = method_idx; |
| 585 | cu_->access_flags = access_flags; |
| 586 | cu_->invoke_type = invoke_type; |
| 587 | cu_->shorty = dex_file.GetMethodShorty(dex_file.GetMethodId(method_idx)); |
| 588 | cu_->num_ins = current_code_item_->ins_size_; |
| 589 | cu_->num_regs = current_code_item_->registers_size_ - cu_->num_ins; |
| 590 | cu_->num_outs = current_code_item_->outs_size_; |
| 591 | cu_->num_dalvik_registers = current_code_item_->registers_size_; |
| 592 | cu_->insns = current_code_item_->insns_; |
| 593 | cu_->code_item = current_code_item_; |
| 594 | } else { |
| 595 | UNIMPLEMENTED(FATAL) << "Nested inlining not implemented."; |
| 596 | /* |
| 597 | * Will need to manage storage for ins & outs, push prevous state and update |
| 598 | * insert point. |
| 599 | */ |
| 600 | } |
| 601 | |
| 602 | /* Current block to record parsed instructions */ |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 603 | BasicBlock *cur_block = NewMemBB(kDalvikByteCode, num_blocks_++); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 604 | DCHECK_EQ(current_offset_, 0U); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 605 | cur_block->start_offset = current_offset_; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 606 | block_list_.Insert(cur_block); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 607 | // TODO: for inlining support, insert at the insert point rather than entry block. |
| 608 | entry_block_->fall_through = cur_block->id; |
| 609 | cur_block->predecessors->Insert(entry_block_->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 610 | |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 611 | /* Identify code range in try blocks and set up the empty catch blocks */ |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 612 | ProcessTryCatchBlocks(); |
| 613 | |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 614 | uint64_t merged_df_flags = 0u; |
| 615 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 616 | /* Parse all instructions and put them into containing basic blocks */ |
| 617 | while (code_ptr < code_end) { |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 618 | MIR *insn = static_cast<MIR *>(arena_->Alloc(sizeof(MIR), kArenaAllocMIR)); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 619 | insn->offset = current_offset_; |
| 620 | insn->m_unit_index = current_method_; |
| 621 | int width = ParseInsn(code_ptr, &insn->dalvikInsn); |
| 622 | insn->width = width; |
| 623 | Instruction::Code opcode = insn->dalvikInsn.opcode; |
| 624 | if (opcode_count_ != NULL) { |
| 625 | opcode_count_[static_cast<int>(opcode)]++; |
| 626 | } |
| 627 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 628 | int flags = Instruction::FlagsOf(insn->dalvikInsn.opcode); |
buzbee | b1f1d64 | 2014-02-27 12:55:32 -0800 | [diff] [blame] | 629 | int verify_flags = Instruction::VerifyFlagsOf(insn->dalvikInsn.opcode); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 630 | |
Jean Christophe Beyler | cc794c3 | 2014-05-02 09:34:13 -0700 | [diff] [blame] | 631 | uint64_t df_flags = GetDataFlowAttributes(insn); |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 632 | merged_df_flags |= df_flags; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 633 | |
| 634 | if (df_flags & DF_HAS_DEFS) { |
| 635 | def_count_ += (df_flags & DF_A_WIDE) ? 2 : 1; |
| 636 | } |
| 637 | |
buzbee | 1da1e2f | 2013-11-15 13:37:01 -0800 | [diff] [blame] | 638 | if (df_flags & DF_LVN) { |
| 639 | cur_block->use_lvn = true; // Run local value numbering on this basic block. |
| 640 | } |
| 641 | |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 642 | // Check for inline data block signatures |
| 643 | if (opcode == Instruction::NOP) { |
| 644 | // A simple NOP will have a width of 1 at this point, embedded data NOP > 1. |
| 645 | if ((width == 1) && ((current_offset_ & 0x1) == 0x1) && ((code_end - code_ptr) > 1)) { |
| 646 | // Could be an aligning nop. If an embedded data NOP follows, treat pair as single unit. |
| 647 | uint16_t following_raw_instruction = code_ptr[1]; |
| 648 | if ((following_raw_instruction == Instruction::kSparseSwitchSignature) || |
| 649 | (following_raw_instruction == Instruction::kPackedSwitchSignature) || |
| 650 | (following_raw_instruction == Instruction::kArrayDataSignature)) { |
| 651 | width += Instruction::At(code_ptr + 1)->SizeInCodeUnits(); |
| 652 | } |
| 653 | } |
| 654 | if (width == 1) { |
| 655 | // It is a simple nop - treat normally. |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 656 | cur_block->AppendMIR(insn); |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 657 | } else { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 658 | DCHECK(cur_block->fall_through == NullBasicBlockId); |
| 659 | DCHECK(cur_block->taken == NullBasicBlockId); |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 660 | // Unreachable instruction, mark for no continuation. |
| 661 | flags &= ~Instruction::kContinue; |
| 662 | } |
| 663 | } else { |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 664 | cur_block->AppendMIR(insn); |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 665 | } |
| 666 | |
buzbee | b48819d | 2013-09-14 16:15:25 -0700 | [diff] [blame] | 667 | // Associate the starting dex_pc for this opcode with its containing basic block. |
| 668 | dex_pc_to_block_map_.Put(insn->offset, cur_block->id); |
| 669 | |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 670 | code_ptr += width; |
| 671 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 672 | if (flags & Instruction::kBranch) { |
| 673 | cur_block = ProcessCanBranch(cur_block, insn, current_offset_, |
| 674 | width, flags, code_ptr, code_end); |
| 675 | } else if (flags & Instruction::kReturn) { |
| 676 | cur_block->terminated_by_return = true; |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 677 | cur_block->fall_through = exit_block_->id; |
| 678 | exit_block_->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 679 | /* |
| 680 | * Terminate the current block if there are instructions |
| 681 | * afterwards. |
| 682 | */ |
| 683 | if (code_ptr < code_end) { |
| 684 | /* |
| 685 | * Create a fallthrough block for real instructions |
| 686 | * (incl. NOP). |
| 687 | */ |
buzbee | 2724776 | 2013-07-28 12:03:58 -0700 | [diff] [blame] | 688 | FindBlock(current_offset_ + width, /* split */ false, /* create */ true, |
| 689 | /* immed_pred_block_p */ NULL); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 690 | } |
| 691 | } else if (flags & Instruction::kThrow) { |
| 692 | cur_block = ProcessCanThrow(cur_block, insn, current_offset_, width, flags, try_block_addr_, |
| 693 | code_ptr, code_end); |
| 694 | } else if (flags & Instruction::kSwitch) { |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 695 | cur_block = ProcessCanSwitch(cur_block, insn, current_offset_, width, flags); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 696 | } |
buzbee | b1f1d64 | 2014-02-27 12:55:32 -0800 | [diff] [blame] | 697 | if (verify_flags & Instruction::kVerifyVarArgRange) { |
| 698 | /* |
| 699 | * The Quick backend's runtime model includes a gap between a method's |
| 700 | * argument ("in") vregs and the rest of its vregs. Handling a range instruction |
| 701 | * which spans the gap is somewhat complicated, and should not happen |
| 702 | * in normal usage of dx. Punt to the interpreter. |
| 703 | */ |
| 704 | int first_reg_in_range = insn->dalvikInsn.vC; |
| 705 | int last_reg_in_range = first_reg_in_range + insn->dalvikInsn.vA - 1; |
| 706 | if (IsInVReg(first_reg_in_range) != IsInVReg(last_reg_in_range)) { |
| 707 | punt_to_interpreter_ = true; |
| 708 | } |
| 709 | } |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 710 | current_offset_ += width; |
| 711 | BasicBlock *next_block = FindBlock(current_offset_, /* split */ false, /* create */ |
| 712 | false, /* immed_pred_block_p */ NULL); |
| 713 | if (next_block) { |
| 714 | /* |
| 715 | * The next instruction could be the target of a previously parsed |
| 716 | * forward branch so a block is already created. If the current |
| 717 | * instruction is not an unconditional branch, connect them through |
| 718 | * the fall-through link. |
| 719 | */ |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 720 | DCHECK(cur_block->fall_through == NullBasicBlockId || |
| 721 | GetBasicBlock(cur_block->fall_through) == next_block || |
| 722 | GetBasicBlock(cur_block->fall_through) == exit_block_); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 723 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 724 | if ((cur_block->fall_through == NullBasicBlockId) && (flags & Instruction::kContinue)) { |
| 725 | cur_block->fall_through = next_block->id; |
| 726 | next_block->predecessors->Insert(cur_block->id); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 727 | } |
| 728 | cur_block = next_block; |
| 729 | } |
| 730 | } |
Vladimir Marko | 3d73ba2 | 2014-03-06 15:18:04 +0000 | [diff] [blame] | 731 | merged_df_flags_ = merged_df_flags; |
Vladimir Marko | 5816ed4 | 2013-11-27 17:04:20 +0000 | [diff] [blame] | 732 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 733 | if (cu_->enable_debug & (1 << kDebugDumpCFG)) { |
| 734 | DumpCFG("/sdcard/1_post_parse_cfg/", true); |
| 735 | } |
| 736 | |
| 737 | if (cu_->verbose) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 738 | DumpMIRGraph(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 739 | } |
| 740 | } |
| 741 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 742 | void MIRGraph::ShowOpcodeStats() { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 743 | DCHECK(opcode_count_ != NULL); |
| 744 | LOG(INFO) << "Opcode Count"; |
| 745 | for (int i = 0; i < kNumPackedOpcodes; i++) { |
| 746 | if (opcode_count_[i] != 0) { |
| 747 | LOG(INFO) << "-C- " << Instruction::Name(static_cast<Instruction::Code>(i)) |
| 748 | << " " << opcode_count_[i]; |
| 749 | } |
| 750 | } |
| 751 | } |
| 752 | |
Jean Christophe Beyler | cc794c3 | 2014-05-02 09:34:13 -0700 | [diff] [blame] | 753 | uint64_t MIRGraph::GetDataFlowAttributes(Instruction::Code opcode) { |
| 754 | DCHECK_LT((size_t) opcode, (sizeof(oat_data_flow_attributes_) / sizeof(oat_data_flow_attributes_[0]))); |
| 755 | return oat_data_flow_attributes_[opcode]; |
| 756 | } |
| 757 | |
| 758 | uint64_t MIRGraph::GetDataFlowAttributes(MIR* mir) { |
| 759 | DCHECK(mir != nullptr); |
| 760 | Instruction::Code opcode = mir->dalvikInsn.opcode; |
| 761 | return GetDataFlowAttributes(opcode); |
| 762 | } |
| 763 | |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 764 | // TODO: use a configurable base prefix, and adjust callers to supply pass name. |
| 765 | /* Dump the CFG into a DOT graph */ |
Jean Christophe Beyler | d0a5155 | 2014-01-10 14:18:31 -0800 | [diff] [blame] | 766 | void MIRGraph::DumpCFG(const char* dir_prefix, bool all_blocks, const char *suffix) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 767 | FILE* file; |
| 768 | std::string fname(PrettyMethod(cu_->method_idx, *cu_->dex_file)); |
| 769 | ReplaceSpecialChars(fname); |
Jean Christophe Beyler | d0a5155 | 2014-01-10 14:18:31 -0800 | [diff] [blame] | 770 | fname = StringPrintf("%s%s%x%s.dot", dir_prefix, fname.c_str(), |
| 771 | GetBasicBlock(GetEntryBlock()->fall_through)->start_offset, |
| 772 | suffix == nullptr ? "" : suffix); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 773 | file = fopen(fname.c_str(), "w"); |
| 774 | if (file == NULL) { |
| 775 | return; |
| 776 | } |
| 777 | fprintf(file, "digraph G {\n"); |
| 778 | |
| 779 | fprintf(file, " rankdir=TB\n"); |
| 780 | |
| 781 | int num_blocks = all_blocks ? GetNumBlocks() : num_reachable_blocks_; |
| 782 | int idx; |
| 783 | |
| 784 | for (idx = 0; idx < num_blocks; idx++) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 785 | int block_idx = all_blocks ? idx : dfs_order_->Get(idx); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 786 | BasicBlock *bb = GetBasicBlock(block_idx); |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 787 | if (bb == NULL) continue; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 788 | if (bb->block_type == kDead) continue; |
| 789 | if (bb->block_type == kEntryBlock) { |
| 790 | fprintf(file, " entry_%d [shape=Mdiamond];\n", bb->id); |
| 791 | } else if (bb->block_type == kExitBlock) { |
| 792 | fprintf(file, " exit_%d [shape=Mdiamond];\n", bb->id); |
| 793 | } else if (bb->block_type == kDalvikByteCode) { |
| 794 | fprintf(file, " block%04x_%d [shape=record,label = \"{ \\\n", |
| 795 | bb->start_offset, bb->id); |
| 796 | const MIR *mir; |
| 797 | fprintf(file, " {block id %d\\l}%s\\\n", bb->id, |
| 798 | bb->first_mir_insn ? " | " : " "); |
| 799 | for (mir = bb->first_mir_insn; mir; mir = mir->next) { |
| 800 | int opcode = mir->dalvikInsn.opcode; |
| 801 | fprintf(file, " {%04x %s %s %s\\l}%s\\\n", mir->offset, |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 802 | mir->ssa_rep ? GetDalvikDisassembly(mir) : |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 803 | (opcode < kMirOpFirst) ? Instruction::Name(mir->dalvikInsn.opcode) : |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 804 | extended_mir_op_names_[opcode - kMirOpFirst], |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 805 | (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0 ? " no_rangecheck" : " ", |
| 806 | (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0 ? " no_nullcheck" : " ", |
| 807 | mir->next ? " | " : " "); |
| 808 | } |
| 809 | fprintf(file, " }\"];\n\n"); |
| 810 | } else if (bb->block_type == kExceptionHandling) { |
| 811 | char block_name[BLOCK_NAME_LEN]; |
| 812 | |
| 813 | GetBlockName(bb, block_name); |
| 814 | fprintf(file, " %s [shape=invhouse];\n", block_name); |
| 815 | } |
| 816 | |
| 817 | char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN]; |
| 818 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 819 | if (bb->taken != NullBasicBlockId) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 820 | GetBlockName(bb, block_name1); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 821 | GetBlockName(GetBasicBlock(bb->taken), block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 822 | fprintf(file, " %s:s -> %s:n [style=dotted]\n", |
| 823 | block_name1, block_name2); |
| 824 | } |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 825 | if (bb->fall_through != NullBasicBlockId) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 826 | GetBlockName(bb, block_name1); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 827 | GetBlockName(GetBasicBlock(bb->fall_through), block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 828 | fprintf(file, " %s:s -> %s:n\n", block_name1, block_name2); |
| 829 | } |
| 830 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 831 | if (bb->successor_block_list_type != kNotUsed) { |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 832 | fprintf(file, " succ%04x_%d [shape=%s,label = \"{ \\\n", |
| 833 | bb->start_offset, bb->id, |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 834 | (bb->successor_block_list_type == kCatch) ? "Mrecord" : "record"); |
| 835 | GrowableArray<SuccessorBlockInfo*>::Iterator iterator(bb->successor_blocks); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 836 | SuccessorBlockInfo *successor_block_info = iterator.Next(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 837 | |
| 838 | int succ_id = 0; |
| 839 | while (true) { |
| 840 | if (successor_block_info == NULL) break; |
| 841 | |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 842 | BasicBlock *dest_block = GetBasicBlock(successor_block_info->block); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 843 | SuccessorBlockInfo *next_successor_block_info = iterator.Next(); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 844 | |
| 845 | fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n", |
| 846 | succ_id++, |
| 847 | successor_block_info->key, |
| 848 | dest_block->start_offset, |
| 849 | (next_successor_block_info != NULL) ? " | " : " "); |
| 850 | |
| 851 | successor_block_info = next_successor_block_info; |
| 852 | } |
| 853 | fprintf(file, " }\"];\n\n"); |
| 854 | |
| 855 | GetBlockName(bb, block_name1); |
| 856 | fprintf(file, " %s:s -> succ%04x_%d:n [style=dashed]\n", |
| 857 | block_name1, bb->start_offset, bb->id); |
| 858 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 859 | // Link the successor pseudo-block with all of its potential targets. |
| 860 | GrowableArray<SuccessorBlockInfo*>::Iterator iter(bb->successor_blocks); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 861 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 862 | succ_id = 0; |
| 863 | while (true) { |
| 864 | SuccessorBlockInfo *successor_block_info = iter.Next(); |
| 865 | if (successor_block_info == NULL) break; |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 866 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 867 | BasicBlock* dest_block = GetBasicBlock(successor_block_info->block); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 868 | |
Razvan A Lupusoru | 25bc279 | 2014-03-19 14:27:59 -0700 | [diff] [blame] | 869 | GetBlockName(dest_block, block_name2); |
| 870 | fprintf(file, " succ%04x_%d:f%d:e -> %s:n\n", bb->start_offset, |
| 871 | bb->id, succ_id++, block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 872 | } |
| 873 | } |
| 874 | fprintf(file, "\n"); |
| 875 | |
| 876 | if (cu_->verbose) { |
| 877 | /* Display the dominator tree */ |
| 878 | GetBlockName(bb, block_name1); |
| 879 | fprintf(file, " cfg%s [label=\"%s\", shape=none];\n", |
| 880 | block_name1, block_name1); |
| 881 | if (bb->i_dom) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 882 | GetBlockName(GetBasicBlock(bb->i_dom), block_name2); |
buzbee | 311ca16 | 2013-02-28 15:56:43 -0800 | [diff] [blame] | 883 | fprintf(file, " cfg%s:s -> cfg%s:n\n\n", block_name2, block_name1); |
| 884 | } |
| 885 | } |
| 886 | } |
| 887 | fprintf(file, "}\n"); |
| 888 | fclose(file); |
| 889 | } |
| 890 | |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 891 | /* Insert an MIR instruction to the end of a basic block */ |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 892 | void BasicBlock::AppendMIR(MIR* mir) { |
| 893 | if (first_mir_insn == nullptr) { |
| 894 | DCHECK(last_mir_insn == nullptr); |
| 895 | last_mir_insn = first_mir_insn = mir; |
| 896 | mir->next = nullptr; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 897 | } else { |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 898 | last_mir_insn->next = mir; |
| 899 | mir->next = nullptr; |
| 900 | last_mir_insn = mir; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 901 | } |
| 902 | } |
| 903 | |
| 904 | /* Insert an MIR instruction to the head of a basic block */ |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 905 | void BasicBlock::PrependMIR(MIR* mir) { |
| 906 | if (first_mir_insn == nullptr) { |
| 907 | DCHECK(last_mir_insn == nullptr); |
| 908 | last_mir_insn = first_mir_insn = mir; |
| 909 | mir->next = nullptr; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 910 | } else { |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 911 | mir->next = first_mir_insn; |
| 912 | first_mir_insn = mir; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 913 | } |
| 914 | } |
| 915 | |
| 916 | /* Insert a MIR instruction after the specified MIR */ |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 917 | void BasicBlock::InsertMIRAfter(MIR* current_mir, MIR* new_mir) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 918 | new_mir->next = current_mir->next; |
| 919 | current_mir->next = new_mir; |
| 920 | |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 921 | if (last_mir_insn == current_mir) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 922 | /* Is the last MIR in the block */ |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 923 | last_mir_insn = new_mir; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 924 | } |
| 925 | } |
| 926 | |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 927 | MIR* BasicBlock::GetNextUnconditionalMir(MIRGraph* mir_graph, MIR* current) { |
Razvan A Lupusoru | 3bc0174 | 2014-02-06 13:18:43 -0800 | [diff] [blame] | 928 | MIR* next_mir = nullptr; |
| 929 | |
| 930 | if (current != nullptr) { |
| 931 | next_mir = current->next; |
| 932 | } |
| 933 | |
| 934 | if (next_mir == nullptr) { |
| 935 | // Only look for next MIR that follows unconditionally. |
Jean Christophe Beyler | cdacac4 | 2014-03-13 14:54:59 -0700 | [diff] [blame] | 936 | if ((taken == NullBasicBlockId) && (fall_through != NullBasicBlockId)) { |
| 937 | next_mir = mir_graph->GetBasicBlock(fall_through)->first_mir_insn; |
Razvan A Lupusoru | 3bc0174 | 2014-02-06 13:18:43 -0800 | [diff] [blame] | 938 | } |
| 939 | } |
| 940 | |
| 941 | return next_mir; |
| 942 | } |
| 943 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 944 | char* MIRGraph::GetDalvikDisassembly(const MIR* mir) { |
Ian Rogers | 29a2648 | 2014-05-02 15:27:29 -0700 | [diff] [blame] | 945 | MIR::DecodedInstruction insn = mir->dalvikInsn; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 946 | std::string str; |
| 947 | int flags = 0; |
| 948 | int opcode = insn.opcode; |
| 949 | char* ret; |
| 950 | bool nop = false; |
| 951 | SSARepresentation* ssa_rep = mir->ssa_rep; |
| 952 | Instruction::Format dalvik_format = Instruction::k10x; // Default to no-operand format |
| 953 | int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0; |
| 954 | int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0; |
| 955 | |
| 956 | // Handle special cases. |
| 957 | if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) { |
| 958 | str.append(extended_mir_op_names_[opcode - kMirOpFirst]); |
| 959 | str.append(": "); |
| 960 | // Recover the original Dex instruction |
| 961 | insn = mir->meta.throw_insn->dalvikInsn; |
| 962 | ssa_rep = mir->meta.throw_insn->ssa_rep; |
| 963 | defs = ssa_rep->num_defs; |
| 964 | uses = ssa_rep->num_uses; |
| 965 | opcode = insn.opcode; |
| 966 | } else if (opcode == kMirOpNop) { |
| 967 | str.append("["); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 968 | // Recover original opcode. |
| 969 | insn.opcode = Instruction::At(current_code_item_->insns_ + mir->offset)->Opcode(); |
| 970 | opcode = insn.opcode; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 971 | nop = true; |
| 972 | } |
| 973 | |
| 974 | if (opcode >= kMirOpFirst) { |
| 975 | str.append(extended_mir_op_names_[opcode - kMirOpFirst]); |
| 976 | } else { |
| 977 | dalvik_format = Instruction::FormatOf(insn.opcode); |
| 978 | flags = Instruction::FlagsOf(insn.opcode); |
| 979 | str.append(Instruction::Name(insn.opcode)); |
| 980 | } |
| 981 | |
| 982 | if (opcode == kMirOpPhi) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 983 | BasicBlockId* incoming = mir->meta.phi_incoming; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 984 | str.append(StringPrintf(" %s = (%s", |
| 985 | GetSSANameWithConst(ssa_rep->defs[0], true).c_str(), |
| 986 | GetSSANameWithConst(ssa_rep->uses[0], true).c_str())); |
Brian Carlstrom | b1eba21 | 2013-07-17 18:07:19 -0700 | [diff] [blame] | 987 | str.append(StringPrintf(":%d", incoming[0])); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 988 | int i; |
| 989 | for (i = 1; i < uses; i++) { |
| 990 | str.append(StringPrintf(", %s:%d", |
| 991 | GetSSANameWithConst(ssa_rep->uses[i], true).c_str(), |
| 992 | incoming[i])); |
| 993 | } |
| 994 | str.append(")"); |
| 995 | } else if ((flags & Instruction::kBranch) != 0) { |
| 996 | // For branches, decode the instructions to print out the branch targets. |
| 997 | int offset = 0; |
| 998 | switch (dalvik_format) { |
| 999 | case Instruction::k21t: |
| 1000 | str.append(StringPrintf(" %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str())); |
| 1001 | offset = insn.vB; |
| 1002 | break; |
| 1003 | case Instruction::k22t: |
| 1004 | str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(ssa_rep->uses[0], false).c_str(), |
| 1005 | GetSSANameWithConst(ssa_rep->uses[1], false).c_str())); |
| 1006 | offset = insn.vC; |
| 1007 | break; |
| 1008 | case Instruction::k10t: |
| 1009 | case Instruction::k20t: |
| 1010 | case Instruction::k30t: |
| 1011 | offset = insn.vA; |
| 1012 | break; |
| 1013 | default: |
| 1014 | LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode; |
| 1015 | } |
| 1016 | str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset, |
| 1017 | offset > 0 ? '+' : '-', offset > 0 ? offset : -offset)); |
| 1018 | } else { |
| 1019 | // For invokes-style formats, treat wide regs as a pair of singles |
| 1020 | bool show_singles = ((dalvik_format == Instruction::k35c) || |
| 1021 | (dalvik_format == Instruction::k3rc)); |
| 1022 | if (defs != 0) { |
| 1023 | str.append(StringPrintf(" %s", GetSSANameWithConst(ssa_rep->defs[0], false).c_str())); |
| 1024 | if (uses != 0) { |
| 1025 | str.append(", "); |
| 1026 | } |
| 1027 | } |
| 1028 | for (int i = 0; i < uses; i++) { |
| 1029 | str.append( |
| 1030 | StringPrintf(" %s", GetSSANameWithConst(ssa_rep->uses[i], show_singles).c_str())); |
| 1031 | if (!show_singles && (reg_location_ != NULL) && reg_location_[i].wide) { |
| 1032 | // For the listing, skip the high sreg. |
| 1033 | i++; |
| 1034 | } |
| 1035 | if (i != (uses -1)) { |
| 1036 | str.append(","); |
| 1037 | } |
| 1038 | } |
| 1039 | switch (dalvik_format) { |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 1040 | case Instruction::k11n: // Add one immediate from vB |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1041 | case Instruction::k21s: |
| 1042 | case Instruction::k31i: |
| 1043 | case Instruction::k21h: |
| 1044 | str.append(StringPrintf(", #%d", insn.vB)); |
| 1045 | break; |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 1046 | case Instruction::k51l: // Add one wide immediate |
Ian Rogers | 23b03b5 | 2014-01-24 11:10:03 -0800 | [diff] [blame] | 1047 | str.append(StringPrintf(", #%" PRId64, insn.vB_wide)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1048 | break; |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 1049 | case Instruction::k21c: // One register, one string/type/method index |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1050 | case Instruction::k31c: |
| 1051 | str.append(StringPrintf(", index #%d", insn.vB)); |
| 1052 | break; |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 1053 | case Instruction::k22c: // Two registers, one string/type/method index |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1054 | str.append(StringPrintf(", index #%d", insn.vC)); |
| 1055 | break; |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 1056 | case Instruction::k22s: // Add one immediate from vC |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1057 | case Instruction::k22b: |
| 1058 | str.append(StringPrintf(", #%d", insn.vC)); |
| 1059 | break; |
Brian Carlstrom | 02c8cc6 | 2013-07-18 15:54:44 -0700 | [diff] [blame] | 1060 | default: { |
| 1061 | // Nothing left to print |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1062 | } |
Brian Carlstrom | 02c8cc6 | 2013-07-18 15:54:44 -0700 | [diff] [blame] | 1063 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1064 | } |
| 1065 | if (nop) { |
| 1066 | str.append("]--optimized away"); |
| 1067 | } |
| 1068 | int length = str.length() + 1; |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1069 | ret = static_cast<char*>(arena_->Alloc(length, kArenaAllocDFInfo)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1070 | strncpy(ret, str.c_str(), length); |
| 1071 | return ret; |
| 1072 | } |
| 1073 | |
| 1074 | /* Turn method name into a legal Linux file name */ |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1075 | void MIRGraph::ReplaceSpecialChars(std::string& str) { |
Brian Carlstrom | 9b7085a | 2013-07-18 15:15:21 -0700 | [diff] [blame] | 1076 | static const struct { const char before; const char after; } match[] = { |
| 1077 | {'/', '-'}, {';', '#'}, {' ', '#'}, {'$', '+'}, |
| 1078 | {'(', '@'}, {')', '@'}, {'<', '='}, {'>', '='} |
| 1079 | }; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1080 | for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) { |
| 1081 | std::replace(str.begin(), str.end(), match[i].before, match[i].after); |
| 1082 | } |
| 1083 | } |
| 1084 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1085 | std::string MIRGraph::GetSSAName(int ssa_reg) { |
Ian Rogers | 39ebcb8 | 2013-05-30 16:57:23 -0700 | [diff] [blame] | 1086 | // TODO: This value is needed for LLVM and debugging. Currently, we compute this and then copy to |
| 1087 | // the arena. We should be smarter and just place straight into the arena, or compute the |
| 1088 | // value more lazily. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1089 | return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); |
| 1090 | } |
| 1091 | |
| 1092 | // 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] | 1093 | std::string MIRGraph::GetSSANameWithConst(int ssa_reg, bool singles_only) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1094 | if (reg_location_ == NULL) { |
| 1095 | // Pre-SSA - just use the standard name |
| 1096 | return GetSSAName(ssa_reg); |
| 1097 | } |
| 1098 | if (IsConst(reg_location_[ssa_reg])) { |
| 1099 | if (!singles_only && reg_location_[ssa_reg].wide) { |
Ian Rogers | 23b03b5 | 2014-01-24 11:10:03 -0800 | [diff] [blame] | 1100 | return StringPrintf("v%d_%d#0x%" PRIx64, SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1101 | ConstantValueWide(reg_location_[ssa_reg])); |
| 1102 | } else { |
Brian Carlstrom | b1eba21 | 2013-07-17 18:07:19 -0700 | [diff] [blame] | 1103 | return StringPrintf("v%d_%d#0x%x", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg), |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1104 | ConstantValue(reg_location_[ssa_reg])); |
| 1105 | } |
| 1106 | } else { |
| 1107 | return StringPrintf("v%d_%d", SRegToVReg(ssa_reg), GetSSASubscript(ssa_reg)); |
| 1108 | } |
| 1109 | } |
| 1110 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1111 | void MIRGraph::GetBlockName(BasicBlock* bb, char* name) { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1112 | switch (bb->block_type) { |
| 1113 | case kEntryBlock: |
| 1114 | snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id); |
| 1115 | break; |
| 1116 | case kExitBlock: |
| 1117 | snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id); |
| 1118 | break; |
| 1119 | case kDalvikByteCode: |
| 1120 | snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id); |
| 1121 | break; |
| 1122 | case kExceptionHandling: |
| 1123 | snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset, |
| 1124 | bb->id); |
| 1125 | break; |
| 1126 | default: |
| 1127 | snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id); |
| 1128 | break; |
| 1129 | } |
| 1130 | } |
| 1131 | |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1132 | const char* MIRGraph::GetShortyFromTargetIdx(int target_idx) { |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1133 | // TODO: for inlining support, use current code unit. |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1134 | const DexFile::MethodId& method_id = cu_->dex_file->GetMethodId(target_idx); |
| 1135 | return cu_->dex_file->GetShorty(method_id.proto_idx_); |
| 1136 | } |
| 1137 | |
| 1138 | /* Debug Utility - dump a compilation unit */ |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1139 | void MIRGraph::DumpMIRGraph() { |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1140 | BasicBlock* bb; |
| 1141 | const char* block_type_names[] = { |
buzbee | 17189ac | 2013-11-08 11:07:02 -0800 | [diff] [blame] | 1142 | "Null Block", |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1143 | "Entry Block", |
| 1144 | "Code Block", |
| 1145 | "Exit Block", |
| 1146 | "Exception Handling", |
| 1147 | "Catch Block" |
| 1148 | }; |
| 1149 | |
| 1150 | LOG(INFO) << "Compiling " << PrettyMethod(cu_->method_idx, *cu_->dex_file); |
| 1151 | LOG(INFO) << cu_->insns << " insns"; |
| 1152 | LOG(INFO) << GetNumBlocks() << " blocks in total"; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1153 | GrowableArray<BasicBlock*>::Iterator iterator(&block_list_); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1154 | |
| 1155 | while (true) { |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1156 | bb = iterator.Next(); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1157 | if (bb == NULL) break; |
| 1158 | LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)", |
| 1159 | bb->id, |
| 1160 | block_type_names[bb->block_type], |
| 1161 | bb->start_offset, |
| 1162 | bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset, |
| 1163 | bb->last_mir_insn ? "" : " empty"); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1164 | if (bb->taken != NullBasicBlockId) { |
| 1165 | LOG(INFO) << " Taken branch: block " << bb->taken |
| 1166 | << "(0x" << std::hex << GetBasicBlock(bb->taken)->start_offset << ")"; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1167 | } |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1168 | if (bb->fall_through != NullBasicBlockId) { |
| 1169 | LOG(INFO) << " Fallthrough : block " << bb->fall_through |
| 1170 | << " (0x" << std::hex << GetBasicBlock(bb->fall_through)->start_offset << ")"; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1171 | } |
| 1172 | } |
| 1173 | } |
| 1174 | |
| 1175 | /* |
| 1176 | * Build an array of location records for the incoming arguments. |
| 1177 | * Note: one location record per word of arguments, with dummy |
| 1178 | * high-word loc for wide arguments. Also pull up any following |
| 1179 | * MOVE_RESULT and incorporate it into the invoke. |
| 1180 | */ |
| 1181 | CallInfo* MIRGraph::NewMemCallInfo(BasicBlock* bb, MIR* mir, InvokeType type, |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1182 | bool is_range) { |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 1183 | CallInfo* info = static_cast<CallInfo*>(arena_->Alloc(sizeof(CallInfo), |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1184 | kArenaAllocMisc)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1185 | MIR* move_result_mir = FindMoveResult(bb, mir); |
| 1186 | if (move_result_mir == NULL) { |
| 1187 | info->result.location = kLocInvalid; |
| 1188 | } else { |
| 1189 | info->result = GetRawDest(move_result_mir); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1190 | move_result_mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop); |
| 1191 | } |
| 1192 | info->num_arg_words = mir->ssa_rep->num_uses; |
| 1193 | info->args = (info->num_arg_words == 0) ? NULL : static_cast<RegLocation*> |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1194 | (arena_->Alloc(sizeof(RegLocation) * info->num_arg_words, kArenaAllocMisc)); |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1195 | for (int i = 0; i < info->num_arg_words; i++) { |
| 1196 | info->args[i] = GetRawSrc(mir, i); |
| 1197 | } |
| 1198 | info->opt_flags = mir->optimization_flags; |
| 1199 | info->type = type; |
| 1200 | info->is_range = is_range; |
| 1201 | info->index = mir->dalvikInsn.vB; |
| 1202 | info->offset = mir->offset; |
Vladimir Marko | f096aad | 2014-01-23 15:51:58 +0000 | [diff] [blame] | 1203 | info->mir = mir; |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1204 | return info; |
| 1205 | } |
| 1206 | |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1207 | // Allocate a new basic block. |
Brian Carlstrom | 2ce745c | 2013-07-17 17:44:30 -0700 | [diff] [blame] | 1208 | BasicBlock* MIRGraph::NewMemBB(BBType block_type, int block_id) { |
Mathieu Chartier | f6c4b3b | 2013-08-24 16:11:37 -0700 | [diff] [blame] | 1209 | BasicBlock* bb = static_cast<BasicBlock*>(arena_->Alloc(sizeof(BasicBlock), |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1210 | kArenaAllocBB)); |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1211 | bb->block_type = block_type; |
| 1212 | bb->id = block_id; |
| 1213 | // TUNING: better estimate of the exit block predecessors? |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1214 | bb->predecessors = new (arena_) GrowableArray<BasicBlockId>(arena_, |
Brian Carlstrom | df62950 | 2013-07-17 22:39:56 -0700 | [diff] [blame] | 1215 | (block_type == kExitBlock) ? 2048 : 2, |
| 1216 | kGrowableArrayPredecessors); |
buzbee | 0d82948 | 2013-10-11 15:24:55 -0700 | [diff] [blame] | 1217 | bb->successor_block_list_type = kNotUsed; |
buzbee | 862a760 | 2013-04-05 10:58:54 -0700 | [diff] [blame] | 1218 | block_id_map_.Put(block_id, block_id); |
| 1219 | return bb; |
| 1220 | } |
buzbee | 1fd3346 | 2013-03-25 13:40:45 -0700 | [diff] [blame] | 1221 | |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1222 | void MIRGraph::InitializeConstantPropagation() { |
| 1223 | is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false); |
Vladimir Marko | 83cc7ae | 2014-02-12 18:02:05 +0000 | [diff] [blame] | 1224 | constant_values_ = static_cast<int*>(arena_->Alloc(sizeof(int) * GetNumSSARegs(), kArenaAllocDFInfo)); |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1225 | } |
| 1226 | |
| 1227 | void MIRGraph::InitializeMethodUses() { |
| 1228 | // The gate starts by initializing the use counts |
| 1229 | int num_ssa_regs = GetNumSSARegs(); |
| 1230 | use_counts_.Resize(num_ssa_regs + 32); |
| 1231 | raw_use_counts_.Resize(num_ssa_regs + 32); |
| 1232 | // Initialize list |
| 1233 | for (int i = 0; i < num_ssa_regs; i++) { |
| 1234 | use_counts_.Insert(0); |
| 1235 | raw_use_counts_.Insert(0); |
| 1236 | } |
| 1237 | } |
| 1238 | |
| 1239 | void MIRGraph::InitializeSSATransformation() { |
| 1240 | /* Compute the DFS order */ |
| 1241 | ComputeDFSOrders(); |
| 1242 | |
| 1243 | /* Compute the dominator info */ |
| 1244 | ComputeDominators(); |
| 1245 | |
| 1246 | /* Allocate data structures in preparation for SSA conversion */ |
| 1247 | CompilerInitializeSSAConversion(); |
| 1248 | |
| 1249 | /* Find out the "Dalvik reg def x block" relation */ |
| 1250 | ComputeDefBlockMatrix(); |
| 1251 | |
| 1252 | /* Insert phi nodes to dominance frontiers for all variables */ |
| 1253 | InsertPhiNodes(); |
| 1254 | |
| 1255 | /* Rename register names by local defs and phi nodes */ |
| 1256 | ClearAllVisitedFlags(); |
| 1257 | DoDFSPreOrderSSARename(GetEntryBlock()); |
Jean Christophe Beyler | 4e97c53 | 2014-01-07 10:07:18 -0800 | [diff] [blame] | 1258 | } |
| 1259 | |
Jean Christophe Beyler | f8c762b | 2014-05-02 12:54:37 -0700 | [diff] [blame] | 1260 | ChildBlockIterator::ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph) |
| 1261 | : basic_block_(bb), mir_graph_(mir_graph), visited_fallthrough_(false), |
| 1262 | visited_taken_(false), have_successors_(false) { |
| 1263 | // Check if we actually do have successors. |
| 1264 | if (basic_block_ != 0 && basic_block_->successor_block_list_type != kNotUsed) { |
| 1265 | have_successors_ = true; |
| 1266 | successor_iter_.Reset(basic_block_->successor_blocks); |
| 1267 | } |
| 1268 | } |
| 1269 | |
| 1270 | BasicBlock* ChildBlockIterator::Next() { |
| 1271 | // We check if we have a basic block. If we don't we cannot get next child. |
| 1272 | if (basic_block_ == nullptr) { |
| 1273 | return nullptr; |
| 1274 | } |
| 1275 | |
| 1276 | // If we haven't visited fallthrough, return that. |
| 1277 | if (visited_fallthrough_ == false) { |
| 1278 | visited_fallthrough_ = true; |
| 1279 | |
| 1280 | BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->fall_through); |
| 1281 | if (result != nullptr) { |
| 1282 | return result; |
| 1283 | } |
| 1284 | } |
| 1285 | |
| 1286 | // If we haven't visited taken, return that. |
| 1287 | if (visited_taken_ == false) { |
| 1288 | visited_taken_ = true; |
| 1289 | |
| 1290 | BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->taken); |
| 1291 | if (result != nullptr) { |
| 1292 | return result; |
| 1293 | } |
| 1294 | } |
| 1295 | |
| 1296 | // We visited both taken and fallthrough. Now check if we have successors we need to visit. |
| 1297 | if (have_successors_ == true) { |
| 1298 | // Get information about next successor block. |
| 1299 | SuccessorBlockInfo* successor_block_info = successor_iter_.Next(); |
| 1300 | |
| 1301 | // If we don't have anymore successors, return nullptr. |
| 1302 | if (successor_block_info != nullptr) { |
| 1303 | return mir_graph_->GetBasicBlock(successor_block_info->block); |
| 1304 | } |
| 1305 | } |
| 1306 | |
| 1307 | // We do not have anything. |
| 1308 | return nullptr; |
| 1309 | } |
| 1310 | |
Brian Carlstrom | 7934ac2 | 2013-07-26 10:54:15 -0700 | [diff] [blame] | 1311 | } // namespace art |