builder.cc revision 753f1fb083d5221f51b1d60d4089a33527ae5bc9 
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> referrer_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_referrer_class = (resolved_method->GetDeclaringClass() == referrer_class.Get());
690      if (is_referrer_class) {
691        storage_index = referrer_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                                                                   referrer_class.Get(),
696                                                                   resolved_method,
697                                                                   method_idx,
698                                                                   &storage_index);
699      }
700
701      if (referrer_class.Get()->IsSubClass(resolved_method->GetDeclaringClass())) {
702        // If the referrer class is the declaring class or a subclass
703        // of the declaring class, no class initialization is needed
704        // before the static method call.
705        clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kNone;
706      } else if (storage_index != DexFile::kDexNoIndex) {
707        // If the method's class type index is available, check
708        // whether we should add an explicit class initialization
709        // check for its declaring class before the static method call.
710
711        // TODO: find out why this check is needed.
712        bool is_in_dex_cache = compiler_driver_->CanAssumeTypeIsPresentInDexCache(
713            *outer_compilation_unit_->GetDexFile(), storage_index);
714        bool is_initialized =
715            resolved_method->GetDeclaringClass()->IsInitialized() && is_in_dex_cache;
716
717        if (is_initialized) {
718          clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kNone;
719        } else {
720          clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit;
721          HLoadClass* load_class =
722              new (arena_) HLoadClass(storage_index, is_referrer_class, dex_pc);
723          current_block_->AddInstruction(load_class);
724          clinit_check = new (arena_) HClinitCheck(load_class, dex_pc);
725          current_block_->AddInstruction(clinit_check);
726        }
727      }
728    }
729
730    invoke = new (arena_) HInvokeStaticOrDirect(
731        arena_, number_of_arguments, return_type, dex_pc, target_method.dex_method_index,
732        is_recursive, string_init_offset, invoke_type, optimized_invoke_type,
733        clinit_check_requirement);
734  }
735
736  size_t start_index = 0;
737  Temporaries temps(graph_);
738  if (is_instance_call) {
739    HInstruction* arg = LoadLocal(is_range ? register_index : args[0], Primitive::kPrimNot);
740    HNullCheck* null_check = new (arena_) HNullCheck(arg, dex_pc);
741    current_block_->AddInstruction(null_check);
742    temps.Add(null_check);
743    invoke->SetArgumentAt(0, null_check);
744    start_index = 1;
745  }
746
747  uint32_t descriptor_index = 1;  // Skip the return type.
748  uint32_t argument_index = start_index;
749  if (is_string_init) {
750    start_index = 1;
751  }
752  for (size_t i = start_index;
753       // Make sure we don't go over the expected arguments or over the number of
754       // dex registers given. If the instruction was seen as dead by the verifier,
755       // it hasn't been properly checked.
756       (i < number_of_vreg_arguments) && (argument_index < number_of_arguments);
757       i++, argument_index++) {
758    Primitive::Type type = Primitive::GetType(descriptor[descriptor_index++]);
759    bool is_wide = (type == Primitive::kPrimLong) || (type == Primitive::kPrimDouble);
760    if (!is_range
761        && is_wide
762        && ((i + 1 == number_of_vreg_arguments) || (args[i] + 1 != args[i + 1]))) {
763      // Longs and doubles should be in pairs, that is, sequential registers. The verifier should
764      // reject any class where this is violated. However, the verifier only does these checks
765      // on non trivially dead instructions, so we just bailout the compilation.
766      VLOG(compiler) << "Did not compile "
767                     << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
768                     << " because of non-sequential dex register pair in wide argument";
769      MaybeRecordStat(MethodCompilationStat::kNotCompiledMalformedOpcode);
770      return false;
771    }
772    HInstruction* arg = LoadLocal(is_range ? register_index + i : args[i], type);
773    invoke->SetArgumentAt(argument_index, arg);
774    if (is_wide) {
775      i++;
776    }
777  }
778
779  if (argument_index != number_of_arguments) {
780    VLOG(compiler) << "Did not compile "
781                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
782                   << " because of wrong number of arguments in invoke instruction";
783    MaybeRecordStat(MethodCompilationStat::kNotCompiledMalformedOpcode);
784    return false;
785  }
786
787  if (clinit_check_requirement == HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit) {
788    // Add the class initialization check as last input of `invoke`.
789    DCHECK(clinit_check != nullptr);
790    invoke->SetArgumentAt(argument_index, clinit_check);
791  }
792
793  current_block_->AddInstruction(invoke);
794  latest_result_ = invoke;
795
796  // Add move-result for StringFactory method.
797  if (is_string_init) {
798    uint32_t orig_this_reg = is_range ? register_index : args[0];
799    UpdateLocal(orig_this_reg, invoke);
800    const VerifiedMethod* verified_method =
801        compiler_driver_->GetVerifiedMethod(dex_file_, dex_compilation_unit_->GetDexMethodIndex());
802    if (verified_method == nullptr) {
803      LOG(WARNING) << "No verified method for method calling String.<init>: "
804                   << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_);
805      return false;
806    }
807    const SafeMap<uint32_t, std::set<uint32_t>>& string_init_map =
808        verified_method->GetStringInitPcRegMap();
809    auto map_it = string_init_map.find(dex_pc);
810    if (map_it != string_init_map.end()) {
811      std::set<uint32_t> reg_set = map_it->second;
812      for (auto set_it = reg_set.begin(); set_it != reg_set.end(); ++set_it) {
813        HInstruction* load_local = LoadLocal(orig_this_reg, Primitive::kPrimNot);
814        UpdateLocal(*set_it, load_local);
815      }
816    }
817  }
818  return true;
819}
820
821bool HGraphBuilder::BuildInstanceFieldAccess(const Instruction& instruction,
822                                             uint32_t dex_pc,
823                                             bool is_put) {
824  uint32_t source_or_dest_reg = instruction.VRegA_22c();
825  uint32_t obj_reg = instruction.VRegB_22c();
826  uint16_t field_index = instruction.VRegC_22c();
827
828  ScopedObjectAccess soa(Thread::Current());
829  ArtField* resolved_field =
830      compiler_driver_->ComputeInstanceFieldInfo(field_index, dex_compilation_unit_, is_put, soa);
831
832  if (resolved_field == nullptr) {
833    MaybeRecordStat(MethodCompilationStat::kNotCompiledUnresolvedField);
834    return false;
835  }
836
837  Primitive::Type field_type = resolved_field->GetTypeAsPrimitiveType();
838
839  HInstruction* object = LoadLocal(obj_reg, Primitive::kPrimNot);
840  current_block_->AddInstruction(new (arena_) HNullCheck(object, dex_pc));
841  if (is_put) {
842    Temporaries temps(graph_);
843    HInstruction* null_check = current_block_->GetLastInstruction();
844    // We need one temporary for the null check.
845    temps.Add(null_check);
846    HInstruction* value = LoadLocal(source_or_dest_reg, field_type);
847    current_block_->AddInstruction(new (arena_) HInstanceFieldSet(
848        null_check,
849        value,
850        field_type,
851        resolved_field->GetOffset(),
852        resolved_field->IsVolatile()));
853  } else {
854    current_block_->AddInstruction(new (arena_) HInstanceFieldGet(
855        current_block_->GetLastInstruction(),
856        field_type,
857        resolved_field->GetOffset(),
858        resolved_field->IsVolatile()));
859
860    UpdateLocal(source_or_dest_reg, current_block_->GetLastInstruction());
861  }
862  return true;
863}
864
865mirror::Class* HGraphBuilder::GetOutermostCompilingClass() const {
866  ScopedObjectAccess soa(Thread::Current());
867  StackHandleScope<2> hs(soa.Self());
868  const DexFile& outer_dex_file = *outer_compilation_unit_->GetDexFile();
869  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
870      soa.Decode<mirror::ClassLoader*>(dex_compilation_unit_->GetClassLoader())));
871  Handle<mirror::DexCache> outer_dex_cache(hs.NewHandle(
872      outer_compilation_unit_->GetClassLinker()->FindDexCache(outer_dex_file)));
873
874  return compiler_driver_->ResolveCompilingMethodsClass(
875      soa, outer_dex_cache, class_loader, outer_compilation_unit_);
876}
877
878bool HGraphBuilder::IsOutermostCompilingClass(uint16_t type_index) const {
879  ScopedObjectAccess soa(Thread::Current());
880  StackHandleScope<4> hs(soa.Self());
881  Handle<mirror::DexCache> dex_cache(hs.NewHandle(
882      dex_compilation_unit_->GetClassLinker()->FindDexCache(*dex_compilation_unit_->GetDexFile())));
883  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
884      soa.Decode<mirror::ClassLoader*>(dex_compilation_unit_->GetClassLoader())));
885  Handle<mirror::Class> cls(hs.NewHandle(compiler_driver_->ResolveClass(
886      soa, dex_cache, class_loader, type_index, dex_compilation_unit_)));
887  Handle<mirror::Class> compiling_class(hs.NewHandle(GetOutermostCompilingClass()));
888
889  return compiling_class.Get() == cls.Get();
890}
891
892bool HGraphBuilder::BuildStaticFieldAccess(const Instruction& instruction,
893                                           uint32_t dex_pc,
894                                           bool is_put) {
895  uint32_t source_or_dest_reg = instruction.VRegA_21c();
896  uint16_t field_index = instruction.VRegB_21c();
897
898  ScopedObjectAccess soa(Thread::Current());
899  StackHandleScope<4> hs(soa.Self());
900  Handle<mirror::DexCache> dex_cache(hs.NewHandle(
901      dex_compilation_unit_->GetClassLinker()->FindDexCache(*dex_compilation_unit_->GetDexFile())));
902  Handle<mirror::ClassLoader> class_loader(hs.NewHandle(
903      soa.Decode<mirror::ClassLoader*>(dex_compilation_unit_->GetClassLoader())));
904  ArtField* resolved_field = compiler_driver_->ResolveField(
905      soa, dex_cache, class_loader, dex_compilation_unit_, field_index, true);
906
907  if (resolved_field == nullptr) {
908    MaybeRecordStat(MethodCompilationStat::kNotCompiledUnresolvedField);
909    return false;
910  }
911
912  const DexFile& outer_dex_file = *outer_compilation_unit_->GetDexFile();
913  Handle<mirror::DexCache> outer_dex_cache(hs.NewHandle(
914      outer_compilation_unit_->GetClassLinker()->FindDexCache(outer_dex_file)));
915  Handle<mirror::Class> referrer_class(hs.NewHandle(GetOutermostCompilingClass()));
916
917  // The index at which the field's class is stored in the DexCache's type array.
918  uint32_t storage_index;
919  bool is_referrer_class = (referrer_class.Get() == resolved_field->GetDeclaringClass());
920  if (is_referrer_class) {
921    storage_index = referrer_class->GetDexTypeIndex();
922  } else if (outer_dex_cache.Get() != dex_cache.Get()) {
923    // The compiler driver cannot currently understand multiple dex caches involved. Just bailout.
924    return false;
925  } else {
926    std::pair<bool, bool> pair = compiler_driver_->IsFastStaticField(
927        outer_dex_cache.Get(),
928        referrer_class.Get(),
929        resolved_field,
930        field_index,
931        &storage_index);
932    bool can_easily_access = is_put ? pair.second : pair.first;
933    if (!can_easily_access) {
934      return false;
935    }
936  }
937
938  // TODO: find out why this check is needed.
939  bool is_in_dex_cache = compiler_driver_->CanAssumeTypeIsPresentInDexCache(
940      *outer_compilation_unit_->GetDexFile(), storage_index);
941  bool is_initialized = resolved_field->GetDeclaringClass()->IsInitialized() && is_in_dex_cache;
942
943  HLoadClass* constant = new (arena_) HLoadClass(storage_index, is_referrer_class, dex_pc);
944  current_block_->AddInstruction(constant);
945
946  HInstruction* cls = constant;
947  if (!is_initialized && !is_referrer_class) {
948    cls = new (arena_) HClinitCheck(constant, dex_pc);
949    current_block_->AddInstruction(cls);
950  }
951
952  Primitive::Type field_type = resolved_field->GetTypeAsPrimitiveType();
953  if (is_put) {
954    // We need to keep the class alive before loading the value.
955    Temporaries temps(graph_);
956    temps.Add(cls);
957    HInstruction* value = LoadLocal(source_or_dest_reg, field_type);
958    DCHECK_EQ(value->GetType(), field_type);
959    current_block_->AddInstruction(
960        new (arena_) HStaticFieldSet(cls, value, field_type, resolved_field->GetOffset(),
961            resolved_field->IsVolatile()));
962  } else {
963    current_block_->AddInstruction(
964        new (arena_) HStaticFieldGet(cls, field_type, resolved_field->GetOffset(),
965            resolved_field->IsVolatile()));
966    UpdateLocal(source_or_dest_reg, current_block_->GetLastInstruction());
967  }
968  return true;
969}
970
971void HGraphBuilder::BuildCheckedDivRem(uint16_t out_vreg,
972                                       uint16_t first_vreg,
973                                       int64_t second_vreg_or_constant,
974                                       uint32_t dex_pc,
975                                       Primitive::Type type,
976                                       bool second_is_constant,
977                                       bool isDiv) {
978  DCHECK(type == Primitive::kPrimInt || type == Primitive::kPrimLong);
979
980  HInstruction* first = LoadLocal(first_vreg, type);
981  HInstruction* second = nullptr;
982  if (second_is_constant) {
983    if (type == Primitive::kPrimInt) {
984      second = graph_->GetIntConstant(second_vreg_or_constant);
985    } else {
986      second = graph_->GetLongConstant(second_vreg_or_constant);
987    }
988  } else {
989    second = LoadLocal(second_vreg_or_constant, type);
990  }
991
992  if (!second_is_constant
993      || (type == Primitive::kPrimInt && second->AsIntConstant()->GetValue() == 0)
994      || (type == Primitive::kPrimLong && second->AsLongConstant()->GetValue() == 0)) {
995    second = new (arena_) HDivZeroCheck(second, dex_pc);
996    Temporaries temps(graph_);
997    current_block_->AddInstruction(second);
998    temps.Add(current_block_->GetLastInstruction());
999  }
1000
1001  if (isDiv) {
1002    current_block_->AddInstruction(new (arena_) HDiv(type, first, second, dex_pc));
1003  } else {
1004    current_block_->AddInstruction(new (arena_) HRem(type, first, second, dex_pc));
1005  }
1006  UpdateLocal(out_vreg, current_block_->GetLastInstruction());
1007}
1008
1009void HGraphBuilder::BuildArrayAccess(const Instruction& instruction,
1010                                     uint32_t dex_pc,
1011                                     bool is_put,
1012                                     Primitive::Type anticipated_type) {
1013  uint8_t source_or_dest_reg = instruction.VRegA_23x();
1014  uint8_t array_reg = instruction.VRegB_23x();
1015  uint8_t index_reg = instruction.VRegC_23x();
1016
1017  // We need one temporary for the null check, one for the index, and one for the length.
1018  Temporaries temps(graph_);
1019
1020  HInstruction* object = LoadLocal(array_reg, Primitive::kPrimNot);
1021  object = new (arena_) HNullCheck(object, dex_pc);
1022  current_block_->AddInstruction(object);
1023  temps.Add(object);
1024
1025  HInstruction* length = new (arena_) HArrayLength(object);
1026  current_block_->AddInstruction(length);
1027  temps.Add(length);
1028  HInstruction* index = LoadLocal(index_reg, Primitive::kPrimInt);
1029  index = new (arena_) HBoundsCheck(index, length, dex_pc);
1030  current_block_->AddInstruction(index);
1031  temps.Add(index);
1032  if (is_put) {
1033    HInstruction* value = LoadLocal(source_or_dest_reg, anticipated_type);
1034    // TODO: Insert a type check node if the type is Object.
1035    current_block_->AddInstruction(new (arena_) HArraySet(
1036        object, index, value, anticipated_type, dex_pc));
1037  } else {
1038    current_block_->AddInstruction(new (arena_) HArrayGet(object, index, anticipated_type));
1039    UpdateLocal(source_or_dest_reg, current_block_->GetLastInstruction());
1040  }
1041  graph_->SetHasBoundsChecks(true);
1042}
1043
1044void HGraphBuilder::BuildFilledNewArray(uint32_t dex_pc,
1045                                        uint32_t type_index,
1046                                        uint32_t number_of_vreg_arguments,
1047                                        bool is_range,
1048                                        uint32_t* args,
1049                                        uint32_t register_index) {
1050  HInstruction* length = graph_->GetIntConstant(number_of_vreg_arguments);
1051  QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
1052      ? kQuickAllocArrayWithAccessCheck
1053      : kQuickAllocArray;
1054  HInstruction* object = new (arena_) HNewArray(length, dex_pc, type_index, entrypoint);
1055  current_block_->AddInstruction(object);
1056
1057  const char* descriptor = dex_file_->StringByTypeIdx(type_index);
1058  DCHECK_EQ(descriptor[0], '[') << descriptor;
1059  char primitive = descriptor[1];
1060  DCHECK(primitive == 'I'
1061      || primitive == 'L'
1062      || primitive == '[') << descriptor;
1063  bool is_reference_array = (primitive == 'L') || (primitive == '[');
1064  Primitive::Type type = is_reference_array ? Primitive::kPrimNot : Primitive::kPrimInt;
1065
1066  Temporaries temps(graph_);
1067  temps.Add(object);
1068  for (size_t i = 0; i < number_of_vreg_arguments; ++i) {
1069    HInstruction* value = LoadLocal(is_range ? register_index + i : args[i], type);
1070    HInstruction* index = graph_->GetIntConstant(i);
1071    current_block_->AddInstruction(
1072        new (arena_) HArraySet(object, index, value, type, dex_pc));
1073  }
1074  latest_result_ = object;
1075}
1076
1077template <typename T>
1078void HGraphBuilder::BuildFillArrayData(HInstruction* object,
1079                                       const T* data,
1080                                       uint32_t element_count,
1081                                       Primitive::Type anticipated_type,
1082                                       uint32_t dex_pc) {
1083  for (uint32_t i = 0; i < element_count; ++i) {
1084    HInstruction* index = graph_->GetIntConstant(i);
1085    HInstruction* value = graph_->GetIntConstant(data[i]);
1086    current_block_->AddInstruction(new (arena_) HArraySet(
1087      object, index, value, anticipated_type, dex_pc));
1088  }
1089}
1090
1091void HGraphBuilder::BuildFillArrayData(const Instruction& instruction, uint32_t dex_pc) {
1092  Temporaries temps(graph_);
1093  HInstruction* array = LoadLocal(instruction.VRegA_31t(), Primitive::kPrimNot);
1094  HNullCheck* null_check = new (arena_) HNullCheck(array, dex_pc);
1095  current_block_->AddInstruction(null_check);
1096  temps.Add(null_check);
1097
1098  HInstruction* length = new (arena_) HArrayLength(null_check);
1099  current_block_->AddInstruction(length);
1100
1101  int32_t payload_offset = instruction.VRegB_31t() + dex_pc;
1102  const Instruction::ArrayDataPayload* payload =
1103      reinterpret_cast<const Instruction::ArrayDataPayload*>(code_start_ + payload_offset);
1104  const uint8_t* data = payload->data;
1105  uint32_t element_count = payload->element_count;
1106
1107  // Implementation of this DEX instruction seems to be that the bounds check is
1108  // done before doing any stores.
1109  HInstruction* last_index = graph_->GetIntConstant(payload->element_count - 1);
1110  current_block_->AddInstruction(new (arena_) HBoundsCheck(last_index, length, dex_pc));
1111
1112  switch (payload->element_width) {
1113    case 1:
1114      BuildFillArrayData(null_check,
1115                         reinterpret_cast<const int8_t*>(data),
1116                         element_count,
1117                         Primitive::kPrimByte,
1118                         dex_pc);
1119      break;
1120    case 2:
1121      BuildFillArrayData(null_check,
1122                         reinterpret_cast<const int16_t*>(data),
1123                         element_count,
1124                         Primitive::kPrimShort,
1125                         dex_pc);
1126      break;
1127    case 4:
1128      BuildFillArrayData(null_check,
1129                         reinterpret_cast<const int32_t*>(data),
1130                         element_count,
1131                         Primitive::kPrimInt,
1132                         dex_pc);
1133      break;
1134    case 8:
1135      BuildFillWideArrayData(null_check,
1136                             reinterpret_cast<const int64_t*>(data),
1137                             element_count,
1138                             dex_pc);
1139      break;
1140    default:
1141      LOG(FATAL) << "Unknown element width for " << payload->element_width;
1142  }
1143  graph_->SetHasBoundsChecks(true);
1144}
1145
1146void HGraphBuilder::BuildFillWideArrayData(HInstruction* object,
1147                                           const int64_t* data,
1148                                           uint32_t element_count,
1149                                           uint32_t dex_pc) {
1150  for (uint32_t i = 0; i < element_count; ++i) {
1151    HInstruction* index = graph_->GetIntConstant(i);
1152    HInstruction* value = graph_->GetLongConstant(data[i]);
1153    current_block_->AddInstruction(new (arena_) HArraySet(
1154      object, index, value, Primitive::kPrimLong, dex_pc));
1155  }
1156}
1157
1158bool HGraphBuilder::BuildTypeCheck(const Instruction& instruction,
1159                                   uint8_t destination,
1160                                   uint8_t reference,
1161                                   uint16_t type_index,
1162                                   uint32_t dex_pc) {
1163  bool type_known_final;
1164  bool type_known_abstract;
1165  // `CanAccessTypeWithoutChecks` will tell whether the method being
1166  // built is trying to access its own class, so that the generated
1167  // code can optimize for this case. However, the optimization does not
1168  // work for inlining, so we use `IsOutermostCompilingClass` instead.
1169  bool dont_use_is_referrers_class;
1170  bool can_access = compiler_driver_->CanAccessTypeWithoutChecks(
1171      dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index,
1172      &type_known_final, &type_known_abstract, &dont_use_is_referrers_class);
1173  if (!can_access) {
1174    MaybeRecordStat(MethodCompilationStat::kNotCompiledCantAccesType);
1175    return false;
1176  }
1177  HInstruction* object = LoadLocal(reference, Primitive::kPrimNot);
1178  HLoadClass* cls = new (arena_) HLoadClass(
1179      type_index, IsOutermostCompilingClass(type_index), dex_pc);
1180  current_block_->AddInstruction(cls);
1181  // The class needs a temporary before being used by the type check.
1182  Temporaries temps(graph_);
1183  temps.Add(cls);
1184  if (instruction.Opcode() == Instruction::INSTANCE_OF) {
1185    current_block_->AddInstruction(
1186        new (arena_) HInstanceOf(object, cls, type_known_final, dex_pc));
1187    UpdateLocal(destination, current_block_->GetLastInstruction());
1188  } else {
1189    DCHECK_EQ(instruction.Opcode(), Instruction::CHECK_CAST);
1190    current_block_->AddInstruction(
1191        new (arena_) HCheckCast(object, cls, type_known_final, dex_pc));
1192  }
1193  return true;
1194}
1195
1196bool HGraphBuilder::NeedsAccessCheck(uint32_t type_index) const {
1197  return !compiler_driver_->CanAccessInstantiableTypeWithoutChecks(
1198      dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index);
1199}
1200
1201void HGraphBuilder::BuildPackedSwitch(const Instruction& instruction, uint32_t dex_pc) {
1202  // Verifier guarantees that the payload for PackedSwitch contains:
1203  //   (a) number of entries (may be zero)
1204  //   (b) first and lowest switch case value (entry 0, always present)
1205  //   (c) list of target pcs (entries 1 <= i <= N)
1206  SwitchTable table(instruction, dex_pc, false);
1207
1208  // Value to test against.
1209  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
1210
1211  // Retrieve number of entries.
1212  uint16_t num_entries = table.GetNumEntries();
1213  if (num_entries == 0) {
1214    return;
1215  }
1216
1217  // Chained cmp-and-branch, starting from starting_key.
1218  int32_t starting_key = table.GetEntryAt(0);
1219
1220  for (size_t i = 1; i <= num_entries; i++) {
1221    BuildSwitchCaseHelper(instruction, i, i == num_entries, table, value, starting_key + i - 1,
1222                          table.GetEntryAt(i), dex_pc);
1223  }
1224}
1225
1226void HGraphBuilder::BuildSparseSwitch(const Instruction& instruction, uint32_t dex_pc) {
1227  // Verifier guarantees that the payload for SparseSwitch contains:
1228  //   (a) number of entries (may be zero)
1229  //   (b) sorted key values (entries 0 <= i < N)
1230  //   (c) target pcs corresponding to the switch values (entries N <= i < 2*N)
1231  SwitchTable table(instruction, dex_pc, true);
1232
1233  // Value to test against.
1234  HInstruction* value = LoadLocal(instruction.VRegA(), Primitive::kPrimInt);
1235
1236  uint16_t num_entries = table.GetNumEntries();
1237
1238  for (size_t i = 0; i < num_entries; i++) {
1239    BuildSwitchCaseHelper(instruction, i, i == static_cast<size_t>(num_entries) - 1, table, value,
1240                          table.GetEntryAt(i), table.GetEntryAt(i + num_entries), dex_pc);
1241  }
1242}
1243
1244void HGraphBuilder::BuildSwitchCaseHelper(const Instruction& instruction, size_t index,
1245                                          bool is_last_case, const SwitchTable& table,
1246                                          HInstruction* value, int32_t case_value_int,
1247                                          int32_t target_offset, uint32_t dex_pc) {
1248  HBasicBlock* case_target = FindBlockStartingAt(dex_pc + target_offset);
1249  DCHECK(case_target != nullptr);
1250  PotentiallyAddSuspendCheck(case_target, dex_pc);
1251
1252  // The current case's value.
1253  HInstruction* this_case_value = graph_->GetIntConstant(case_value_int);
1254
1255  // Compare value and this_case_value.
1256  HEqual* comparison = new (arena_) HEqual(value, this_case_value);
1257  current_block_->AddInstruction(comparison);
1258  HInstruction* ifinst = new (arena_) HIf(comparison);
1259  current_block_->AddInstruction(ifinst);
1260
1261  // Case hit: use the target offset to determine where to go.
1262  current_block_->AddSuccessor(case_target);
1263
1264  // Case miss: go to the next case (or default fall-through).
1265  // When there is a next case, we use the block stored with the table offset representing this
1266  // case (that is where we registered them in ComputeBranchTargets).
1267  // When there is no next case, we use the following instruction.
1268  // TODO: Find a good way to peel the last iteration to avoid conditional, but still have re-use.
1269  if (!is_last_case) {
1270    HBasicBlock* next_case_target = FindBlockStartingAt(table.GetDexPcForIndex(index));
1271    DCHECK(next_case_target != nullptr);
1272    current_block_->AddSuccessor(next_case_target);
1273
1274    // Need to manually add the block, as there is no dex-pc transition for the cases.
1275    graph_->AddBlock(next_case_target);
1276
1277    current_block_ = next_case_target;
1278  } else {
1279    HBasicBlock* default_target = FindBlockStartingAt(dex_pc + instruction.SizeInCodeUnits());
1280    DCHECK(default_target != nullptr);
1281    current_block_->AddSuccessor(default_target);
1282    current_block_ = nullptr;
1283  }
1284}
1285
1286void HGraphBuilder::PotentiallyAddSuspendCheck(HBasicBlock* target, uint32_t dex_pc) {
1287  int32_t target_offset = target->GetDexPc() - dex_pc;
1288  if (target_offset <= 0) {
1289    // DX generates back edges to the first encountered return. We can save
1290    // time of later passes by not adding redundant suspend checks.
1291    HInstruction* last_in_target = target->GetLastInstruction();
1292    if (last_in_target != nullptr &&
1293        (last_in_target->IsReturn() || last_in_target->IsReturnVoid())) {
1294      return;
1295    }
1296
1297    // Add a suspend check to backward branches which may potentially loop. We
1298    // can remove them after we recognize loops in the graph.
1299    current_block_->AddInstruction(new (arena_) HSuspendCheck(dex_pc));
1300  }
1301}
1302
1303bool HGraphBuilder::AnalyzeDexInstruction(const Instruction& instruction, uint32_t dex_pc) {
1304  if (current_block_ == nullptr) {
1305    return true;  // Dead code
1306  }
1307
1308  switch (instruction.Opcode()) {
1309    case Instruction::CONST_4: {
1310      int32_t register_index = instruction.VRegA();
1311      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_11n());
1312      UpdateLocal(register_index, constant);
1313      break;
1314    }
1315
1316    case Instruction::CONST_16: {
1317      int32_t register_index = instruction.VRegA();
1318      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_21s());
1319      UpdateLocal(register_index, constant);
1320      break;
1321    }
1322
1323    case Instruction::CONST: {
1324      int32_t register_index = instruction.VRegA();
1325      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_31i());
1326      UpdateLocal(register_index, constant);
1327      break;
1328    }
1329
1330    case Instruction::CONST_HIGH16: {
1331      int32_t register_index = instruction.VRegA();
1332      HIntConstant* constant = graph_->GetIntConstant(instruction.VRegB_21h() << 16);
1333      UpdateLocal(register_index, constant);
1334      break;
1335    }
1336
1337    case Instruction::CONST_WIDE_16: {
1338      int32_t register_index = instruction.VRegA();
1339      // Get 16 bits of constant value, sign extended to 64 bits.
1340      int64_t value = instruction.VRegB_21s();
1341      value <<= 48;
1342      value >>= 48;
1343      HLongConstant* constant = graph_->GetLongConstant(value);
1344      UpdateLocal(register_index, constant);
1345      break;
1346    }
1347
1348    case Instruction::CONST_WIDE_32: {
1349      int32_t register_index = instruction.VRegA();
1350      // Get 32 bits of constant value, sign extended to 64 bits.
1351      int64_t value = instruction.VRegB_31i();
1352      value <<= 32;
1353      value >>= 32;
1354      HLongConstant* constant = graph_->GetLongConstant(value);
1355      UpdateLocal(register_index, constant);
1356      break;
1357    }
1358
1359    case Instruction::CONST_WIDE: {
1360      int32_t register_index = instruction.VRegA();
1361      HLongConstant* constant = graph_->GetLongConstant(instruction.VRegB_51l());
1362      UpdateLocal(register_index, constant);
1363      break;
1364    }
1365
1366    case Instruction::CONST_WIDE_HIGH16: {
1367      int32_t register_index = instruction.VRegA();
1368      int64_t value = static_cast<int64_t>(instruction.VRegB_21h()) << 48;
1369      HLongConstant* constant = graph_->GetLongConstant(value);
1370      UpdateLocal(register_index, constant);
1371      break;
1372    }
1373
1374    // Note that the SSA building will refine the types.
1375    case Instruction::MOVE:
1376    case Instruction::MOVE_FROM16:
1377    case Instruction::MOVE_16: {
1378      HInstruction* value = LoadLocal(instruction.VRegB(), Primitive::kPrimInt);
1379      UpdateLocal(instruction.VRegA(), value);
1380      break;
1381    }
1382
1383    // Note that the SSA building will refine the types.
1384    case Instruction::MOVE_WIDE:
1385    case Instruction::MOVE_WIDE_FROM16:
1386    case Instruction::MOVE_WIDE_16: {
1387      HInstruction* value = LoadLocal(instruction.VRegB(), Primitive::kPrimLong);
1388      UpdateLocal(instruction.VRegA(), value);
1389      break;
1390    }
1391
1392    case Instruction::MOVE_OBJECT:
1393    case Instruction::MOVE_OBJECT_16:
1394    case Instruction::MOVE_OBJECT_FROM16: {
1395      HInstruction* value = LoadLocal(instruction.VRegB(), Primitive::kPrimNot);
1396      UpdateLocal(instruction.VRegA(), value);
1397      break;
1398    }
1399
1400    case Instruction::RETURN_VOID: {
1401      BuildReturn(instruction, Primitive::kPrimVoid);
1402      break;
1403    }
1404
1405#define IF_XX(comparison, cond) \
1406    case Instruction::IF_##cond: If_22t<comparison>(instruction, dex_pc); break; \
1407    case Instruction::IF_##cond##Z: If_21t<comparison>(instruction, dex_pc); break
1408
1409    IF_XX(HEqual, EQ);
1410    IF_XX(HNotEqual, NE);
1411    IF_XX(HLessThan, LT);
1412    IF_XX(HLessThanOrEqual, LE);
1413    IF_XX(HGreaterThan, GT);
1414    IF_XX(HGreaterThanOrEqual, GE);
1415
1416    case Instruction::GOTO:
1417    case Instruction::GOTO_16:
1418    case Instruction::GOTO_32: {
1419      int32_t offset = instruction.GetTargetOffset();
1420      HBasicBlock* target = FindBlockStartingAt(offset + dex_pc);
1421      DCHECK(target != nullptr);
1422      PotentiallyAddSuspendCheck(target, dex_pc);
1423      current_block_->AddInstruction(new (arena_) HGoto());
1424      current_block_->AddSuccessor(target);
1425      current_block_ = nullptr;
1426      break;
1427    }
1428
1429    case Instruction::RETURN: {
1430      DCHECK_NE(return_type_, Primitive::kPrimNot);
1431      DCHECK_NE(return_type_, Primitive::kPrimLong);
1432      DCHECK_NE(return_type_, Primitive::kPrimDouble);
1433      BuildReturn(instruction, return_type_);
1434      break;
1435    }
1436
1437    case Instruction::RETURN_OBJECT: {
1438      DCHECK(return_type_ == Primitive::kPrimNot);
1439      BuildReturn(instruction, return_type_);
1440      break;
1441    }
1442
1443    case Instruction::RETURN_WIDE: {
1444      DCHECK(return_type_ == Primitive::kPrimDouble || return_type_ == Primitive::kPrimLong);
1445      BuildReturn(instruction, return_type_);
1446      break;
1447    }
1448
1449    case Instruction::INVOKE_DIRECT:
1450    case Instruction::INVOKE_INTERFACE:
1451    case Instruction::INVOKE_STATIC:
1452    case Instruction::INVOKE_SUPER:
1453    case Instruction::INVOKE_VIRTUAL: {
1454      uint32_t method_idx = instruction.VRegB_35c();
1455      uint32_t number_of_vreg_arguments = instruction.VRegA_35c();
1456      uint32_t args[5];
1457      instruction.GetVarArgs(args);
1458      if (!BuildInvoke(instruction, dex_pc, method_idx,
1459                       number_of_vreg_arguments, false, args, -1)) {
1460        return false;
1461      }
1462      break;
1463    }
1464
1465    case Instruction::INVOKE_DIRECT_RANGE:
1466    case Instruction::INVOKE_INTERFACE_RANGE:
1467    case Instruction::INVOKE_STATIC_RANGE:
1468    case Instruction::INVOKE_SUPER_RANGE:
1469    case Instruction::INVOKE_VIRTUAL_RANGE: {
1470      uint32_t method_idx = instruction.VRegB_3rc();
1471      uint32_t number_of_vreg_arguments = instruction.VRegA_3rc();
1472      uint32_t register_index = instruction.VRegC();
1473      if (!BuildInvoke(instruction, dex_pc, method_idx,
1474                       number_of_vreg_arguments, true, nullptr, register_index)) {
1475        return false;
1476      }
1477      break;
1478    }
1479
1480    case Instruction::NEG_INT: {
1481      Unop_12x<HNeg>(instruction, Primitive::kPrimInt);
1482      break;
1483    }
1484
1485    case Instruction::NEG_LONG: {
1486      Unop_12x<HNeg>(instruction, Primitive::kPrimLong);
1487      break;
1488    }
1489
1490    case Instruction::NEG_FLOAT: {
1491      Unop_12x<HNeg>(instruction, Primitive::kPrimFloat);
1492      break;
1493    }
1494
1495    case Instruction::NEG_DOUBLE: {
1496      Unop_12x<HNeg>(instruction, Primitive::kPrimDouble);
1497      break;
1498    }
1499
1500    case Instruction::NOT_INT: {
1501      Unop_12x<HNot>(instruction, Primitive::kPrimInt);
1502      break;
1503    }
1504
1505    case Instruction::NOT_LONG: {
1506      Unop_12x<HNot>(instruction, Primitive::kPrimLong);
1507      break;
1508    }
1509
1510    case Instruction::INT_TO_LONG: {
1511      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimLong, dex_pc);
1512      break;
1513    }
1514
1515    case Instruction::INT_TO_FLOAT: {
1516      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimFloat, dex_pc);
1517      break;
1518    }
1519
1520    case Instruction::INT_TO_DOUBLE: {
1521      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimDouble, dex_pc);
1522      break;
1523    }
1524
1525    case Instruction::LONG_TO_INT: {
1526      Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimInt, dex_pc);
1527      break;
1528    }
1529
1530    case Instruction::LONG_TO_FLOAT: {
1531      Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimFloat, dex_pc);
1532      break;
1533    }
1534
1535    case Instruction::LONG_TO_DOUBLE: {
1536      Conversion_12x(instruction, Primitive::kPrimLong, Primitive::kPrimDouble, dex_pc);
1537      break;
1538    }
1539
1540    case Instruction::FLOAT_TO_INT: {
1541      Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimInt, dex_pc);
1542      break;
1543    }
1544
1545    case Instruction::FLOAT_TO_LONG: {
1546      Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimLong, dex_pc);
1547      break;
1548    }
1549
1550    case Instruction::FLOAT_TO_DOUBLE: {
1551      Conversion_12x(instruction, Primitive::kPrimFloat, Primitive::kPrimDouble, dex_pc);
1552      break;
1553    }
1554
1555    case Instruction::DOUBLE_TO_INT: {
1556      Conversion_12x(instruction, Primitive::kPrimDouble, Primitive::kPrimInt, dex_pc);
1557      break;
1558    }
1559
1560    case Instruction::DOUBLE_TO_LONG: {
1561      Conversion_12x(instruction, Primitive::kPrimDouble, Primitive::kPrimLong, dex_pc);
1562      break;
1563    }
1564
1565    case Instruction::DOUBLE_TO_FLOAT: {
1566      Conversion_12x(instruction, Primitive::kPrimDouble, Primitive::kPrimFloat, dex_pc);
1567      break;
1568    }
1569
1570    case Instruction::INT_TO_BYTE: {
1571      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimByte, dex_pc);
1572      break;
1573    }
1574
1575    case Instruction::INT_TO_SHORT: {
1576      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimShort, dex_pc);
1577      break;
1578    }
1579
1580    case Instruction::INT_TO_CHAR: {
1581      Conversion_12x(instruction, Primitive::kPrimInt, Primitive::kPrimChar, dex_pc);
1582      break;
1583    }
1584
1585    case Instruction::ADD_INT: {
1586      Binop_23x<HAdd>(instruction, Primitive::kPrimInt);
1587      break;
1588    }
1589
1590    case Instruction::ADD_LONG: {
1591      Binop_23x<HAdd>(instruction, Primitive::kPrimLong);
1592      break;
1593    }
1594
1595    case Instruction::ADD_DOUBLE: {
1596      Binop_23x<HAdd>(instruction, Primitive::kPrimDouble);
1597      break;
1598    }
1599
1600    case Instruction::ADD_FLOAT: {
1601      Binop_23x<HAdd>(instruction, Primitive::kPrimFloat);
1602      break;
1603    }
1604
1605    case Instruction::SUB_INT: {
1606      Binop_23x<HSub>(instruction, Primitive::kPrimInt);
1607      break;
1608    }
1609
1610    case Instruction::SUB_LONG: {
1611      Binop_23x<HSub>(instruction, Primitive::kPrimLong);
1612      break;
1613    }
1614
1615    case Instruction::SUB_FLOAT: {
1616      Binop_23x<HSub>(instruction, Primitive::kPrimFloat);
1617      break;
1618    }
1619
1620    case Instruction::SUB_DOUBLE: {
1621      Binop_23x<HSub>(instruction, Primitive::kPrimDouble);
1622      break;
1623    }
1624
1625    case Instruction::ADD_INT_2ADDR: {
1626      Binop_12x<HAdd>(instruction, Primitive::kPrimInt);
1627      break;
1628    }
1629
1630    case Instruction::MUL_INT: {
1631      Binop_23x<HMul>(instruction, Primitive::kPrimInt);
1632      break;
1633    }
1634
1635    case Instruction::MUL_LONG: {
1636      Binop_23x<HMul>(instruction, Primitive::kPrimLong);
1637      break;
1638    }
1639
1640    case Instruction::MUL_FLOAT: {
1641      Binop_23x<HMul>(instruction, Primitive::kPrimFloat);
1642      break;
1643    }
1644
1645    case Instruction::MUL_DOUBLE: {
1646      Binop_23x<HMul>(instruction, Primitive::kPrimDouble);
1647      break;
1648    }
1649
1650    case Instruction::DIV_INT: {
1651      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1652                         dex_pc, Primitive::kPrimInt, false, true);
1653      break;
1654    }
1655
1656    case Instruction::DIV_LONG: {
1657      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1658                         dex_pc, Primitive::kPrimLong, false, true);
1659      break;
1660    }
1661
1662    case Instruction::DIV_FLOAT: {
1663      Binop_23x<HDiv>(instruction, Primitive::kPrimFloat, dex_pc);
1664      break;
1665    }
1666
1667    case Instruction::DIV_DOUBLE: {
1668      Binop_23x<HDiv>(instruction, Primitive::kPrimDouble, dex_pc);
1669      break;
1670    }
1671
1672    case Instruction::REM_INT: {
1673      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1674                         dex_pc, Primitive::kPrimInt, false, false);
1675      break;
1676    }
1677
1678    case Instruction::REM_LONG: {
1679      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1680                         dex_pc, Primitive::kPrimLong, false, false);
1681      break;
1682    }
1683
1684    case Instruction::REM_FLOAT: {
1685      Binop_23x<HRem>(instruction, Primitive::kPrimFloat, dex_pc);
1686      break;
1687    }
1688
1689    case Instruction::REM_DOUBLE: {
1690      Binop_23x<HRem>(instruction, Primitive::kPrimDouble, dex_pc);
1691      break;
1692    }
1693
1694    case Instruction::AND_INT: {
1695      Binop_23x<HAnd>(instruction, Primitive::kPrimInt);
1696      break;
1697    }
1698
1699    case Instruction::AND_LONG: {
1700      Binop_23x<HAnd>(instruction, Primitive::kPrimLong);
1701      break;
1702    }
1703
1704    case Instruction::SHL_INT: {
1705      Binop_23x_shift<HShl>(instruction, Primitive::kPrimInt);
1706      break;
1707    }
1708
1709    case Instruction::SHL_LONG: {
1710      Binop_23x_shift<HShl>(instruction, Primitive::kPrimLong);
1711      break;
1712    }
1713
1714    case Instruction::SHR_INT: {
1715      Binop_23x_shift<HShr>(instruction, Primitive::kPrimInt);
1716      break;
1717    }
1718
1719    case Instruction::SHR_LONG: {
1720      Binop_23x_shift<HShr>(instruction, Primitive::kPrimLong);
1721      break;
1722    }
1723
1724    case Instruction::USHR_INT: {
1725      Binop_23x_shift<HUShr>(instruction, Primitive::kPrimInt);
1726      break;
1727    }
1728
1729    case Instruction::USHR_LONG: {
1730      Binop_23x_shift<HUShr>(instruction, Primitive::kPrimLong);
1731      break;
1732    }
1733
1734    case Instruction::OR_INT: {
1735      Binop_23x<HOr>(instruction, Primitive::kPrimInt);
1736      break;
1737    }
1738
1739    case Instruction::OR_LONG: {
1740      Binop_23x<HOr>(instruction, Primitive::kPrimLong);
1741      break;
1742    }
1743
1744    case Instruction::XOR_INT: {
1745      Binop_23x<HXor>(instruction, Primitive::kPrimInt);
1746      break;
1747    }
1748
1749    case Instruction::XOR_LONG: {
1750      Binop_23x<HXor>(instruction, Primitive::kPrimLong);
1751      break;
1752    }
1753
1754    case Instruction::ADD_LONG_2ADDR: {
1755      Binop_12x<HAdd>(instruction, Primitive::kPrimLong);
1756      break;
1757    }
1758
1759    case Instruction::ADD_DOUBLE_2ADDR: {
1760      Binop_12x<HAdd>(instruction, Primitive::kPrimDouble);
1761      break;
1762    }
1763
1764    case Instruction::ADD_FLOAT_2ADDR: {
1765      Binop_12x<HAdd>(instruction, Primitive::kPrimFloat);
1766      break;
1767    }
1768
1769    case Instruction::SUB_INT_2ADDR: {
1770      Binop_12x<HSub>(instruction, Primitive::kPrimInt);
1771      break;
1772    }
1773
1774    case Instruction::SUB_LONG_2ADDR: {
1775      Binop_12x<HSub>(instruction, Primitive::kPrimLong);
1776      break;
1777    }
1778
1779    case Instruction::SUB_FLOAT_2ADDR: {
1780      Binop_12x<HSub>(instruction, Primitive::kPrimFloat);
1781      break;
1782    }
1783
1784    case Instruction::SUB_DOUBLE_2ADDR: {
1785      Binop_12x<HSub>(instruction, Primitive::kPrimDouble);
1786      break;
1787    }
1788
1789    case Instruction::MUL_INT_2ADDR: {
1790      Binop_12x<HMul>(instruction, Primitive::kPrimInt);
1791      break;
1792    }
1793
1794    case Instruction::MUL_LONG_2ADDR: {
1795      Binop_12x<HMul>(instruction, Primitive::kPrimLong);
1796      break;
1797    }
1798
1799    case Instruction::MUL_FLOAT_2ADDR: {
1800      Binop_12x<HMul>(instruction, Primitive::kPrimFloat);
1801      break;
1802    }
1803
1804    case Instruction::MUL_DOUBLE_2ADDR: {
1805      Binop_12x<HMul>(instruction, Primitive::kPrimDouble);
1806      break;
1807    }
1808
1809    case Instruction::DIV_INT_2ADDR: {
1810      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1811                         dex_pc, Primitive::kPrimInt, false, true);
1812      break;
1813    }
1814
1815    case Instruction::DIV_LONG_2ADDR: {
1816      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1817                         dex_pc, Primitive::kPrimLong, false, true);
1818      break;
1819    }
1820
1821    case Instruction::REM_INT_2ADDR: {
1822      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1823                         dex_pc, Primitive::kPrimInt, false, false);
1824      break;
1825    }
1826
1827    case Instruction::REM_LONG_2ADDR: {
1828      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegA(), instruction.VRegB(),
1829                         dex_pc, Primitive::kPrimLong, false, false);
1830      break;
1831    }
1832
1833    case Instruction::REM_FLOAT_2ADDR: {
1834      Binop_12x<HRem>(instruction, Primitive::kPrimFloat, dex_pc);
1835      break;
1836    }
1837
1838    case Instruction::REM_DOUBLE_2ADDR: {
1839      Binop_12x<HRem>(instruction, Primitive::kPrimDouble, dex_pc);
1840      break;
1841    }
1842
1843    case Instruction::SHL_INT_2ADDR: {
1844      Binop_12x_shift<HShl>(instruction, Primitive::kPrimInt);
1845      break;
1846    }
1847
1848    case Instruction::SHL_LONG_2ADDR: {
1849      Binop_12x_shift<HShl>(instruction, Primitive::kPrimLong);
1850      break;
1851    }
1852
1853    case Instruction::SHR_INT_2ADDR: {
1854      Binop_12x_shift<HShr>(instruction, Primitive::kPrimInt);
1855      break;
1856    }
1857
1858    case Instruction::SHR_LONG_2ADDR: {
1859      Binop_12x_shift<HShr>(instruction, Primitive::kPrimLong);
1860      break;
1861    }
1862
1863    case Instruction::USHR_INT_2ADDR: {
1864      Binop_12x_shift<HUShr>(instruction, Primitive::kPrimInt);
1865      break;
1866    }
1867
1868    case Instruction::USHR_LONG_2ADDR: {
1869      Binop_12x_shift<HUShr>(instruction, Primitive::kPrimLong);
1870      break;
1871    }
1872
1873    case Instruction::DIV_FLOAT_2ADDR: {
1874      Binop_12x<HDiv>(instruction, Primitive::kPrimFloat, dex_pc);
1875      break;
1876    }
1877
1878    case Instruction::DIV_DOUBLE_2ADDR: {
1879      Binop_12x<HDiv>(instruction, Primitive::kPrimDouble, dex_pc);
1880      break;
1881    }
1882
1883    case Instruction::AND_INT_2ADDR: {
1884      Binop_12x<HAnd>(instruction, Primitive::kPrimInt);
1885      break;
1886    }
1887
1888    case Instruction::AND_LONG_2ADDR: {
1889      Binop_12x<HAnd>(instruction, Primitive::kPrimLong);
1890      break;
1891    }
1892
1893    case Instruction::OR_INT_2ADDR: {
1894      Binop_12x<HOr>(instruction, Primitive::kPrimInt);
1895      break;
1896    }
1897
1898    case Instruction::OR_LONG_2ADDR: {
1899      Binop_12x<HOr>(instruction, Primitive::kPrimLong);
1900      break;
1901    }
1902
1903    case Instruction::XOR_INT_2ADDR: {
1904      Binop_12x<HXor>(instruction, Primitive::kPrimInt);
1905      break;
1906    }
1907
1908    case Instruction::XOR_LONG_2ADDR: {
1909      Binop_12x<HXor>(instruction, Primitive::kPrimLong);
1910      break;
1911    }
1912
1913    case Instruction::ADD_INT_LIT16: {
1914      Binop_22s<HAdd>(instruction, false);
1915      break;
1916    }
1917
1918    case Instruction::AND_INT_LIT16: {
1919      Binop_22s<HAnd>(instruction, false);
1920      break;
1921    }
1922
1923    case Instruction::OR_INT_LIT16: {
1924      Binop_22s<HOr>(instruction, false);
1925      break;
1926    }
1927
1928    case Instruction::XOR_INT_LIT16: {
1929      Binop_22s<HXor>(instruction, false);
1930      break;
1931    }
1932
1933    case Instruction::RSUB_INT: {
1934      Binop_22s<HSub>(instruction, true);
1935      break;
1936    }
1937
1938    case Instruction::MUL_INT_LIT16: {
1939      Binop_22s<HMul>(instruction, false);
1940      break;
1941    }
1942
1943    case Instruction::ADD_INT_LIT8: {
1944      Binop_22b<HAdd>(instruction, false);
1945      break;
1946    }
1947
1948    case Instruction::AND_INT_LIT8: {
1949      Binop_22b<HAnd>(instruction, false);
1950      break;
1951    }
1952
1953    case Instruction::OR_INT_LIT8: {
1954      Binop_22b<HOr>(instruction, false);
1955      break;
1956    }
1957
1958    case Instruction::XOR_INT_LIT8: {
1959      Binop_22b<HXor>(instruction, false);
1960      break;
1961    }
1962
1963    case Instruction::RSUB_INT_LIT8: {
1964      Binop_22b<HSub>(instruction, true);
1965      break;
1966    }
1967
1968    case Instruction::MUL_INT_LIT8: {
1969      Binop_22b<HMul>(instruction, false);
1970      break;
1971    }
1972
1973    case Instruction::DIV_INT_LIT16:
1974    case Instruction::DIV_INT_LIT8: {
1975      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1976                         dex_pc, Primitive::kPrimInt, true, true);
1977      break;
1978    }
1979
1980    case Instruction::REM_INT_LIT16:
1981    case Instruction::REM_INT_LIT8: {
1982      BuildCheckedDivRem(instruction.VRegA(), instruction.VRegB(), instruction.VRegC(),
1983                         dex_pc, Primitive::kPrimInt, true, false);
1984      break;
1985    }
1986
1987    case Instruction::SHL_INT_LIT8: {
1988      Binop_22b<HShl>(instruction, false);
1989      break;
1990    }
1991
1992    case Instruction::SHR_INT_LIT8: {
1993      Binop_22b<HShr>(instruction, false);
1994      break;
1995    }
1996
1997    case Instruction::USHR_INT_LIT8: {
1998      Binop_22b<HUShr>(instruction, false);
1999      break;
2000    }
2001
2002    case Instruction::NEW_INSTANCE: {
2003      uint16_t type_index = instruction.VRegB_21c();
2004      if (compiler_driver_->IsStringTypeIndex(type_index, dex_file_)) {
2005        // Turn new-instance of string into a const 0.
2006        int32_t register_index = instruction.VRegA();
2007        HNullConstant* constant = graph_->GetNullConstant();
2008        UpdateLocal(register_index, constant);
2009      } else {
2010        QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
2011            ? kQuickAllocObjectWithAccessCheck
2012            : kQuickAllocObject;
2013
2014        current_block_->AddInstruction(new (arena_) HNewInstance(dex_pc, type_index, entrypoint));
2015        UpdateLocal(instruction.VRegA(), current_block_->GetLastInstruction());
2016      }
2017      break;
2018    }
2019
2020    case Instruction::NEW_ARRAY: {
2021      uint16_t type_index = instruction.VRegC_22c();
2022      HInstruction* length = LoadLocal(instruction.VRegB_22c(), Primitive::kPrimInt);
2023      QuickEntrypointEnum entrypoint = NeedsAccessCheck(type_index)
2024          ? kQuickAllocArrayWithAccessCheck
2025          : kQuickAllocArray;
2026      current_block_->AddInstruction(
2027          new (arena_) HNewArray(length, dex_pc, type_index, entrypoint));
2028      UpdateLocal(instruction.VRegA_22c(), current_block_->GetLastInstruction());
2029      break;
2030    }
2031
2032    case Instruction::FILLED_NEW_ARRAY: {
2033      uint32_t number_of_vreg_arguments = instruction.VRegA_35c();
2034      uint32_t type_index = instruction.VRegB_35c();
2035      uint32_t args[5];
2036      instruction.GetVarArgs(args);
2037      BuildFilledNewArray(dex_pc, type_index, number_of_vreg_arguments, false, args, 0);
2038      break;
2039    }
2040
2041    case Instruction::FILLED_NEW_ARRAY_RANGE: {
2042      uint32_t number_of_vreg_arguments = instruction.VRegA_3rc();
2043      uint32_t type_index = instruction.VRegB_3rc();
2044      uint32_t register_index = instruction.VRegC_3rc();
2045      BuildFilledNewArray(
2046          dex_pc, type_index, number_of_vreg_arguments, true, nullptr, register_index);
2047      break;
2048    }
2049
2050    case Instruction::FILL_ARRAY_DATA: {
2051      BuildFillArrayData(instruction, dex_pc);
2052      break;
2053    }
2054
2055    case Instruction::MOVE_RESULT:
2056    case Instruction::MOVE_RESULT_WIDE:
2057    case Instruction::MOVE_RESULT_OBJECT:
2058      UpdateLocal(instruction.VRegA(), latest_result_);
2059      latest_result_ = nullptr;
2060      break;
2061
2062    case Instruction::CMP_LONG: {
2063      Binop_23x_cmp(instruction, Primitive::kPrimLong, HCompare::kNoBias);
2064      break;
2065    }
2066
2067    case Instruction::CMPG_FLOAT: {
2068      Binop_23x_cmp(instruction, Primitive::kPrimFloat, HCompare::kGtBias);
2069      break;
2070    }
2071
2072    case Instruction::CMPG_DOUBLE: {
2073      Binop_23x_cmp(instruction, Primitive::kPrimDouble, HCompare::kGtBias);
2074      break;
2075    }
2076
2077    case Instruction::CMPL_FLOAT: {
2078      Binop_23x_cmp(instruction, Primitive::kPrimFloat, HCompare::kLtBias);
2079      break;
2080    }
2081
2082    case Instruction::CMPL_DOUBLE: {
2083      Binop_23x_cmp(instruction, Primitive::kPrimDouble, HCompare::kLtBias);
2084      break;
2085    }
2086
2087    case Instruction::NOP:
2088      break;
2089
2090    case Instruction::IGET:
2091    case Instruction::IGET_WIDE:
2092    case Instruction::IGET_OBJECT:
2093    case Instruction::IGET_BOOLEAN:
2094    case Instruction::IGET_BYTE:
2095    case Instruction::IGET_CHAR:
2096    case Instruction::IGET_SHORT: {
2097      if (!BuildInstanceFieldAccess(instruction, dex_pc, false)) {
2098        return false;
2099      }
2100      break;
2101    }
2102
2103    case Instruction::IPUT:
2104    case Instruction::IPUT_WIDE:
2105    case Instruction::IPUT_OBJECT:
2106    case Instruction::IPUT_BOOLEAN:
2107    case Instruction::IPUT_BYTE:
2108    case Instruction::IPUT_CHAR:
2109    case Instruction::IPUT_SHORT: {
2110      if (!BuildInstanceFieldAccess(instruction, dex_pc, true)) {
2111        return false;
2112      }
2113      break;
2114    }
2115
2116    case Instruction::SGET:
2117    case Instruction::SGET_WIDE:
2118    case Instruction::SGET_OBJECT:
2119    case Instruction::SGET_BOOLEAN:
2120    case Instruction::SGET_BYTE:
2121    case Instruction::SGET_CHAR:
2122    case Instruction::SGET_SHORT: {
2123      if (!BuildStaticFieldAccess(instruction, dex_pc, false)) {
2124        return false;
2125      }
2126      break;
2127    }
2128
2129    case Instruction::SPUT:
2130    case Instruction::SPUT_WIDE:
2131    case Instruction::SPUT_OBJECT:
2132    case Instruction::SPUT_BOOLEAN:
2133    case Instruction::SPUT_BYTE:
2134    case Instruction::SPUT_CHAR:
2135    case Instruction::SPUT_SHORT: {
2136      if (!BuildStaticFieldAccess(instruction, dex_pc, true)) {
2137        return false;
2138      }
2139      break;
2140    }
2141
2142#define ARRAY_XX(kind, anticipated_type)                                          \
2143    case Instruction::AGET##kind: {                                               \
2144      BuildArrayAccess(instruction, dex_pc, false, anticipated_type);         \
2145      break;                                                                      \
2146    }                                                                             \
2147    case Instruction::APUT##kind: {                                               \
2148      BuildArrayAccess(instruction, dex_pc, true, anticipated_type);          \
2149      break;                                                                      \
2150    }
2151
2152    ARRAY_XX(, Primitive::kPrimInt);
2153    ARRAY_XX(_WIDE, Primitive::kPrimLong);
2154    ARRAY_XX(_OBJECT, Primitive::kPrimNot);
2155    ARRAY_XX(_BOOLEAN, Primitive::kPrimBoolean);
2156    ARRAY_XX(_BYTE, Primitive::kPrimByte);
2157    ARRAY_XX(_CHAR, Primitive::kPrimChar);
2158    ARRAY_XX(_SHORT, Primitive::kPrimShort);
2159
2160    case Instruction::ARRAY_LENGTH: {
2161      HInstruction* object = LoadLocal(instruction.VRegB_12x(), Primitive::kPrimNot);
2162      // No need for a temporary for the null check, it is the only input of the following
2163      // instruction.
2164      object = new (arena_) HNullCheck(object, dex_pc);
2165      current_block_->AddInstruction(object);
2166      current_block_->AddInstruction(new (arena_) HArrayLength(object));
2167      UpdateLocal(instruction.VRegA_12x(), current_block_->GetLastInstruction());
2168      break;
2169    }
2170
2171    case Instruction::CONST_STRING: {
2172      current_block_->AddInstruction(new (arena_) HLoadString(instruction.VRegB_21c(), dex_pc));
2173      UpdateLocal(instruction.VRegA_21c(), current_block_->GetLastInstruction());
2174      break;
2175    }
2176
2177    case Instruction::CONST_STRING_JUMBO: {
2178      current_block_->AddInstruction(new (arena_) HLoadString(instruction.VRegB_31c(), dex_pc));
2179      UpdateLocal(instruction.VRegA_31c(), current_block_->GetLastInstruction());
2180      break;
2181    }
2182
2183    case Instruction::CONST_CLASS: {
2184      uint16_t type_index = instruction.VRegB_21c();
2185      bool type_known_final;
2186      bool type_known_abstract;
2187      bool dont_use_is_referrers_class;
2188      // `CanAccessTypeWithoutChecks` will tell whether the method being
2189      // built is trying to access its own class, so that the generated
2190      // code can optimize for this case. However, the optimization does not
2191      // work for inlining, so we use `IsOutermostCompilingClass` instead.
2192      bool can_access = compiler_driver_->CanAccessTypeWithoutChecks(
2193          dex_compilation_unit_->GetDexMethodIndex(), *dex_file_, type_index,
2194          &type_known_final, &type_known_abstract, &dont_use_is_referrers_class);
2195      if (!can_access) {
2196        MaybeRecordStat(MethodCompilationStat::kNotCompiledCantAccesType);
2197        return false;
2198      }
2199      current_block_->AddInstruction(
2200          new (arena_) HLoadClass(type_index, IsOutermostCompilingClass(type_index), dex_pc));
2201      UpdateLocal(instruction.VRegA_21c(), current_block_->GetLastInstruction());
2202      break;
2203    }
2204
2205    case Instruction::MOVE_EXCEPTION: {
2206      current_block_->AddInstruction(new (arena_) HLoadException());
2207      UpdateLocal(instruction.VRegA_11x(), current_block_->GetLastInstruction());
2208      break;
2209    }
2210
2211    case Instruction::THROW: {
2212      HInstruction* exception = LoadLocal(instruction.VRegA_11x(), Primitive::kPrimNot);
2213      current_block_->AddInstruction(new (arena_) HThrow(exception, dex_pc));
2214      // A throw instruction must branch to the exit block.
2215      current_block_->AddSuccessor(exit_block_);
2216      // We finished building this block. Set the current block to null to avoid
2217      // adding dead instructions to it.
2218      current_block_ = nullptr;
2219      break;
2220    }
2221
2222    case Instruction::INSTANCE_OF: {
2223      uint8_t destination = instruction.VRegA_22c();
2224      uint8_t reference = instruction.VRegB_22c();
2225      uint16_t type_index = instruction.VRegC_22c();
2226      if (!BuildTypeCheck(instruction, destination, reference, type_index, dex_pc)) {
2227        return false;
2228      }
2229      break;
2230    }
2231
2232    case Instruction::CHECK_CAST: {
2233      uint8_t reference = instruction.VRegA_21c();
2234      uint16_t type_index = instruction.VRegB_21c();
2235      if (!BuildTypeCheck(instruction, -1, reference, type_index, dex_pc)) {
2236        return false;
2237      }
2238      break;
2239    }
2240
2241    case Instruction::MONITOR_ENTER: {
2242      current_block_->AddInstruction(new (arena_) HMonitorOperation(
2243          LoadLocal(instruction.VRegA_11x(), Primitive::kPrimNot),
2244          HMonitorOperation::kEnter,
2245          dex_pc));
2246      break;
2247    }
2248
2249    case Instruction::MONITOR_EXIT: {
2250      current_block_->AddInstruction(new (arena_) HMonitorOperation(
2251          LoadLocal(instruction.VRegA_11x(), Primitive::kPrimNot),
2252          HMonitorOperation::kExit,
2253          dex_pc));
2254      break;
2255    }
2256
2257    case Instruction::PACKED_SWITCH: {
2258      BuildPackedSwitch(instruction, dex_pc);
2259      break;
2260    }
2261
2262    case Instruction::SPARSE_SWITCH: {
2263      BuildSparseSwitch(instruction, dex_pc);
2264      break;
2265    }
2266
2267    default:
2268      VLOG(compiler) << "Did not compile "
2269                     << PrettyMethod(dex_compilation_unit_->GetDexMethodIndex(), *dex_file_)
2270                     << " because of unhandled instruction "
2271                     << instruction.Name();
2272      MaybeRecordStat(MethodCompilationStat::kNotCompiledUnhandledInstruction);
2273      return false;
2274  }
2275  return true;
2276}  // NOLINT(readability/fn_size)
2277
2278HLocal* HGraphBuilder::GetLocalAt(int register_index) const {
2279  return locals_.Get(register_index);
2280}
2281
2282void HGraphBuilder::UpdateLocal(int register_index, HInstruction* instruction) const {
2283  HLocal* local = GetLocalAt(register_index);
2284  current_block_->AddInstruction(new (arena_) HStoreLocal(local, instruction));
2285}
2286
2287HInstruction* HGraphBuilder::LoadLocal(int register_index, Primitive::Type type) const {
2288  HLocal* local = GetLocalAt(register_index);
2289  current_block_->AddInstruction(new (arena_) HLoadLocal(local, type));
2290  return current_block_->GetLastInstruction();
2291}
2292
2293}  // namespace art
2294