builder.cc revision 042fd00295d21f936ba7a8c16915ce678970e658 
1/*
2 * Copyright (C) 2014 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 "builder.h"
18
19#include "art_field-inl.h"
20#include "base/logging.h"
21#include "class_linker.h"
22#include "dex/verified_method.h"
23#include "dex_file-inl.h"
24#include "dex_instruction-inl.h"
25#include "dex/verified_method.h"
26#include "driver/compiler_driver-inl.h"
27#include "driver/compiler_options.h"
28#include "mirror/class_loader.h"
29#include "mirror/dex_cache.h"
30#include "nodes.h"
31#include "primitive.h"
32#include "scoped_thread_state_change.h"
33#include "thread.h"
34
35namespace art {
36
37/**
38 * Helper class to add HTemporary instructions. This class is used when
39 * converting a DEX instruction to multiple HInstruction, and where those
40 * instructions do not die at the following instruction, but instead spans
41 * multiple instructions.
42 */
43class Temporaries : public ValueObject {
44 public:
45  explicit Temporaries(HGraph* graph) : graph_(graph), index_(0) {}
46
47  void Add(HInstruction* instruction) {
48    HInstruction* temp = new (graph_->GetArena()) HTemporary(index_);
49    instruction->GetBlock()->AddInstruction(temp);
50
51    DCHECK(temp->GetPrevious() == instruction);
52
53    size_t offset;
54    if (instruction->GetType() == Primitive::kPrimLong
55        || instruction->GetType() == Primitive::kPrimDouble) {
56      offset = 2;
57    } else {
58      offset = 1;
59    }
60    index_ += offset;
61
62    graph_->UpdateTemporariesVRegSlots(index_);
63  }
64
65 private:
66  HGraph* const graph_;
67
68  // Current index in the temporary stack, updated by `Add`.
69  size_t index_;
70};
71
72class SwitchTable : public ValueObject {
73 public:
74  SwitchTable(const Instruction& instruction, uint32_t dex_pc, bool sparse)
75      : instruction_(instruction), dex_pc_(dex_pc), sparse_(sparse) {
76    int32_t table_offset = instruction.VRegB_31t();
77    const uint16_t* table = reinterpret_cast<const uint16_t*>(&instruction) + table_offset;
78    if (sparse) {
79      CHECK_EQ(table[0], static_cast<uint16_t>(Instruction::kSparseSwitchSignature));
80    } else {
81      CHECK_EQ(table[0], static_cast<uint16_t>(Instruction::kPackedSwitchSignature));
82    }
83    num_entries_ = table[1];
84    values_ = reinterpret_cast<const int32_t*>(&table[2]);
85  }
86
87  uint16_t GetNumEntries() const {
88    return num_entries_;
89  }
90
91  void CheckIndex(size_t index) const {
92    if (sparse_) {
93      // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order.
94      DCHECK_LT(index, 2 * static_cast<size_t>(num_entries_));
95    } else {
96      // In a packed table, we have the starting key and num_entries_ values.
97      DCHECK_LT(index, 1 + static_cast<size_t>(num_entries_));
98    }
99  }
100
101  int32_t GetEntryAt(size_t index) const {
102    CheckIndex(index);
103    return values_[index];
104  }
105
106  uint32_t GetDexPcForIndex(size_t index) const {
107    CheckIndex(index);
108    return dex_pc_ +
109        (reinterpret_cast<const int16_t*>(values_ + index) -
110         reinterpret_cast<const int16_t*>(&instruction_));
111  }
112
113  // Index of the first value in the table.
114  size_t GetFirstValueIndex() const {
115    if (sparse_) {
116      // In a sparse table, we have num_entries_ keys and num_entries_ values, in that order.
117      return num_entries_;
118    } else {
119      // In a packed table, we have the starting key and num_entries_ values.
120      return 1;
121    }
122  }
123
124 private:
125  const Instruction& instruction_;
126  const uint32_t dex_pc_;
127
128  // Whether this is a sparse-switch table (or a packed-switch one).
129  const bool sparse_;
130
131  // This can't be const as it needs to be computed off of the given instruction, and complicated
132  // expressions in the initializer list seemed very ugly.
133  uint16_t num_entries_;
134
135  const int32_t* values_;
136
137  DISALLOW_COPY_AND_ASSIGN(SwitchTable);
138};
139
140void HGraphBuilder::InitializeLocals(uint16_t count) {
141  graph_->SetNumberOfVRegs(count);
142  locals_.SetSize(count);
143  for (int i = 0; i < count; i++) {
144    HLocal* local = new (arena_) HLocal(i);
145    entry_block_->AddInstruction(local);
146    locals_.Put(i, local);
147  }
148}
149
150void HGraphBuilder::InitializeParameters(uint16_t number_of_parameters) {
151  // dex_compilation_unit_ is null only when unit testing.
152  if (dex_compilation_unit_ == nullptr) {
153    return;
154  }
155
156  graph_->SetNumberOfInVRegs(number_of_parameters);
157  const char* shorty = dex_compilation_unit_->GetShorty();
158  int locals_index = locals_.Size() - number_of_parameters;
159  int parameter_index = 0;
160
161  if (!dex_compilation_unit_->IsStatic()) {
162    // Add the implicit 'this' argument, not expressed in the signature.
163    HParameterValue* parameter =
164        new (arena_) HParameterValue(parameter_index++, Primitive::kPrimNot, true);
165    entry_block_->AddInstruction(parameter);
166    HLocal* local = GetLocalAt(locals_index++);
167    entry_block_->AddInstruction(new (arena_) HStoreLocal(local, parameter));
168    number_of_parameters--;
169  }
170
171  uint32_t pos = 1;
172  for (int i = 0; i < number_of_parameters; i++) {
173    HParameterValue* parameter =
174        new (arena_) HParameterValue(parameter_index++, Primitive::GetType(shorty[pos++]));
175    entry_block_->AddInstruction(parameter);
176    HLocal* local = GetLocalAt(locals_index++);
177    // Store the parameter value in the local that the dex code will use
178    // to reference that parameter.
179    entry_block_->AddInstruction(new (arena_) HStoreLocal(local, parameter));
180    bool is_wide = (parameter->GetType() == Primitive::kPrimLong)
181        || (parameter->GetType() == Primitive::kPrimDouble);
182    if (is_wide) {
183      i++;
184      locals_index++;
185      parameter_index++;
186    }
187  }
188}
189
190template<typename T>
191void HGraphBuilder::If_22t(const Instruction& instruction, uint32_t dex_pc) {
192  int32_t target_offset = instruction.GetTargetOffset();
193  HBasicBlock* branch_target = FindBlockStartingAt(dex_pc + target_offset);
194  HBasicBlock* fallthrough_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
195  DCHECK(branch_target != nullptr);
196  DCHECK(fallthrough_target != nullptr);
197  PotentiallyAddSuspendCheck(branch_target, dex_pc);
198  HInstruction* first = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
199  HInstruction* second = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
200  T* comparison = new (arena_) T(first, second);
201  current_block_->AddInstruction(comparison);
202  HInstruction* ifinst = new (arena_) HIf(comparison);
203  current_block_->AddInstruction(ifinst);
204  current_block_->AddSuccessor(branch_target);
205  current_block_->AddSuccessor(fallthrough_target);
206  current_block_ = nullptr;
207}
208
209template<typename T>
210void HGraphBuilder::If_21t(const Instruction& instruction, uint32_t dex_pc) {
211  int32_t target_offset = instruction.GetTargetOffset();
212  HBasicBlock* branch_target = FindBlockStartingAt(dex_pc + target_offset);
213  HBasicBlock* fallthrough_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
214  DCHECK(branch_target != nullptr);
215  DCHECK(fallthrough_target != nullptr);
216  PotentiallyAddSuspendCheck(branch_target, dex_pc);
217  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
218  T* comparison = new (arena_) T(value, graph_->GetIntConstant(0));
219  current_block_->AddInstruction(comparison);
220  HInstruction* ifinst = new (arena_) HIf(comparison);
221  current_block_->AddInstruction(ifinst);
222  current_block_->AddSuccessor(branch_target);
223  current_block_->AddSuccessor(fallthrough_target);
224  current_block_ = nullptr;
225}
226
227void HGraphBuilder::MaybeRecordStat(MethodCompilationStat compilation_stat) {
228  if (compilation_stats_ != nullptr) {
229    compilation_stats_->RecordStat(compilation_stat);
230  }
231}
232
233bool HGraphBuilder::SkipCompilation(const DexFile::CodeItem& code_item,
234                                    size_t number_of_branches) {
235  const CompilerOptions& compiler_options = compiler_driver_->GetCompilerOptions();
236  CompilerOptions::CompilerFilter compiler_filter = compiler_options.GetCompilerFilter();
237  if (compiler_filter == CompilerOptions::kEverything) {
238    return false;
239  }
240
241  if (compiler_options.IsHugeMethod(code_item.insns_size_in_code_units_)) {
242    VLOG(compiler) << "Skip compilation of huge method "
243                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
244                   << ": " << code_item.insns_size_in_code_units_ << " code units";
245    MaybeRecordStat(MethodCompilationStat::kNotCompiledHugeMethod);
246    return true;
247  }
248
249  // If it's large and contains no branches, it's likely to be machine generated initialization.
250  if (compiler_options.IsLargeMethod(code_item.insns_size_in_code_units_)
251      && (number_of_branches == 0)) {
252    VLOG(compiler) << "Skip compilation of large method with no branch "
253                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
254                   << ": " << code_item.insns_size_in_code_units_ << " code units";
255    MaybeRecordStat(MethodCompilationStat::kNotCompiledLargeMethodNoBranches);
256    return true;
257  }
258
259  return false;
260}
261
262bool HGraphBuilder::BuildGraph(const DexFile::CodeItem& code_item) {
263  DCHECK(graph_->GetBlocks().IsEmpty());
264
265  const uint16_t* code_ptr = code_item.insns_;
266  const uint16_t* code_end = code_item.insns_ + code_item.insns_size_in_code_units_;
267  code_start_ = code_ptr;
268
269  // Setup the graph with the entry block and exit block.
270  entry_block_ = new (arena_) HBasicBlock(graph_, 0);
271  graph_->AddBlock(entry_block_);
272  exit_block_ = new (arena_) HBasicBlock(graph_, kNoDexPc);
273  graph_->SetEntryBlock(entry_block_);
274  graph_->SetExitBlock(exit_block_);
275
276  InitializeLocals(code_item.registers_size_);
277  graph_->SetMaximumNumberOfOutVRegs(code_item.outs_size_);
278
279  // Compute the number of dex instructions, blocks, and branches. We will
280  // check these values against limits given to the compiler.
281  size_t number_of_branches = 0;
282
283  // To avoid splitting blocks, we compute ahead of time the instructions that
284  // start a new block, and create these blocks.
285  if (!ComputeBranchTargets(code_ptr, code_end, &number_of_branches)) {
286    MaybeRecordStat(MethodCompilationStat::kNotCompiledBranchOutsideMethodCode);
287    return false;
288  }
289
290  // Note that the compiler driver is null when unit testing.
291  if ((compiler_driver_ != nullptr) && SkipCompilation(code_item, number_of_branches)) {
292    return false;
293  }
294
295  // Also create blocks for catch handlers.
296  if (code_item.tries_size_ != 0) {
297    const uint8_t* handlers_ptr = DexFile::GetCatchHandlerData(code_item, 0);
298    uint32_t handlers_size = DecodeUnsignedLeb128(&handlers_ptr);
299    for (uint32_t idx = 0; idx < handlers_size; ++idx) {
300      CatchHandlerIterator iterator(handlers_ptr);
301      for (; iterator.HasNext(); iterator.Next()) {
302        uint32_t address = iterator.GetHandlerAddress();
303        HBasicBlock* block = FindBlockStartingAt(address);
304        if (block == nullptr) {
305          block = new (arena_) HBasicBlock(graph_, address);
306          branch_targets_.Put(address, block);
307        }
308        block->SetIsCatchBlock();
309      }
310      handlers_ptr = iterator.EndDataPointer();
311    }
312  }
313
314  InitializeParameters(code_item.ins_size_);
315
316  size_t dex_pc = 0;
317  while (code_ptr < code_end) {
318    // Update the current block if dex_pc starts a new block.
319    MaybeUpdateCurrentBlock(dex_pc);
320    const Instruction& instruction = *Instruction::At(code_ptr);
321    if (!AnalyzeDexInstruction(instruction, dex_pc)) {
322      return false;
323    }
324    dex_pc += instruction.SizeInCodeUnits();
325    code_ptr += instruction.SizeInCodeUnits();
326  }
327
328  // Add the exit block at the end to give it the highest id.
329  graph_->AddBlock(exit_block_);
330  exit_block_->AddInstruction(new (arena_) HExit());
331  // Add the suspend check to the entry block.
332  entry_block_->AddInstruction(new (arena_) HSuspendCheck(0));
333  entry_block_->AddInstruction(new (arena_) HGoto());
334
335  return true;
336}
337
338void HGraphBuilder::MaybeUpdateCurrentBlock(size_t index) {
339  HBasicBlock* block = FindBlockStartingAt(index);
340  if (block == nullptr) {
341    return;
342  }
343
344  if (current_block_ != nullptr) {
345    // Branching instructions clear current_block, so we know
346    // the last instruction of the current block is not a branching
347    // instruction. We add an unconditional goto to the found block.
348    current_block_->AddInstruction(new (arena_) HGoto());
349    current_block_->AddSuccessor(block);
350  }
351  graph_->AddBlock(block);
352  current_block_ = block;
353}
354
355bool HGraphBuilder::ComputeBranchTargets(const uint16_t* code_ptr,
356                                         const uint16_t* code_end,
357                                         size_t* number_of_branches) {
358  branch_targets_.SetSize(code_end - code_ptr);
359
360  // Create the first block for the dex instructions, single successor of the entry block.
361  HBasicBlock* block = new (arena_) HBasicBlock(graph_, 0);
362  branch_targets_.Put(0, block);
363  entry_block_->AddSuccessor(block);
364
365  // Iterate over all instructions and find branching instructions. Create blocks for
366  // the locations these instructions branch to.
367  uint32_t dex_pc = 0;
368  while (code_ptr < code_end) {
369    const Instruction& instruction = *Instruction::At(code_ptr);
370    if (instruction.IsBranch()) {
371      (*number_of_branches)++;
372      int32_t target = instruction.GetTargetOffset() + dex_pc;
373      // Create a block for the target instruction.
374      if (FindBlockStartingAt(target) == nullptr) {
375        block = new (arena_) HBasicBlock(graph_, target);
376        branch_targets_.Put(target, block);
377      }
378      dex_pc += instruction.SizeInCodeUnits();
379      code_ptr += instruction.SizeInCodeUnits();
380
381      if (code_ptr >= code_end) {
382        if (instruction.CanFlowThrough()) {
383          // In the normal case we should never hit this but someone can artificially forge a dex
384          // file to fall-through out the method code. In this case we bail out compilation.
385          return false;
386        }
387      } else if (FindBlockStartingAt(dex_pc) == nullptr) {
388        block = new (arena_) HBasicBlock(graph_, dex_pc);
389        branch_targets_.Put(dex_pc, block);
390      }
391    } else if (instruction.IsSwitch()) {
392      SwitchTable table(instruction, dex_pc, instruction.Opcode() == Instruction::SPARSE_SWITCH);
393
394      uint16_t num_entries = table.GetNumEntries();
395
396      // In a packed-switch, the entry at index 0 is the starting key. In a sparse-switch, the
397      // entry at index 0 is the first key, and values are after *all* keys.
398      size_t offset = table.GetFirstValueIndex();
399
400      // Use a larger loop counter type to avoid overflow issues.
401      for (size_t i = 0; i < num_entries; ++i) {
402        // The target of the case.
403        uint32_t target = dex_pc + table.GetEntryAt(i + offset);
404        if (FindBlockStartingAt(target) == nullptr) {
405          block = new (arena_) HBasicBlock(graph_, target);
406          branch_targets_.Put(target, block);
407        }
408
409        // The next case gets its own block.
410        if (i < num_entries) {
411          block = new (arena_) HBasicBlock(graph_, target);
412          branch_targets_.Put(table.GetDexPcForIndex(i), block);
413        }
414      }
415
416      // Fall-through. Add a block if there is more code afterwards.
417      dex_pc += instruction.SizeInCodeUnits();
418      code_ptr += instruction.SizeInCodeUnits();
419      if (code_ptr >= code_end) {
420        // In the normal case we should never hit this but someone can artificially forge a dex
421        // file to fall-through out the method code. In this case we bail out compilation.
422        // (A switch can fall-through so we don't need to check CanFlowThrough().)
423        return false;
424      } else if (FindBlockStartingAt(dex_pc) == nullptr) {
425        block = new (arena_) HBasicBlock(graph_, dex_pc);
426        branch_targets_.Put(dex_pc, block);
427      }
428    } else {
429      code_ptr += instruction.SizeInCodeUnits();
430      dex_pc += instruction.SizeInCodeUnits();
431    }
432  }
433  return true;
434}
435
436HBasicBlock* HGraphBuilder::FindBlockStartingAt(int32_t index) const {
437  DCHECK_GE(index, 0);
438  return branch_targets_.Get(index);
439}
440
441template<typename T>
442void HGraphBuilder::Unop_12x(const Instruction& instruction, Primitive::Type type) {
443  HInstruction* first = LoadLocal(instruction.VRegB(), type);
444  current_block_->AddInstruction(new (arena_) T(type, first));
445  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
446}
447
448void HGraphBuilder::Conversion_12x(const Instruction& instruction,
449                                   Primitive::Type input_type,
450                                   Primitive::Type result_type,
451                                   uint32_t dex_pc) {
452  HInstruction* first = LoadLocal(instruction.VRegB(), input_type);
453  current_block_->AddInstruction(new (arena_) HTypeConversion(result_type, first, dex_pc));
454  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
455}
456
457template<typename T>
458void HGraphBuilder::Binop_23x(const Instruction& instruction, Primitive::Type type) {
459  HInstruction* first = LoadLocal(instruction.VRegB(), type);
460  HInstruction* second = LoadLocal(instruction.VRegC(), type);
461  current_block_->AddInstruction(new (arena_) T(type, first, second));
462  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
463}
464
465template<typename T>
466void HGraphBuilder::Binop_23x(const Instruction& instruction,
467                              Primitive::Type type,
468                              uint32_t dex_pc) {
469  HInstruction* first = LoadLocal(instruction.VRegB(), type);
470  HInstruction* second = LoadLocal(instruction.VRegC(), type);
471  current_block_->AddInstruction(new (arena_) T(type, first, second, dex_pc));
472  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
473}
474
475template<typename T>
476void HGraphBuilder::Binop_23x_shift(const Instruction& instruction,
477                                    Primitive::Type type) {
478  HInstruction* first = LoadLocal(instruction.VRegB(), type);
479  HInstruction* second = LoadLocal(instruction.VRegC(), Primitive::kPrimInt);
480  current_block_->AddInstruction(new (arena_) T(type, first, second));
481  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
482}
483
484void HGraphBuilder::Binop_23x_cmp(const Instruction& instruction,
485                                  Primitive::Type type,
486                                  HCompare::Bias bias) {
487  HInstruction* first = LoadLocal(instruction.VRegB(), type);
488  HInstruction* second = LoadLocal(instruction.VRegC(), type);
489  current_block_->AddInstruction(new (arena_) HCompare(type, first, second, bias));
490  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
491}
492
493template<typename T>
494void HGraphBuilder::Binop_12x(const Instruction& instruction, Primitive::Type type) {
495  HInstruction* first = LoadLocal(instruction.VRegA(), type);
496  HInstruction* second = LoadLocal(instruction.VRegB(), type);
497  current_block_->AddInstruction(new (arena_) T(type, first, second));
498  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
499}
500
501template<typename T>
502void HGraphBuilder::Binop_12x_shift(const Instruction& instruction, Primitive::Type type) {
503  HInstruction* first = LoadLocal(instruction.VRegA(), type);
504  HInstruction* second = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
505  current_block_->AddInstruction(new (arena_) T(type, first, second));
506  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
507}
508
509template<typename T>
510void HGraphBuilder::Binop_12x(const Instruction& instruction,
511                              Primitive::Type type,
512                              uint32_t dex_pc) {
513  HInstruction* first = LoadLocal(instruction.VRegA(), type);
514  HInstruction* second = LoadLocal(instruction.VRegB(), type);
515  current_block_->AddInstruction(new (arena_) T(type, first, second, dex_pc));
516  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
517}
518
519template<typename T>
520void HGraphBuilder::Binop_22s(const Instruction& instruction, bool reverse) {
521  HInstruction* first = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
522  HInstruction* second = graph_->GetIntConstant(instruction.VRegC_22s());
523  if (reverse) {
524    std::swap(first, second);
525  }
526  current_block_->AddInstruction(new (arena_) T(Primitive::kPrimInt, first, second));
527  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
528}
529
530template<typename T>
531void HGraphBuilder::Binop_22b(const Instruction& instruction, bool reverse) {
532  HInstruction* first = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
533  HInstruction* second = graph_->GetIntConstant(instruction.VRegC_22b());
534  if (reverse) {
535    std::swap(first, second);
536  }
537  current_block_->AddInstruction(new (arena_) T(Primitive::kPrimInt, first, second));
538  UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
539}
540
541static bool RequiresConstructorBarrier(const DexCompilationUnit* cu, const CompilerDriver& driver) {
542  // dex compilation unit is null only when unit testing.
543  if (cu == nullptr) {
544    return false;
545  }
546
547  Thread* self = Thread::Current();
548  return cu->IsConstructor()
549      && driver.RequiresConstructorBarrier(self, cu->GetDexFile(), cu->GetClassDefIndex());
550}
551
552void HGraphBuilder::BuildReturn(const Instruction& instruction, Primitive::Type type) {
553  if (type == Primitive::kPrimVoid) {
554    // Note that we might insert redundant barriers when inlining `super` calls.
555    // TODO: add a data flow analysis to get rid of duplicate barriers.
556    if (RequiresConstructorBarrier(dex_compilation_unit_, *compiler_driver_)) {
557      current_block_->AddInstruction(new (arena_) HMemoryBarrier(kStoreStore));
558    }
559    current_block_->AddInstruction(new (arena_) HReturnVoid());
560  } else {
561    HInstruction* value = LoadLocal(instruction.VRegA(), type);
562    current_block_->AddInstruction(new (arena_) HReturn(value));
563  }
564  current_block_->AddSuccessor(exit_block_);
565  current_block_ = nullptr;
566}
567
568bool HGraphBuilder::BuildInvoke(const Instruction& instruction,
569                                uint32_t dex_pc,
570                                uint32_t method_idx,
571                                uint32_t number_of_vreg_arguments,
572                                bool is_range,
573                                uint32_t* args,
574                                uint32_t register_index) {
575  Instruction::Code opcode = instruction.Opcode();
576  InvokeType invoke_type;
577  switch (opcode) {
578    case Instruction::INVOKE_STATIC:
579    case Instruction::INVOKE_STATIC_RANGE:
580      invoke_type = kStatic;
581      break;
582    case Instruction::INVOKE_DIRECT:
583    case Instruction::INVOKE_DIRECT_RANGE:
584      invoke_type = kDirect;
585      break;
586    case Instruction::INVOKE_VIRTUAL:
587    case Instruction::INVOKE_VIRTUAL_RANGE:
588      invoke_type = kVirtual;
589      break;
590    case Instruction::INVOKE_INTERFACE:
591    case Instruction::INVOKE_INTERFACE_RANGE:
592      invoke_type = kInterface;
593      break;
594    case Instruction::INVOKE_SUPER_RANGE:
595    case Instruction::INVOKE_SUPER:
596      invoke_type = kSuper;
597      break;
598    default:
599      LOG(FATAL) << "Unexpected invoke op: " << opcode;
600      return false;
601  }
602
603  const DexFile::MethodId& method_id = dex_file_->GetMethodId(method_idx);
604  const DexFile::ProtoId& proto_id = dex_file_->GetProtoId(method_id.proto_idx_);
605  const char* descriptor = dex_file_->StringDataByIdx(proto_id.shorty_idx_);
606  Primitive::Type return_type = Primitive::GetType(descriptor[0]);
607  bool is_instance_call = invoke_type != kStatic;
608  // Remove the return type from the 'proto'.
609  size_t number_of_arguments = strlen(descriptor) - 1;
610  if (is_instance_call) {
611    // One extra argument for 'this'.
612    ++number_of_arguments;
613  }
614
615  MethodReference target_method(dex_file_, method_idx);
616  uintptr_t direct_code;
617  uintptr_t direct_method;
618  int table_index;
619  InvokeType optimized_invoke_type = invoke_type;
620
621  if (!compiler_driver_->ComputeInvokeInfo(dex_compilation_unit_, dex_pc, true, true,
622                                           &optimized_invoke_type, &target_method, &table_index,
623                                           &direct_code, &direct_method)) {
624    VLOG(compiler) << "Did not compile "
625                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
626                   << " because a method call could not be resolved";
627    MaybeRecordStat(MethodCompilationStat::kNotCompiledUnresolvedMethod);
628    return false;
629  }
630  DCHECK(optimized_invoke_type != kSuper);
631
632  // By default, consider that the called method implicitly requires
633  // an initialization check of its declaring method.
634  HInvokeStaticOrDirect::ClinitCheckRequirement clinit_check_requirement =
635      HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit;
636  // Potential class initialization check, in the case of a static method call.
637  HClinitCheck* clinit_check = nullptr;
638  // Replace calls to String.<init> with StringFactory.
639  int32_t string_init_offset = 0;
640  bool is_string_init = compiler_driver_->IsStringInit(method_idx, dex_file_, &string_init_offset);
641  if (is_string_init) {
642    return_type = Primitive::kPrimNot;
643    is_instance_call = false;
644    number_of_arguments--;
645    invoke_type = kStatic;
646    optimized_invoke_type = kStatic;
647  }
648
649  HInvoke* invoke = nullptr;
650
651  if (optimized_invoke_type == kVirtual) {
652    invoke = new (arena_) HInvokeVirtual(
653        arena_, number_of_arguments, return_type, dex_pc, method_idx, table_index);
654  } else if (optimized_invoke_type == kInterface) {
655    invoke = new (arena_) HInvokeInterface(
656        arena_, number_of_arguments, return_type, dex_pc, method_idx, table_index);
657  } else {
658    DCHECK(optimized_invoke_type == kDirect || optimized_invoke_type == kStatic);
659    // Sharpening to kDirect only works if we compile PIC.
660    DCHECK((optimized_invoke_type == invoke_type) || (optimized_invoke_type != kDirect)
661           || compiler_driver_->GetCompilerOptions().GetCompilePic());
662    bool is_recursive =
663        (target_method.dex_method_index == dex_compilation_unit_->GetDexMethodIndex());
664    DCHECK(!is_recursive || (target_method.dex_file == dex_compilation_unit_->GetDexFile()));
665
666    if (optimized_invoke_type == kStatic && !is_string_init) {
667      ScopedObjectAccess soa(Thread::Current());
668      StackHandleScope<4> hs(soa.Self());
669      Handle<mirror::DexCache> dex_cache(hs.NewHandle(
670          dex_compilation_unit_->GetClassLinker()->FindDexCache(
671              *dex_compilation_unit_->GetDexFile())));
672      Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
673          soa.Decode<mirror::ClassLoader*>(dex_compilation_unit_->GetClassLoader())));
674      ArtMethod* resolved_method = compiler_driver_->ResolveMethod(
675          soa, dex_cache, class_loader, dex_compilation_unit_, method_idx, optimized_invoke_type);
676
677      if (resolved_method == nullptr) {
678        MaybeRecordStat(MethodCompilationStat::kNotCompiledUnresolvedMethod);
679        return false;
680      }
681
682      const DexFile& outer_dex_file = *outer_compilation_unit_->GetDexFile();
683      Handle<mirror::DexCache> outer_dex_cache(hs.NewHandle(
684          outer_compilation_unit_->GetClassLinker()->FindDexCache(outer_dex_file)));
685      Handle<mirror::Class> outer_class(hs.NewHandle(GetOutermostCompilingClass()));
686
687      // The index at which the method's class is stored in the DexCache's type array.
688      uint32_t storage_index = DexFile::kDexNoIndex;
689      bool is_outer_class = (resolved_method->GetDeclaringClass() == outer_class.Get());
690      if (is_outer_class) {
691        storage_index = outer_class->GetDexTypeIndex();
692      } else if (outer_dex_cache.Get() == dex_cache.Get()) {
693        // Get `storage_index` from IsClassOfStaticMethodAvailableToReferrer.
694        compiler_driver_->IsClassOfStaticMethodAvailableToReferrer(outer_dex_cache.Get(),
695                                                                   GetCompilingClass(),
696                                                                   resolved_method,
697                                                                   method_idx,
698                                                                   &storage_index);
699      }
700
701      if (!outer_class->IsInterface()
702          && outer_class->IsSubClass(resolved_method->GetDeclaringClass())) {
703        // If the outer class is the declaring class or a subclass
704        // of the declaring class, no class initialization is needed
705        // before the static method call.
706        // Note that in case of inlining, we do not need to add clinit checks
707        // to calls that satisfy this subclass check with any inlined methods. This
708        // will be detected by the optimization passes.
709        clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kNone;
710      } else if (storage_index != DexFile::kDexNoIndex) {
711        // If the method's class type index is available, check
712        // whether we should add an explicit class initialization
713        // check for its declaring class before the static method call.
714
715        // TODO: find out why this check is needed.
716        bool is_in_dex_cache = compiler_driver_->CanAssumeTypeIsPresentInDexCache(
717            *outer_compilation_unit_->GetDexFile(), storage_index);
718        bool is_initialized =
719            resolved_method->GetDeclaringClass()->IsInitialized() && is_in_dex_cache;
720
721        if (is_initialized) {
722          clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kNone;
723        } else {
724          clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit;
725          HLoadClass* load_class =
726              new (arena_) HLoadClass(storage_index, is_outer_class, dex_pc);
727          current_block_->AddInstruction(load_class);
728          clinit_check = new (arena_) HClinitCheck(load_class, dex_pc);
729          current_block_->AddInstruction(clinit_check);
730        }
731      }
732    }
733
734    invoke = new (arena_) HInvokeStaticOrDirect(
735        arena_, number_of_arguments, return_type, dex_pc, target_method.dex_method_index,
736        is_recursive, string_init_offset, invoke_type, optimized_invoke_type,
737        clinit_check_requirement);
738  }
739
740  size_t start_index = 0;
741  Temporaries temps(graph_);
742  if (is_instance_call) {
743    HInstruction* arg = LoadLocal(is_range ? register_index : args[0], Primitive::kPrimNot);
744    HNullCheck* null_check = new (arena_) HNullCheck(arg, dex_pc);
745    current_block_->AddInstruction(null_check);
746    temps.Add(null_check);
747    invoke->SetArgumentAt(0, null_check);
748    start_index = 1;
749  }
750
751  uint32_t descriptor_index = 1;  // Skip the return type.
752  uint32_t argument_index = start_index;
753  if (is_string_init) {
754    start_index = 1;
755  }
756  for (size_t i = start_index;
757       // Make sure we don't go over the expected arguments or over the number of
758       // dex registers given. If the instruction was seen as dead by the verifier,
759       // it hasn't been properly checked.
760       (i < number_of_vreg_arguments) && (argument_index < number_of_arguments);
761       i++, argument_index++) {
762    Primitive::Type type = Primitive::GetType(descriptor[descriptor_index++]);
763    bool is_wide = (type == Primitive::kPrimLong) || (type == Primitive::kPrimDouble);
764    if (!is_range
765        && is_wide
766        && ((i + 1 == number_of_vreg_arguments) || (args[i] + 1 != args[i + 1]))) {
767      // Longs and doubles should be in pairs, that is, sequential registers. The verifier should
768      // reject any class where this is violated. However, the verifier only does these checks
769      // on non trivially dead instructions, so we just bailout the compilation.
770      VLOG(compiler) << "Did not compile "
771                     << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
772                     << " because of non-sequential dex register pair in wide argument";
773      MaybeRecordStat(MethodCompilationStat::kNotCompiledMalformedOpcode);
774      return false;
775    }
776    HInstruction* arg = LoadLocal(is_range ? register_index + i : args[i], type);
777    invoke->SetArgumentAt(argument_index, arg);
778    if (is_wide) {
779      i++;
780    }
781  }
782
783  if (argument_index != number_of_arguments) {
784    VLOG(compiler) << "Did not compile "
785                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
786                   << " because of wrong number of arguments in invoke instruction";
787    MaybeRecordStat(MethodCompilationStat::kNotCompiledMalformedOpcode);
788    return false;
789  }
790
791  if (clinit_check_requirement == HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit) {
792    // Add the class initialization check as last input of `invoke`.
793    DCHECK(clinit_check != nullptr);
794    invoke->SetArgumentAt(argument_index, clinit_check);
795  }
796
797  current_block_->AddInstruction(invoke);
798  latest_result_ = invoke;
799
800  // Add move-result for StringFactory method.
801  if (is_string_init) {
802    uint32_t orig_this_reg = is_range ? register_index : args[0];
803    UpdateLocal(orig_this_reg, invoke);
804    const VerifiedMethod* verified_method =
805        compiler_driver_->GetVerifiedMethod(dex_file_, dex_compilation_unit_->GetDexMethodIndex());
806    if (verified_method == nullptr) {
807      LOG(WARNING) << "No verified method for method calling String.<init>: "
808                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_);
809      return false;
810    }
811    const SafeMap<uint32_t, std::set<uint32_t>>& string_init_map =
812        verified_method->GetStringInitPcRegMap();
813    auto map_it = string_init_map.find(dex_pc);
814    if (map_it != string_init_map.end()) {
815      std::set<uint32_t> reg_set = map_it->second;
816      for (auto set_it = reg_set.begin(); set_it != reg_set.end(); ++set_it) {
817        HInstruction* load_local = LoadLocal(orig_this_reg, Primitive::kPrimNot);
818        UpdateLocal(*set_it, load_local);
819      }
820    }
821  }
822  return true;
823}
824
825bool HGraphBuilder::BuildInstanceFieldAccess(const Instruction& instruction,
826                                             uint32_t dex_pc,
827                                             bool is_put) {
828  uint32_t source_or_dest_reg = instruction.VRegA_22c();
829  uint32_t obj_reg = instruction.VRegB_22c();
830  uint16_t field_index = instruction.VRegC_22c();
831
832  ScopedObjectAccess soa(Thread::Current());
833  ArtField* resolved_field =
834      compiler_driver_->ComputeInstanceFieldInfo(field_index, dex_compilation_unit_, is_put, soa);
835
836  if (resolved_field == nullptr) {
837    MaybeRecordStat(MethodCompilationStat::kNotCompiledUnresolvedField);
838    return false;
839  }
840
841  Primitive::Type field_type = resolved_field->GetTypeAsPrimitiveType();
842
843  HInstruction* object = LoadLocal(obj_reg, Primitive::kPrimNot);
844  current_block_->AddInstruction(new (arena_) HNullCheck(object, dex_pc));
845  if (is_put) {
846    Temporaries temps(graph_);
847    HInstruction* null_check = current_block_->GetLastInstruction();
848    // We need one temporary for the null check.
849    temps.Add(null_check);
850    HInstruction* value = LoadLocal(source_or_dest_reg, field_type);
851    current_block_->AddInstruction(new (arena_) HInstanceFieldSet(
852        null_check,
853        value,
854        field_type,
855        resolved_field->GetOffset(),
856        resolved_field->IsVolatile()));
857  } else {
858    current_block_->AddInstruction(new (arena_) HInstanceFieldGet(
859        current_block_->GetLastInstruction(),
860        field_type,
861        resolved_field->GetOffset(),
862        resolved_field->IsVolatile()));
863
864    UpdateLocal(source_or_dest_reg, current_block_->GetLastInstruction());
865  }
866  return true;
867}
868
869static mirror::Class* GetClassFrom(CompilerDriver* driver,
870                                   const DexCompilationUnit& compilation_unit) {
871  ScopedObjectAccess soa(Thread::Current());
872  StackHandleScope<2> hs(soa.Self());
873  const DexFile& dex_file = *compilation_unit.GetDexFile();
874  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
875      soa.Decode<mirror::ClassLoader*>(compilation_unit.GetClassLoader())));
876  Handle<mirror::DexCache> dex_cache(hs.NewHandle(
877      compilation_unit.GetClassLinker()->FindDexCache(dex_file)));
878
879  return driver->ResolveCompilingMethodsClass(soa, dex_cache, class_loader, &compilation_unit);
880}
881
882mirror::Class* HGraphBuilder::GetOutermostCompilingClass() const {
883  return GetClassFrom(compiler_driver_, *outer_compilation_unit_);
884}
885
886mirror::Class* HGraphBuilder::GetCompilingClass() const {
887  return GetClassFrom(compiler_driver_, *dex_compilation_unit_);
888}
889
890bool HGraphBuilder::IsOutermostCompilingClass(uint16_t type_index) const {
891  ScopedObjectAccess soa(Thread::Current());
892  StackHandleScope<4> hs(soa.Self());
893  Handle<mirror::DexCache> dex_cache(hs.NewHandle(
894      dex_compilation_unit_->GetClassLinker()->FindDexCache(*dex_compilation_unit_->GetDexFile())));
895  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
896      soa.Decode<mirror::ClassLoader*>(dex_compilation_unit_->GetClassLoader())));
897  Handle<mirror::Class> cls(hs.NewHandle(compiler_driver_->ResolveClass(
898      soa, dex_cache, class_loader, type_index, dex_compilation_unit_)));
899  Handle<mirror::Class> outer_class(hs.NewHandle(GetOutermostCompilingClass()));
900
901  return outer_class.Get() == cls.Get();
902}
903
904bool HGraphBuilder::BuildStaticFieldAccess(const Instruction& instruction,
905                                           uint32_t dex_pc,
906                                           bool is_put) {
907  uint32_t source_or_dest_reg = instruction.VRegA_21c();
908  uint16_t field_index = instruction.VRegB_21c();
909
910  ScopedObjectAccess soa(Thread::Current());
911  StackHandleScope<4> hs(soa.Self());
912  Handle<mirror::DexCache> dex_cache(hs.NewHandle(
913      dex_compilation_unit_->GetClassLinker()->FindDexCache(*dex_compilation_unit_->GetDexFile())));
914  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
915      soa.Decode<mirror::ClassLoader*>(dex_compilation_unit_->GetClassLoader())));
916  ArtField* resolved_field = compiler_driver_->ResolveField(
917      soa, dex_cache, class_loader, dex_compilation_unit_, field_index, true);
918
919  if (resolved_field == nullptr) {
920    MaybeRecordStat(MethodCompilationStat::kNotCompiledUnresolvedField);
921    return false;
922  }
923
924  const DexFile& outer_dex_file = *outer_compilation_unit_->GetDexFile();
925  Handle<mirror::DexCache> outer_dex_cache(hs.NewHandle(
926      outer_compilation_unit_->GetClassLinker()->FindDexCache(outer_dex_file)));
927  Handle<mirror::Class> outer_class(hs.NewHandle(GetOutermostCompilingClass()));
928
929  // The index at which the field's class is stored in the DexCache's type array.
930  uint32_t storage_index;
931  bool is_outer_class = (outer_class.Get() == resolved_field->GetDeclaringClass());
932  if (is_outer_class) {
933    storage_index = outer_class->GetDexTypeIndex();
934  } else if (outer_dex_cache.Get() != dex_cache.Get()) {
935    // The compiler driver cannot currently understand multiple dex caches involved. Just bailout.
936    return false;
937  } else {
938    std::pair<bool, bool> pair = compiler_driver_->IsFastStaticField(
939        outer_dex_cache.Get(),
940        GetCompilingClass(),
941        resolved_field,
942        field_index,
943        &storage_index);
944    bool can_easily_access = is_put ? pair.second : pair.first;
945    if (!can_easily_access) {
946      return false;
947    }
948  }
949
950  // TODO: find out why this check is needed.
951  bool is_in_dex_cache = compiler_driver_->CanAssumeTypeIsPresentInDexCache(
952      *outer_compilation_unit_->GetDexFile(), storage_index);
953  bool is_initialized = resolved_field->GetDeclaringClass()->IsInitialized() && is_in_dex_cache;
954
955  HLoadClass* constant = new (arena_) HLoadClass(storage_index, is_outer_class, dex_pc);
956  current_block_->AddInstruction(constant);
957
958  HInstruction* cls = constant;
959  if (!is_initialized && !is_outer_class) {
960    cls = new (arena_) HClinitCheck(constant, dex_pc);
961    current_block_->AddInstruction(cls);
962  }
963
964  Primitive::Type field_type = resolved_field->GetTypeAsPrimitiveType();
965  if (is_put) {
966    // We need to keep the class alive before loading the value.
967    Temporaries temps(graph_);
968    temps.Add(cls);
969    HInstruction* value = LoadLocal(source_or_dest_reg, field_type);
970    DCHECK_EQ(value->GetType(), field_type);
971    current_block_->AddInstruction(
972        new (arena_) HStaticFieldSet(cls, value, field_type, resolved_field->GetOffset(),
973            resolved_field->IsVolatile()));
974  } else {
975    current_block_->AddInstruction(
976        new (arena_) HStaticFieldGet(cls, field_type, resolved_field->GetOffset(),
977            resolved_field->IsVolatile()));
978    UpdateLocal(source_or_dest_reg, current_block_->GetLastInstruction());
979  }
980  return true;
981}
982
983void HGraphBuilder::BuildCheckedDivRem(uint16_t out_vreg,
984                                       uint16_t first_vreg,
985                                       int64_t second_vreg_or_constant,
986                                       uint32_t dex_pc,
987                                       Primitive::Type type,
988                                       bool second_is_constant,
989                                       bool isDiv) {
990  DCHECK(type == Primitive::kPrimInt || type == Primitive::kPrimLong);
991
992  HInstruction* first = LoadLocal(first_vreg, type);
993  HInstruction* second = nullptr;
994  if (second_is_constant) {
995    if (type == Primitive::kPrimInt) {
996      second = graph_->GetIntConstant(second_vreg_or_constant);
997    } else {
998      second = graph_->GetLongConstant(second_vreg_or_constant);
999    }
1000  } else {
1001    second = LoadLocal(second_vreg_or_constant, type);
1002  }
1003
1004  if (!second_is_constant
1005      || (type == Primitive::kPrimInt && second->AsIntConstant()->GetValue() == 0)
1006      || (type == Primitive::kPrimLong && second->AsLongConstant()->GetValue() == 0)) {
1007    second = new (arena_) HDivZeroCheck(second, dex_pc);
1008    Temporaries temps(graph_);
1009    current_block_->AddInstruction(second);
1010    temps.Add(current_block_->GetLastInstruction());
1011  }
1012
1013  if (isDiv) {
1014    current_block_->AddInstruction(new (arena_) HDiv(type, first, second, dex_pc));
1015  } else {
1016    current_block_->AddInstruction(new (arena_) HRem(type, first, second, dex_pc));
1017  }
1018  UpdateLocal(out_vreg, current_block_->GetLastInstruction());
1019}
1020
1021void HGraphBuilder::BuildArrayAccess(const Instruction& instruction,
1022                                     uint32_t dex_pc,
1023                                     bool is_put,
1024                                     Primitive::Type anticipated_type) {
1025  uint8_t source_or_dest_reg = instruction.VRegA_23x();
1026  uint8_t array_reg = instruction.VRegB_23x();
1027  uint8_t index_reg = instruction.VRegC_23x();
1028
1029  // We need one temporary for the null check, one for the index, and one for the length.
1030  Temporaries temps(graph_);
1031
1032  HInstruction* object = LoadLocal(array_reg, Primitive::kPrimNot);
1033  object = new (arena_) HNullCheck(object, dex_pc);
1034  current_block_->AddInstruction(object);
1035  temps.Add(object);
1036
1037  HInstruction* length = new (arena_) HArrayLength(object);
1038  current_block_->AddInstruction(length);
1039  temps.Add(length);
1040  HInstruction* index = LoadLocal(index_reg, Primitive::kPrimInt);
1041  index = new (arena_) HBoundsCheck(index, length, dex_pc);
1042  current_block_->AddInstruction(index);
1043  temps.Add(index);
1044  if (is_put) {
1045    HInstruction* value = LoadLocal(source_or_dest_reg, anticipated_type);
1046    // TODO: Insert a type check node if the type is Object.
1047    current_block_->AddInstruction(new (arena_) HArraySet(
1048        object, index, value, anticipated_type, dex_pc));
1049  } else {
1050    current_block_->AddInstruction(new (arena_) HArrayGet(object, index, anticipated_type));
1051    UpdateLocal(source_or_dest_reg, current_block_->GetLastInstruction());
1052  }
1053  graph_->SetHasBoundsChecks(true);
1054}
1055
1056void HGraphBuilder::BuildFilledNewArray(uint32_t dex_pc,
1057                                        uint32_t type_index,
1058                                        uint32_t number_of_vreg_arguments,
1059                                        bool is_range,
1060                                        uint32_t* args,
1061                                        uint32_t register_index) {
1062  HInstruction* length = graph_->GetIntConstant(number_of_vreg_arguments);
1063  QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
1064      ? kQuickAllocArrayWithAccessCheck
1065      : kQuickAllocArray;
1066  HInstruction* object = new (arena_) HNewArray(length, dex_pc, type_index, entrypoint);
1067  current_block_->AddInstruction(object);
1068
1069  const char* descriptor = dex_file_->StringByTypeIdx(type_index);
1070  DCHECK_EQ(descriptor[0], '[') << descriptor;
1071  char primitive = descriptor[1];
1072  DCHECK(primitive == 'I'
1073      || primitive == 'L'
1074      || primitive == '[') << descriptor;
1075  bool is_reference_array = (primitive == 'L') || (primitive == '[');
1076  Primitive::Type type = is_reference_array ? Primitive::kPrimNot : Primitive::kPrimInt;
1077
1078  Temporaries temps(graph_);
1079  temps.Add(object);
1080  for (size_t i = 0; i < number_of_vreg_arguments; ++i) {
1081    HInstruction* value = LoadLocal(is_range ? register_index + i : args[i], type);
1082    HInstruction* index = graph_->GetIntConstant(i);
1083    current_block_->AddInstruction(
1084        new (arena_) HArraySet(object, index, value, type, dex_pc));
1085  }
1086  latest_result_ = object;
1087}
1088
1089template <typename T>
1090void HGraphBuilder::BuildFillArrayData(HInstruction* object,
1091                                       const T* data,
1092                                       uint32_t element_count,
1093                                       Primitive::Type anticipated_type,
1094                                       uint32_t dex_pc) {
1095  for (uint32_t i = 0; i < element_count; ++i) {
1096    HInstruction* index = graph_->GetIntConstant(i);
1097    HInstruction* value = graph_->GetIntConstant(data[i]);
1098    current_block_->AddInstruction(new (arena_) HArraySet(
1099      object, index, value, anticipated_type, dex_pc));
1100  }
1101}
1102
1103void HGraphBuilder::BuildFillArrayData(const Instruction& instruction, uint32_t dex_pc) {
1104  Temporaries temps(graph_);
1105  HInstruction* array = LoadLocal(instruction.VRegA_31t(), Primitive::kPrimNot);
1106  HNullCheck* null_check = new (arena_) HNullCheck(array, dex_pc);
1107  current_block_->AddInstruction(null_check);
1108  temps.Add(null_check);
1109
1110  HInstruction* length = new (arena_) HArrayLength(null_check);
1111  current_block_->AddInstruction(length);
1112
1113  int32_t payload_offset = instruction.VRegB_31t() + dex_pc;
1114  const Instruction::ArrayDataPayload* payload =
1115      reinterpret_cast<const Instruction::ArrayDataPayload*>(code_start_ + payload_offset);
1116  const uint8_t* data = payload->data;
1117  uint32_t element_count = payload->element_count;
1118
1119  // Implementation of this DEX instruction seems to be that the bounds check is
1120  // done before doing any stores.
1121  HInstruction* last_index = graph_->GetIntConstant(payload->element_count - 1);
1122  current_block_->AddInstruction(new (arena_) HBoundsCheck(last_index, length, dex_pc));
1123
1124  switch (payload->element_width) {
1125    case 1:
1126      BuildFillArrayData(null_check,
1127                         reinterpret_cast<const int8_t*>(data),
1128                         element_count,
1129                         Primitive::kPrimByte,
1130                         dex_pc);
1131      break;
1132    case 2:
1133      BuildFillArrayData(null_check,
1134                         reinterpret_cast<const int16_t*>(data),
1135                         element_count,
1136                         Primitive::kPrimShort,
1137                         dex_pc);
1138      break;
1139    case 4:
1140      BuildFillArrayData(null_check,
1141                         reinterpret_cast<const int32_t*>(data),
1142                         element_count,
1143                         Primitive::kPrimInt,
1144                         dex_pc);
1145      break;
1146    case 8:
1147      BuildFillWideArrayData(null_check,
1148                             reinterpret_cast<const int64_t*>(data),
1149                             element_count,
1150                             dex_pc);
1151      break;
1152    default:
1153      LOG(FATAL) << "Unknown element width for " << payload->element_width;
1154  }
1155  graph_->SetHasBoundsChecks(true);
1156}
1157
1158void HGraphBuilder::BuildFillWideArrayData(HInstruction* object,
1159                                           const int64_t* data,
1160                                           uint32_t element_count,
1161                                           uint32_t dex_pc) {
1162  for (uint32_t i = 0; i < element_count; ++i) {
1163    HInstruction* index = graph_->GetIntConstant(i);
1164    HInstruction* value = graph_->GetLongConstant(data[i]);
1165    current_block_->AddInstruction(new (arena_) HArraySet(
1166      object, index, value, Primitive::kPrimLong, dex_pc));
1167  }
1168}
1169
1170bool HGraphBuilder::BuildTypeCheck(const Instruction& instruction,
1171                                   uint8_t destination,
1172                                   uint8_t reference,
1173                                   uint16_t type_index,
1174                                   uint32_t dex_pc) {
1175  bool type_known_final;
1176  bool type_known_abstract;
1177  // `CanAccessTypeWithoutChecks` will tell whether the method being
1178  // built is trying to access its own class, so that the generated
1179  // code can optimize for this case. However, the optimization does not
1180  // work for inlining, so we use `IsOutermostCompilingClass` instead.
1181  bool dont_use_is_referrers_class;
1182  bool can_access = compiler_driver_->CanAccessTypeWithoutChecks(
1183      dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index,
1184      &type_known_final, &type_known_abstract, &dont_use_is_referrers_class);
1185  if (!can_access) {
1186    MaybeRecordStat(MethodCompilationStat::kNotCompiledCantAccesType);
1187    return false;
1188  }
1189  HInstruction* object = LoadLocal(reference, Primitive::kPrimNot);
1190  HLoadClass* cls = new (arena_) HLoadClass(
1191      type_index, IsOutermostCompilingClass(type_index), dex_pc);
1192  current_block_->AddInstruction(cls);
1193  // The class needs a temporary before being used by the type check.
1194  Temporaries temps(graph_);
1195  temps.Add(cls);
1196  if (instruction.Opcode() == Instruction::INSTANCE_OF) {
1197    current_block_->AddInstruction(
1198        new (arena_) HInstanceOf(object, cls, type_known_final, dex_pc));
1199    UpdateLocal(destination, current_block_->GetLastInstruction());
1200  } else {
1201    DCHECK_EQ(instruction.Opcode(), Instruction::CHECK_CAST);
1202    current_block_->AddInstruction(
1203        new (arena_) HCheckCast(object, cls, type_known_final, dex_pc));
1204  }
1205  return true;
1206}
1207
1208bool HGraphBuilder::NeedsAccessCheck(uint32_t type_index) const {
1209  return !compiler_driver_->CanAccessInstantiableTypeWithoutChecks(
1210      dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index);
1211}
1212
1213void HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc) {
1214  // Verifier guarantees that the payload for PackedSwitch contains:
1215  //   (a) number of entries (may be zero)
1216  //   (b) first and lowest switch case value (entry 0, always present)
1217  //   (c) list of target pcs (entries 1 <= i <= N)
1218  SwitchTable table(instruction, dex_pc, false);
1219
1220  // Value to test against.
1221  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
1222
1223  // Retrieve number of entries.
1224  uint16_t num_entries = table.GetNumEntries();
1225  if (num_entries == 0) {
1226    return;
1227  }
1228
1229  // Chained cmp-and-branch, starting from starting_key.
1230  int32_t starting_key = table.GetEntryAt(0);
1231
1232  for (size_t i = 1; i <= num_entries; i++) {
1233    BuildSwitchCaseHelper(instruction, i, i == num_entries, table, value, starting_key + i - 1,
1234                          table.GetEntryAt(i), dex_pc);
1235  }
1236}
1237
1238void HGraphBuilder::BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc) {
1239  // Verifier guarantees that the payload for SparseSwitch contains:
1240  //   (a) number of entries (may be zero)
1241  //   (b) sorted key values (entries 0 <= i < N)
1242  //   (c) target pcs corresponding to the switch values (entries N <= i < 2*N)
1243  SwitchTable table(instruction, dex_pc, true);
1244
1245  // Value to test against.
1246  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
1247
1248  uint16_t num_entries = table.GetNumEntries();
1249
1250  for (size_t i = 0; i < num_entries; i++) {
1251    BuildSwitchCaseHelper(instruction, i, i == static_cast<size_t>(num_entries) - 1, table, value,
1252                          table.GetEntryAt(i), table.GetEntryAt(i + num_entries), dex_pc);
1253  }
1254}
1255
1256void HGraphBuilder::BuildSwitchCaseHelper(const Instruction& instruction, size_t index,
1257                                          bool is_last_case, const SwitchTable& table,
1258                                          HInstruction* value, int32_t case_value_int,
1259                                          int32_t target_offset, uint32_t dex_pc) {
1260  HBasicBlock* case_target = FindBlockStartingAt(dex_pc + target_offset);
1261  DCHECK(case_target != nullptr);
1262  PotentiallyAddSuspendCheck(case_target, dex_pc);
1263
1264  // The current case's value.
1265  HInstruction* this_case_value = graph_->GetIntConstant(case_value_int);
1266
1267  // Compare value and this_case_value.
1268  HEqual* comparison = new (arena_) HEqual(value, this_case_value);
1269  current_block_->AddInstruction(comparison);
1270  HInstruction* ifinst = new (arena_) HIf(comparison);
1271  current_block_->AddInstruction(ifinst);
1272
1273  // Case hit: use the target offset to determine where to go.
1274  current_block_->AddSuccessor(case_target);
1275
1276  // Case miss: go to the next case (or default fall-through).
1277  // When there is a next case, we use the block stored with the table offset representing this
1278  // case (that is where we registered them in ComputeBranchTargets).
1279  // When there is no next case, we use the following instruction.
1280  // TODO: Find a good way to peel the last iteration to avoid conditional, but still have re-use.
1281  if (!is_last_case) {
1282    HBasicBlock* next_case_target = FindBlockStartingAt(table.GetDexPcForIndex(index));
1283    DCHECK(next_case_target != nullptr);
1284    current_block_->AddSuccessor(next_case_target);
1285
1286    // Need to manually add the block, as there is no dex-pc transition for the cases.
1287    graph_->AddBlock(next_case_target);
1288
1289    current_block_ = next_case_target;
1290  } else {
1291    HBasicBlock* default_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
1292    DCHECK(default_target != nullptr);
1293    current_block_->AddSuccessor(default_target);
1294    current_block_ = nullptr;
1295  }
1296}
1297
1298void HGraphBuilder::PotentiallyAddSuspendCheck(HBasicBlock* target, uint32_t dex_pc) {
1299  int32_t target_offset = target->GetDexPc() - dex_pc;
1300  if (target_offset <= 0) {
1301    // DX generates back edges to the first encountered return. We can save
1302    // time of later passes by not adding redundant suspend checks.
1303    HInstruction* last_in_target = target->GetLastInstruction();
1304    if (last_in_target != nullptr &&
1305        (last_in_target->IsReturn() || last_in_target->IsReturnVoid())) {
1306      return;
1307    }
1308
1309    // Add a suspend check to backward branches which may potentially loop. We
1310    // can remove them after we recognize loops in the graph.
1311    current_block_->AddInstruction(new (arena_) HSuspendCheck(dex_pc));
1312  }
1313}
1314
1315bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_pc) {
1316  if (current_block_ == nullptr) {
1317    return true;  // Dead code
1318  }
1319
1320  switch (instruction.Opcode()) {
1321    case Instruction::CONST_4: {
1322      int32_t register_index = instruction.VRegA();
1323      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_11n());
1324      UpdateLocal(register_index, constant);
1325      break;
1326    }
1327
1328    case Instruction::CONST_16: {
1329      int32_t register_index = instruction.VRegA();
1330      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_21s());
1331      UpdateLocal(register_index, constant);
1332      break;
1333    }
1334
1335    case Instruction::CONST: {
1336      int32_t register_index = instruction.VRegA();
1337      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_31i());
1338      UpdateLocal(register_index, constant);
1339      break;
1340    }
1341
1342    case Instruction::CONST_HIGH16: {
1343      int32_t register_index = instruction.VRegA();
1344      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_21h() << 16);
1345      UpdateLocal(register_index, constant);
1346      break;
1347    }
1348
1349    case Instruction::CONST_WIDE_16: {
1350      int32_t register_index = instruction.VRegA();
1351      // Get 16 bits of constant value, sign extended to 64 bits.
1352      int64_t value = instruction.VRegB_21s();
1353      value <<= 48;
1354      value >>= 48;
1355      HLongConstant* constant = graph_->GetLongConstant(value);
1356      UpdateLocal(register_index, constant);
1357      break;
1358    }
1359
1360    case Instruction::CONST_WIDE_32: {
1361      int32_t register_index = instruction.VRegA();
1362      // Get 32 bits of constant value, sign extended to 64 bits.
1363      int64_t value = instruction.VRegB_31i();
1364      value <<= 32;
1365      value >>= 32;
1366      HLongConstant* constant = graph_->GetLongConstant(value);
1367      UpdateLocal(register_index, constant);
1368      break;
1369    }
1370
1371    case Instruction::CONST_WIDE: {
1372      int32_t register_index = instruction.VRegA();
1373      HLongConstant* constant = graph_->GetLongConstant(instruction.VRegB_51l());
1374      UpdateLocal(register_index, constant);
1375      break;
1376    }
1377
1378    case Instruction::CONST_WIDE_HIGH16: {
1379      int32_t register_index = instruction.VRegA();
1380      int64_t value = static_cast<int64_t>(instruction.VRegB_21h()) << 48;
1381      HLongConstant* constant = graph_->GetLongConstant(value);
1382      UpdateLocal(register_index, constant);
1383      break;
1384    }
1385
1386    // Note that the SSA building will refine the types.
1387    case Instruction::MOVE:
1388    case Instruction::MOVE_FROM16:
1389    case Instruction::MOVE_16: {
1390      HInstruction* value = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
1391      UpdateLocal(instruction.VRegA(), value);
1392      break;
1393    }
1394
1395    // Note that the SSA building will refine the types.
1396    case Instruction::MOVE_WIDE:
1397    case Instruction::MOVE_WIDE_FROM16:
1398    case Instruction::MOVE_WIDE_16: {
1399      HInstruction* value = LoadLocal(instruction.VRegB(), Primitive::kPrimLong);
1400      UpdateLocal(instruction.VRegA(), value);
1401      break;
1402    }
1403
1404    case Instruction::MOVE_OBJECT:
1405    case Instruction::MOVE_OBJECT_16:
1406    case Instruction::MOVE_OBJECT_FROM16: {
1407      HInstruction* value = LoadLocal(instruction.VRegB(), Primitive::kPrimNot);
1408      UpdateLocal(instruction.VRegA(), value);
1409      break;
1410    }
1411
1412    case Instruction::RETURN_VOID: {
1413      BuildReturn(instruction, Primitive::kPrimVoid);
1414      break;
1415    }
1416
1417#define IF_XX(comparison, cond) \
1418    case Instruction::IF_##cond: If_22t<comparison>(instruction, dex_pc); break; \
1419    case Instruction::IF_##cond##Z: If_21t<comparison>(instruction, dex_pc); break
1420
1421    IF_XX(HEqual, EQ);
1422    IF_XX(HNotEqual, NE);
1423    IF_XX(HLessThan, LT);
1424    IF_XX(HLessThanOrEqual, LE);
1425    IF_XX(HGreaterThan, GT);
1426    IF_XX(HGreaterThanOrEqual, GE);
1427
1428    case Instruction::GOTO:
1429    case Instruction::GOTO_16:
1430    case Instruction::GOTO_32: {
1431      int32_t offset = instruction.GetTargetOffset();
1432      HBasicBlock* target = FindBlockStartingAt(offset + dex_pc);
1433      DCHECK(target != nullptr);
1434      PotentiallyAddSuspendCheck(target, dex_pc);
1435      current_block_->AddInstruction(new (arena_) HGoto());
1436      current_block_->AddSuccessor(target);
1437      current_block_ = nullptr;
1438      break;
1439    }
1440
1441    case Instruction::RETURN: {
1442      BuildReturn(instruction, return_type_);
1443      break;
1444    }
1445
1446    case Instruction::RETURN_OBJECT: {
1447      BuildReturn(instruction, return_type_);
1448      break;
1449    }
1450
1451    case Instruction::RETURN_WIDE: {
1452      BuildReturn(instruction, return_type_);
1453      break;
1454    }
1455
1456    case Instruction::INVOKE_DIRECT:
1457    case Instruction::INVOKE_INTERFACE:
1458    case Instruction::INVOKE_STATIC:
1459    case Instruction::INVOKE_SUPER:
1460    case Instruction::INVOKE_VIRTUAL: {
1461      uint32_t method_idx = instruction.VRegB_35c();
1462      uint32_t number_of_vreg_arguments = instruction.VRegA_35c();
1463      uint32_t args[5];
1464      instruction.GetVarArgs(args);
1465      if (!BuildInvoke(instruction, dex_pc, method_idx,
1466                       number_of_vreg_arguments, false, args, -1)) {
1467        return false;
1468      }
1469      break;
1470    }
1471
1472    case Instruction::INVOKE_DIRECT_RANGE:
1473    case Instruction::INVOKE_INTERFACE_RANGE:
1474    case Instruction::INVOKE_STATIC_RANGE:
1475    case Instruction::INVOKE_SUPER_RANGE:
1476    case Instruction::INVOKE_VIRTUAL_RANGE: {
1477      uint32_t method_idx = instruction.VRegB_3rc();
1478      uint32_t number_of_vreg_arguments = instruction.VRegA_3rc();
1479      uint32_t register_index = instruction.VRegC();
1480      if (!BuildInvoke(instruction, dex_pc, method_idx,
1481                       number_of_vreg_arguments, true, nullptr, register_index)) {
1482        return false;
1483      }
1484      break;
1485    }
1486
1487    case Instruction::NEG_INT: {
1488      Unop_12x<HNeg>(instruction, Primitive::kPrimInt);
1489      break;
1490    }
1491
1492    case Instruction::NEG_LONG: {
1493      Unop_12x<HNeg>(instruction, Primitive::kPrimLong);
1494      break;
1495    }
1496
1497    case Instruction::NEG_FLOAT: {
1498      Unop_12x<HNeg>(instruction, Primitive::kPrimFloat);
1499      break;
1500    }
1501
1502    case Instruction::NEG_DOUBLE: {
1503      Unop_12x<HNeg>(instruction, Primitive::kPrimDouble);
1504      break;
1505    }
1506
1507    case Instruction::NOT_INT: {
1508      Unop_12x<HNot>(instruction, Primitive::kPrimInt);
1509      break;
1510    }
1511
1512    case Instruction::NOT_LONG: {
1513      Unop_12x<HNot>(instruction, Primitive::kPrimLong);
1514      break;
1515    }
1516
1517    case Instruction::INT_TO_LONG: {
1518      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimLong, dex_pc);
1519      break;
1520    }
1521
1522    case Instruction::INT_TO_FLOAT: {
1523      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimFloat, dex_pc);
1524      break;
1525    }
1526
1527    case Instruction::INT_TO_DOUBLE: {
1528      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimDouble, dex_pc);
1529      break;
1530    }
1531
1532    case Instruction::LONG_TO_INT: {
1533      Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimInt, dex_pc);
1534      break;
1535    }
1536
1537    case Instruction::LONG_TO_FLOAT: {
1538      Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimFloat, dex_pc);
1539      break;
1540    }
1541
1542    case Instruction::LONG_TO_DOUBLE: {
1543      Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimDouble, dex_pc);
1544      break;
1545    }
1546
1547    case Instruction::FLOAT_TO_INT: {
1548      Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimInt, dex_pc);
1549      break;
1550    }
1551
1552    case Instruction::FLOAT_TO_LONG: {
1553      Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimLong, dex_pc);
1554      break;
1555    }
1556
1557    case Instruction::FLOAT_TO_DOUBLE: {
1558      Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimDouble, dex_pc);
1559      break;
1560    }
1561
1562    case Instruction::DOUBLE_TO_INT: {
1563      Conversion_12x(instruction, Primitive::kPrimDouble, Primitive::kPrimInt, dex_pc);
1564      break;
1565    }
1566
1567    case Instruction::DOUBLE_TO_LONG: {
1568      Conversion_12x(instruction, Primitive::kPrimDouble, Primitive::kPrimLong, dex_pc);
1569      break;
1570    }
1571
1572    case Instruction::DOUBLE_TO_FLOAT: {
1573      Conversion_12x(instruction, Primitive::kPrimDouble, Primitive::kPrimFloat, dex_pc);
1574      break;
1575    }
1576
1577    case Instruction::INT_TO_BYTE: {
1578      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimByte, dex_pc);
1579      break;
1580    }
1581
1582    case Instruction::INT_TO_SHORT: {
1583      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimShort, dex_pc);
1584      break;
1585    }
1586
1587    case Instruction::INT_TO_CHAR: {
1588      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimChar, dex_pc);
1589      break;
1590    }
1591
1592    case Instruction::ADD_INT: {
1593      Binop_23x<HAdd>(instruction, Primitive::kPrimInt);
1594      break;
1595    }
1596
1597    case Instruction::ADD_LONG: {
1598      Binop_23x<HAdd>(instruction, Primitive::kPrimLong);
1599      break;
1600    }
1601
1602    case Instruction::ADD_DOUBLE: {
1603      Binop_23x<HAdd>(instruction, Primitive::kPrimDouble);
1604      break;
1605    }
1606
1607    case Instruction::ADD_FLOAT: {
1608      Binop_23x<HAdd>(instruction, Primitive::kPrimFloat);
1609      break;
1610    }
1611
1612    case Instruction::SUB_INT: {
1613      Binop_23x<HSub>(instruction, Primitive::kPrimInt);
1614      break;
1615    }
1616
1617    case Instruction::SUB_LONG: {
1618      Binop_23x<HSub>(instruction, Primitive::kPrimLong);
1619      break;
1620    }
1621
1622    case Instruction::SUB_FLOAT: {
1623      Binop_23x<HSub>(instruction, Primitive::kPrimFloat);
1624      break;
1625    }
1626
1627    case Instruction::SUB_DOUBLE: {
1628      Binop_23x<HSub>(instruction, Primitive::kPrimDouble);
1629      break;
1630    }
1631
1632    case Instruction::ADD_INT_2ADDR: {
1633      Binop_12x<HAdd>(instruction, Primitive::kPrimInt);
1634      break;
1635    }
1636
1637    case Instruction::MUL_INT: {
1638      Binop_23x<HMul>(instruction, Primitive::kPrimInt);
1639      break;
1640    }
1641
1642    case Instruction::MUL_LONG: {
1643      Binop_23x<HMul>(instruction, Primitive::kPrimLong);
1644      break;
1645    }
1646
1647    case Instruction::MUL_FLOAT: {
1648      Binop_23x<HMul>(instruction, Primitive::kPrimFloat);
1649      break;
1650    }
1651
1652    case Instruction::MUL_DOUBLE: {
1653      Binop_23x<HMul>(instruction, Primitive::kPrimDouble);
1654      break;
1655    }
1656
1657    case Instruction::DIV_INT: {
1658      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1659                         dex_pc, Primitive::kPrimInt, false, true);
1660      break;
1661    }
1662
1663    case Instruction::DIV_LONG: {
1664      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1665                         dex_pc, Primitive::kPrimLong, false, true);
1666      break;
1667    }
1668
1669    case Instruction::DIV_FLOAT: {
1670      Binop_23x<HDiv>(instruction, Primitive::kPrimFloat, dex_pc);
1671      break;
1672    }
1673
1674    case Instruction::DIV_DOUBLE: {
1675      Binop_23x<HDiv>(instruction, Primitive::kPrimDouble, dex_pc);
1676      break;
1677    }
1678
1679    case Instruction::REM_INT: {
1680      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1681                         dex_pc, Primitive::kPrimInt, false, false);
1682      break;
1683    }
1684
1685    case Instruction::REM_LONG: {
1686      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1687                         dex_pc, Primitive::kPrimLong, false, false);
1688      break;
1689    }
1690
1691    case Instruction::REM_FLOAT: {
1692      Binop_23x<HRem>(instruction, Primitive::kPrimFloat, dex_pc);
1693      break;
1694    }
1695
1696    case Instruction::REM_DOUBLE: {
1697      Binop_23x<HRem>(instruction, Primitive::kPrimDouble, dex_pc);
1698      break;
1699    }
1700
1701    case Instruction::AND_INT: {
1702      Binop_23x<HAnd>(instruction, Primitive::kPrimInt);
1703      break;
1704    }
1705
1706    case Instruction::AND_LONG: {
1707      Binop_23x<HAnd>(instruction, Primitive::kPrimLong);
1708      break;
1709    }
1710
1711    case Instruction::SHL_INT: {
1712      Binop_23x_shift<HShl>(instruction, Primitive::kPrimInt);
1713      break;
1714    }
1715
1716    case Instruction::SHL_LONG: {
1717      Binop_23x_shift<HShl>(instruction, Primitive::kPrimLong);
1718      break;
1719    }
1720
1721    case Instruction::SHR_INT: {
1722      Binop_23x_shift<HShr>(instruction, Primitive::kPrimInt);
1723      break;
1724    }
1725
1726    case Instruction::SHR_LONG: {
1727      Binop_23x_shift<HShr>(instruction, Primitive::kPrimLong);
1728      break;
1729    }
1730
1731    case Instruction::USHR_INT: {
1732      Binop_23x_shift<HUShr>(instruction, Primitive::kPrimInt);
1733      break;
1734    }
1735
1736    case Instruction::USHR_LONG: {
1737      Binop_23x_shift<HUShr>(instruction, Primitive::kPrimLong);
1738      break;
1739    }
1740
1741    case Instruction::OR_INT: {
1742      Binop_23x<HOr>(instruction, Primitive::kPrimInt);
1743      break;
1744    }
1745
1746    case Instruction::OR_LONG: {
1747      Binop_23x<HOr>(instruction, Primitive::kPrimLong);
1748      break;
1749    }
1750
1751    case Instruction::XOR_INT: {
1752      Binop_23x<HXor>(instruction, Primitive::kPrimInt);
1753      break;
1754    }
1755
1756    case Instruction::XOR_LONG: {
1757      Binop_23x<HXor>(instruction, Primitive::kPrimLong);
1758      break;
1759    }
1760
1761    case Instruction::ADD_LONG_2ADDR: {
1762      Binop_12x<HAdd>(instruction, Primitive::kPrimLong);
1763      break;
1764    }
1765
1766    case Instruction::ADD_DOUBLE_2ADDR: {
1767      Binop_12x<HAdd>(instruction, Primitive::kPrimDouble);
1768      break;
1769    }
1770
1771    case Instruction::ADD_FLOAT_2ADDR: {
1772      Binop_12x<HAdd>(instruction, Primitive::kPrimFloat);
1773      break;
1774    }
1775
1776    case Instruction::SUB_INT_2ADDR: {
1777      Binop_12x<HSub>(instruction, Primitive::kPrimInt);
1778      break;
1779    }
1780
1781    case Instruction::SUB_LONG_2ADDR: {
1782      Binop_12x<HSub>(instruction, Primitive::kPrimLong);
1783      break;
1784    }
1785
1786    case Instruction::SUB_FLOAT_2ADDR: {
1787      Binop_12x<HSub>(instruction, Primitive::kPrimFloat);
1788      break;
1789    }
1790
1791    case Instruction::SUB_DOUBLE_2ADDR: {
1792      Binop_12x<HSub>(instruction, Primitive::kPrimDouble);
1793      break;
1794    }
1795
1796    case Instruction::MUL_INT_2ADDR: {
1797      Binop_12x<HMul>(instruction, Primitive::kPrimInt);
1798      break;
1799    }
1800
1801    case Instruction::MUL_LONG_2ADDR: {
1802      Binop_12x<HMul>(instruction, Primitive::kPrimLong);
1803      break;
1804    }
1805
1806    case Instruction::MUL_FLOAT_2ADDR: {
1807      Binop_12x<HMul>(instruction, Primitive::kPrimFloat);
1808      break;
1809    }
1810
1811    case Instruction::MUL_DOUBLE_2ADDR: {
1812      Binop_12x<HMul>(instruction, Primitive::kPrimDouble);
1813      break;
1814    }
1815
1816    case Instruction::DIV_INT_2ADDR: {
1817      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1818                         dex_pc, Primitive::kPrimInt, false, true);
1819      break;
1820    }
1821
1822    case Instruction::DIV_LONG_2ADDR: {
1823      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1824                         dex_pc, Primitive::kPrimLong, false, true);
1825      break;
1826    }
1827
1828    case Instruction::REM_INT_2ADDR: {
1829      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1830                         dex_pc, Primitive::kPrimInt, false, false);
1831      break;
1832    }
1833
1834    case Instruction::REM_LONG_2ADDR: {
1835      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1836                         dex_pc, Primitive::kPrimLong, false, false);
1837      break;
1838    }
1839
1840    case Instruction::REM_FLOAT_2ADDR: {
1841      Binop_12x<HRem>(instruction, Primitive::kPrimFloat, dex_pc);
1842      break;
1843    }
1844
1845    case Instruction::REM_DOUBLE_2ADDR: {
1846      Binop_12x<HRem>(instruction, Primitive::kPrimDouble, dex_pc);
1847      break;
1848    }
1849
1850    case Instruction::SHL_INT_2ADDR: {
1851      Binop_12x_shift<HShl>(instruction, Primitive::kPrimInt);
1852      break;
1853    }
1854
1855    case Instruction::SHL_LONG_2ADDR: {
1856      Binop_12x_shift<HShl>(instruction, Primitive::kPrimLong);
1857      break;
1858    }
1859
1860    case Instruction::SHR_INT_2ADDR: {
1861      Binop_12x_shift<HShr>(instruction, Primitive::kPrimInt);
1862      break;
1863    }
1864
1865    case Instruction::SHR_LONG_2ADDR: {
1866      Binop_12x_shift<HShr>(instruction, Primitive::kPrimLong);
1867      break;
1868    }
1869
1870    case Instruction::USHR_INT_2ADDR: {
1871      Binop_12x_shift<HUShr>(instruction, Primitive::kPrimInt);
1872      break;
1873    }
1874
1875    case Instruction::USHR_LONG_2ADDR: {
1876      Binop_12x_shift<HUShr>(instruction, Primitive::kPrimLong);
1877      break;
1878    }
1879
1880    case Instruction::DIV_FLOAT_2ADDR: {
1881      Binop_12x<HDiv>(instruction, Primitive::kPrimFloat, dex_pc);
1882      break;
1883    }
1884
1885    case Instruction::DIV_DOUBLE_2ADDR: {
1886      Binop_12x<HDiv>(instruction, Primitive::kPrimDouble, dex_pc);
1887      break;
1888    }
1889
1890    case Instruction::AND_INT_2ADDR: {
1891      Binop_12x<HAnd>(instruction, Primitive::kPrimInt);
1892      break;
1893    }
1894
1895    case Instruction::AND_LONG_2ADDR: {
1896      Binop_12x<HAnd>(instruction, Primitive::kPrimLong);
1897      break;
1898    }
1899
1900    case Instruction::OR_INT_2ADDR: {
1901      Binop_12x<HOr>(instruction, Primitive::kPrimInt);
1902      break;
1903    }
1904
1905    case Instruction::OR_LONG_2ADDR: {
1906      Binop_12x<HOr>(instruction, Primitive::kPrimLong);
1907      break;
1908    }
1909
1910    case Instruction::XOR_INT_2ADDR: {
1911      Binop_12x<HXor>(instruction, Primitive::kPrimInt);
1912      break;
1913    }
1914
1915    case Instruction::XOR_LONG_2ADDR: {
1916      Binop_12x<HXor>(instruction, Primitive::kPrimLong);
1917      break;
1918    }
1919
1920    case Instruction::ADD_INT_LIT16: {
1921      Binop_22s<HAdd>(instruction, false);
1922      break;
1923    }
1924
1925    case Instruction::AND_INT_LIT16: {
1926      Binop_22s<HAnd>(instruction, false);
1927      break;
1928    }
1929
1930    case Instruction::OR_INT_LIT16: {
1931      Binop_22s<HOr>(instruction, false);
1932      break;
1933    }
1934
1935    case Instruction::XOR_INT_LIT16: {
1936      Binop_22s<HXor>(instruction, false);
1937      break;
1938    }
1939
1940    case Instruction::RSUB_INT: {
1941      Binop_22s<HSub>(instruction, true);
1942      break;
1943    }
1944
1945    case Instruction::MUL_INT_LIT16: {
1946      Binop_22s<HMul>(instruction, false);
1947      break;
1948    }
1949
1950    case Instruction::ADD_INT_LIT8: {
1951      Binop_22b<HAdd>(instruction, false);
1952      break;
1953    }
1954
1955    case Instruction::AND_INT_LIT8: {
1956      Binop_22b<HAnd>(instruction, false);
1957      break;
1958    }
1959
1960    case Instruction::OR_INT_LIT8: {
1961      Binop_22b<HOr>(instruction, false);
1962      break;
1963    }
1964
1965    case Instruction::XOR_INT_LIT8: {
1966      Binop_22b<HXor>(instruction, false);
1967      break;
1968    }
1969
1970    case Instruction::RSUB_INT_LIT8: {
1971      Binop_22b<HSub>(instruction, true);
1972      break;
1973    }
1974
1975    case Instruction::MUL_INT_LIT8: {
1976      Binop_22b<HMul>(instruction, false);
1977      break;
1978    }
1979
1980    case Instruction::DIV_INT_LIT16:
1981    case Instruction::DIV_INT_LIT8: {
1982      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1983                         dex_pc, Primitive::kPrimInt, true, true);
1984      break;
1985    }
1986
1987    case Instruction::REM_INT_LIT16:
1988    case Instruction::REM_INT_LIT8: {
1989      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1990                         dex_pc, Primitive::kPrimInt, true, false);
1991      break;
1992    }
1993
1994    case Instruction::SHL_INT_LIT8: {
1995      Binop_22b<HShl>(instruction, false);
1996      break;
1997    }
1998
1999    case Instruction::SHR_INT_LIT8: {
2000      Binop_22b<HShr>(instruction, false);
2001      break;
2002    }
2003
2004    case Instruction::USHR_INT_LIT8: {
2005      Binop_22b<HUShr>(instruction, false);
2006      break;
2007    }
2008
2009    case Instruction::NEW_INSTANCE: {
2010      uint16_t type_index = instruction.VRegB_21c();
2011      if (compiler_driver_->IsStringTypeIndex(type_index, dex_file_)) {
2012        // Turn new-instance of string into a const 0.
2013        int32_t register_index = instruction.VRegA();
2014        HNullConstant* constant = graph_->GetNullConstant();
2015        UpdateLocal(register_index, constant);
2016      } else {
2017        QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
2018            ? kQuickAllocObjectWithAccessCheck
2019            : kQuickAllocObject;
2020
2021        current_block_->AddInstruction(new (arena_) HNewInstance(dex_pc, type_index, entrypoint));
2022        UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
2023      }
2024      break;
2025    }
2026
2027    case Instruction::NEW_ARRAY: {
2028      uint16_t type_index = instruction.VRegC_22c();
2029      HInstruction* length = LoadLocal(instruction.VRegB_22c(), Primitive::kPrimInt);
2030      QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
2031          ? kQuickAllocArrayWithAccessCheck
2032          : kQuickAllocArray;
2033      current_block_->AddInstruction(
2034          new (arena_) HNewArray(length, dex_pc, type_index, entrypoint));
2035      UpdateLocal(instruction.VRegA_22c(), current_block_->GetLastInstruction());
2036      break;
2037    }
2038
2039    case Instruction::FILLED_NEW_ARRAY: {
2040      uint32_t number_of_vreg_arguments = instruction.VRegA_35c();
2041      uint32_t type_index = instruction.VRegB_35c();
2042      uint32_t args[5];
2043      instruction.GetVarArgs(args);
2044      BuildFilledNewArray(dex_pc, type_index, number_of_vreg_arguments, false, args, 0);
2045      break;
2046    }
2047
2048    case Instruction::FILLED_NEW_ARRAY_RANGE: {
2049      uint32_t number_of_vreg_arguments = instruction.VRegA_3rc();
2050      uint32_t type_index = instruction.VRegB_3rc();
2051      uint32_t register_index = instruction.VRegC_3rc();
2052      BuildFilledNewArray(
2053          dex_pc, type_index, number_of_vreg_arguments, true, nullptr, register_index);
2054      break;
2055    }
2056
2057    case Instruction::FILL_ARRAY_DATA: {
2058      BuildFillArrayData(instruction, dex_pc);
2059      break;
2060    }
2061
2062    case Instruction::MOVE_RESULT:
2063    case Instruction::MOVE_RESULT_WIDE:
2064    case Instruction::MOVE_RESULT_OBJECT:
2065      UpdateLocal(instruction.VRegA(), latest_result_);
2066      latest_result_ = nullptr;
2067      break;
2068
2069    case Instruction::CMP_LONG: {
2070      Binop_23x_cmp(instruction, Primitive::kPrimLong, HCompare::kNoBias);
2071      break;
2072    }
2073
2074    case Instruction::CMPG_FLOAT: {
2075      Binop_23x_cmp(instruction, Primitive::kPrimFloat, HCompare::kGtBias);
2076      break;
2077    }
2078
2079    case Instruction::CMPG_DOUBLE: {
2080      Binop_23x_cmp(instruction, Primitive::kPrimDouble, HCompare::kGtBias);
2081      break;
2082    }
2083
2084    case Instruction::CMPL_FLOAT: {
2085      Binop_23x_cmp(instruction, Primitive::kPrimFloat, HCompare::kLtBias);
2086      break;
2087    }
2088
2089    case Instruction::CMPL_DOUBLE: {
2090      Binop_23x_cmp(instruction, Primitive::kPrimDouble, HCompare::kLtBias);
2091      break;
2092    }
2093
2094    case Instruction::NOP:
2095      break;
2096
2097    case Instruction::IGET:
2098    case Instruction::IGET_WIDE:
2099    case Instruction::IGET_OBJECT:
2100    case Instruction::IGET_BOOLEAN:
2101    case Instruction::IGET_BYTE:
2102    case Instruction::IGET_CHAR:
2103    case Instruction::IGET_SHORT: {
2104      if (!BuildInstanceFieldAccess(instruction, dex_pc, false)) {
2105        return false;
2106      }
2107      break;
2108    }
2109
2110    case Instruction::IPUT:
2111    case Instruction::IPUT_WIDE:
2112    case Instruction::IPUT_OBJECT:
2113    case Instruction::IPUT_BOOLEAN:
2114    case Instruction::IPUT_BYTE:
2115    case Instruction::IPUT_CHAR:
2116    case Instruction::IPUT_SHORT: {
2117      if (!BuildInstanceFieldAccess(instruction, dex_pc, true)) {
2118        return false;
2119      }
2120      break;
2121    }
2122
2123    case Instruction::SGET:
2124    case Instruction::SGET_WIDE:
2125    case Instruction::SGET_OBJECT:
2126    case Instruction::SGET_BOOLEAN:
2127    case Instruction::SGET_BYTE:
2128    case Instruction::SGET_CHAR:
2129    case Instruction::SGET_SHORT: {
2130      if (!BuildStaticFieldAccess(instruction, dex_pc, false)) {
2131        return false;
2132      }
2133      break;
2134    }
2135
2136    case Instruction::SPUT:
2137    case Instruction::SPUT_WIDE:
2138    case Instruction::SPUT_OBJECT:
2139    case Instruction::SPUT_BOOLEAN:
2140    case Instruction::SPUT_BYTE:
2141    case Instruction::SPUT_CHAR:
2142    case Instruction::SPUT_SHORT: {
2143      if (!BuildStaticFieldAccess(instruction, dex_pc, true)) {
2144        return false;
2145      }
2146      break;
2147    }
2148
2149#define ARRAY_XX(kind, anticipated_type)                                          \
2150    case Instruction::AGET##kind: {                                               \
2151      BuildArrayAccess(instruction, dex_pc, false, anticipated_type);         \
2152      break;                                                                      \
2153    }                                                                             \
2154    case Instruction::APUT##kind: {                                               \
2155      BuildArrayAccess(instruction, dex_pc, true, anticipated_type);          \
2156      break;                                                                      \
2157    }
2158
2159    ARRAY_XX(, Primitive::kPrimInt);
2160    ARRAY_XX(_WIDE, Primitive::kPrimLong);
2161    ARRAY_XX(_OBJECT, Primitive::kPrimNot);
2162    ARRAY_XX(_BOOLEAN, Primitive::kPrimBoolean);
2163    ARRAY_XX(_BYTE, Primitive::kPrimByte);
2164    ARRAY_XX(_CHAR, Primitive::kPrimChar);
2165    ARRAY_XX(_SHORT, Primitive::kPrimShort);
2166
2167    case Instruction::ARRAY_LENGTH: {
2168      HInstruction* object = LoadLocal(instruction.VRegB_12x(), Primitive::kPrimNot);
2169      // No need for a temporary for the null check, it is the only input of the following
2170      // instruction.
2171      object = new (arena_) HNullCheck(object, dex_pc);
2172      current_block_->AddInstruction(object);
2173      current_block_->AddInstruction(new (arena_) HArrayLength(object));
2174      UpdateLocal(instruction.VRegA_12x(), current_block_->GetLastInstruction());
2175      break;
2176    }
2177
2178    case Instruction::CONST_STRING: {
2179      current_block_->AddInstruction(new (arena_) HLoadString(instruction.VRegB_21c(), dex_pc));
2180      UpdateLocal(instruction.VRegA_21c(), current_block_->GetLastInstruction());
2181      break;
2182    }
2183
2184    case Instruction::CONST_STRING_JUMBO: {
2185      current_block_->AddInstruction(new (arena_) HLoadString(instruction.VRegB_31c(), dex_pc));
2186      UpdateLocal(instruction.VRegA_31c(), current_block_->GetLastInstruction());
2187      break;
2188    }
2189
2190    case Instruction::CONST_CLASS: {
2191      uint16_t type_index = instruction.VRegB_21c();
2192      bool type_known_final;
2193      bool type_known_abstract;
2194      bool dont_use_is_referrers_class;
2195      // `CanAccessTypeWithoutChecks` will tell whether the method being
2196      // built is trying to access its own class, so that the generated
2197      // code can optimize for this case. However, the optimization does not
2198      // work for inlining, so we use `IsOutermostCompilingClass` instead.
2199      bool can_access = compiler_driver_->CanAccessTypeWithoutChecks(
2200          dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index,
2201          &type_known_final, &type_known_abstract, &dont_use_is_referrers_class);
2202      if (!can_access) {
2203        MaybeRecordStat(MethodCompilationStat::kNotCompiledCantAccesType);
2204        return false;
2205      }
2206      current_block_->AddInstruction(
2207          new (arena_) HLoadClass(type_index, IsOutermostCompilingClass(type_index), dex_pc));
2208      UpdateLocal(instruction.VRegA_21c(), current_block_->GetLastInstruction());
2209      break;
2210    }
2211
2212    case Instruction::MOVE_EXCEPTION: {
2213      current_block_->AddInstruction(new (arena_) HLoadException());
2214      UpdateLocal(instruction.VRegA_11x(), current_block_->GetLastInstruction());
2215      break;
2216    }
2217
2218    case Instruction::THROW: {
2219      HInstruction* exception = LoadLocal(instruction.VRegA_11x(), Primitive::kPrimNot);
2220      current_block_->AddInstruction(new (arena_) HThrow(exception, dex_pc));
2221      // A throw instruction must branch to the exit block.
2222      current_block_->AddSuccessor(exit_block_);
2223      // We finished building this block. Set the current block to null to avoid
2224      // adding dead instructions to it.
2225      current_block_ = nullptr;
2226      break;
2227    }
2228
2229    case Instruction::INSTANCE_OF: {
2230      uint8_t destination = instruction.VRegA_22c();
2231      uint8_t reference = instruction.VRegB_22c();
2232      uint16_t type_index = instruction.VRegC_22c();
2233      if (!BuildTypeCheck(instruction, destination, reference, type_index, dex_pc)) {
2234        return false;
2235      }
2236      break;
2237    }
2238
2239    case Instruction::CHECK_CAST: {
2240      uint8_t reference = instruction.VRegA_21c();
2241      uint16_t type_index = instruction.VRegB_21c();
2242      if (!BuildTypeCheck(instruction, -1, reference, type_index, dex_pc)) {
2243        return false;
2244      }
2245      break;
2246    }
2247
2248    case Instruction::MONITOR_ENTER: {
2249      current_block_->AddInstruction(new (arena_) HMonitorOperation(
2250          LoadLocal(instruction.VRegA_11x(), Primitive::kPrimNot),
2251          HMonitorOperation::kEnter,
2252          dex_pc));
2253      break;
2254    }
2255
2256    case Instruction::MONITOR_EXIT: {
2257      current_block_->AddInstruction(new (arena_) HMonitorOperation(
2258          LoadLocal(instruction.VRegA_11x(), Primitive::kPrimNot),
2259          HMonitorOperation::kExit,
2260          dex_pc));
2261      break;
2262    }
2263
2264    case Instruction::PACKED_SWITCH: {
2265      BuildPackedSwitch(instruction, dex_pc);
2266      break;
2267    }
2268
2269    case Instruction::SPARSE_SWITCH: {
2270      BuildSparseSwitch(instruction, dex_pc);
2271      break;
2272    }
2273
2274    default:
2275      VLOG(compiler) << "Did not compile "
2276                     << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
2277                     << " because of unhandled instruction "
2278                     << instruction.Name();
2279      MaybeRecordStat(MethodCompilationStat::kNotCompiledUnhandledInstruction);
2280      return false;
2281  }
2282  return true;
2283}  // NOLINT(readability/fn_size)
2284
2285HLocal* HGraphBuilder::GetLocalAt(int register_index) const {
2286  return locals_.Get(register_index);
2287}
2288
2289void HGraphBuilder::UpdateLocal(int register_index, HInstruction* instruction) const {
2290  HLocal* local = GetLocalAt(register_index);
2291  current_block_->AddInstruction(new (arena_) HStoreLocal(local, instruction));
2292}
2293
2294HInstruction* HGraphBuilder::LoadLocal(int register_index, Primitive::Type type) const {
2295  HLocal* local = GetLocalAt(register_index);
2296  current_block_->AddInstruction(new (arena_) HLoadLocal(local, type));
2297  return current_block_->GetLastInstruction();
2298}
2299
2300}  // namespace art
2301