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