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