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