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 "code_generator.h"
18
19#include "code_generator_arm.h"
20#include "code_generator_arm64.h"
21#include "code_generator_x86.h"
22#include "code_generator_x86_64.h"
23#include "code_generator_mips64.h"
24#include "compiled_method.h"
25#include "dex/verified_method.h"
26#include "driver/dex_compilation_unit.h"
27#include "gc_map_builder.h"
28#include "leb128.h"
29#include "mapping_table.h"
30#include "mirror/array-inl.h"
31#include "mirror/object_array-inl.h"
32#include "mirror/object_reference.h"
33#include "ssa_liveness_analysis.h"
34#include "utils/assembler.h"
35#include "verifier/dex_gc_map.h"
36#include "vmap_table.h"
37
38namespace art {
39
40// Return whether a location is consistent with a type.
41static bool CheckType(Primitive::Type type, Location location) {
42  if (location.IsFpuRegister()
43      || (location.IsUnallocated() && (location.GetPolicy() == Location::kRequiresFpuRegister))) {
44    return (type == Primitive::kPrimFloat) || (type == Primitive::kPrimDouble);
45  } else if (location.IsRegister() ||
46             (location.IsUnallocated() && (location.GetPolicy() == Location::kRequiresRegister))) {
47    return Primitive::IsIntegralType(type) || (type == Primitive::kPrimNot);
48  } else if (location.IsRegisterPair()) {
49    return type == Primitive::kPrimLong;
50  } else if (location.IsFpuRegisterPair()) {
51    return type == Primitive::kPrimDouble;
52  } else if (location.IsStackSlot()) {
53    return (Primitive::IsIntegralType(type) && type != Primitive::kPrimLong)
54           || (type == Primitive::kPrimFloat)
55           || (type == Primitive::kPrimNot);
56  } else if (location.IsDoubleStackSlot()) {
57    return (type == Primitive::kPrimLong) || (type == Primitive::kPrimDouble);
58  } else if (location.IsConstant()) {
59    if (location.GetConstant()->IsIntConstant()) {
60      return Primitive::IsIntegralType(type) && (type != Primitive::kPrimLong);
61    } else if (location.GetConstant()->IsNullConstant()) {
62      return type == Primitive::kPrimNot;
63    } else if (location.GetConstant()->IsLongConstant()) {
64      return type == Primitive::kPrimLong;
65    } else if (location.GetConstant()->IsFloatConstant()) {
66      return type == Primitive::kPrimFloat;
67    } else {
68      return location.GetConstant()->IsDoubleConstant()
69          && (type == Primitive::kPrimDouble);
70    }
71  } else {
72    return location.IsInvalid() || (location.GetPolicy() == Location::kAny);
73  }
74}
75
76// Check that a location summary is consistent with an instruction.
77static bool CheckTypeConsistency(HInstruction* instruction) {
78  LocationSummary* locations = instruction->GetLocations();
79  if (locations == nullptr) {
80    return true;
81  }
82
83  if (locations->Out().IsUnallocated()
84      && (locations->Out().GetPolicy() == Location::kSameAsFirstInput)) {
85    DCHECK(CheckType(instruction->GetType(), locations->InAt(0)))
86        << instruction->GetType()
87        << " " << locations->InAt(0);
88  } else {
89    DCHECK(CheckType(instruction->GetType(), locations->Out()))
90        << instruction->GetType()
91        << " " << locations->Out();
92  }
93
94  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
95    DCHECK(CheckType(instruction->InputAt(i)->GetType(), locations->InAt(i)))
96      << instruction->InputAt(i)->GetType()
97      << " " << locations->InAt(i);
98  }
99
100  HEnvironment* environment = instruction->GetEnvironment();
101  for (size_t i = 0; i < instruction->EnvironmentSize(); ++i) {
102    if (environment->GetInstructionAt(i) != nullptr) {
103      Primitive::Type type = environment->GetInstructionAt(i)->GetType();
104      DCHECK(CheckType(type, environment->GetLocationAt(i)))
105        << type << " " << environment->GetLocationAt(i);
106    } else {
107      DCHECK(environment->GetLocationAt(i).IsInvalid())
108        << environment->GetLocationAt(i);
109    }
110  }
111  return true;
112}
113
114size_t CodeGenerator::GetCacheOffset(uint32_t index) {
115  return mirror::ObjectArray<mirror::Object>::OffsetOfElement(index).SizeValue();
116}
117
118size_t CodeGenerator::GetCachePointerOffset(uint32_t index) {
119  auto pointer_size = InstructionSetPointerSize(GetInstructionSet());
120  return mirror::Array::DataOffset(pointer_size).Uint32Value() + pointer_size * index;
121}
122
123void CodeGenerator::CompileBaseline(CodeAllocator* allocator, bool is_leaf) {
124  Initialize();
125  if (!is_leaf) {
126    MarkNotLeaf();
127  }
128  const bool is_64_bit = Is64BitInstructionSet(GetInstructionSet());
129  InitializeCodeGeneration(GetGraph()->GetNumberOfLocalVRegs()
130                             + GetGraph()->GetTemporariesVRegSlots()
131                             + 1 /* filler */,
132                           0, /* the baseline compiler does not have live registers at slow path */
133                           0, /* the baseline compiler does not have live registers at slow path */
134                           GetGraph()->GetMaximumNumberOfOutVRegs()
135                             + (is_64_bit ? 2 : 1) /* current method */,
136                           GetGraph()->GetBlocks());
137  CompileInternal(allocator, /* is_baseline */ true);
138}
139
140bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
141  DCHECK_EQ(block_order_->Get(current_block_index_), current);
142  return GetNextBlockToEmit() == FirstNonEmptyBlock(next);
143}
144
145HBasicBlock* CodeGenerator::GetNextBlockToEmit() const {
146  for (size_t i = current_block_index_ + 1; i < block_order_->Size(); ++i) {
147    HBasicBlock* block = block_order_->Get(i);
148    if (!block->IsSingleGoto()) {
149      return block;
150    }
151  }
152  return nullptr;
153}
154
155HBasicBlock* CodeGenerator::FirstNonEmptyBlock(HBasicBlock* block) const {
156  while (block->IsSingleGoto()) {
157    block = block->GetSuccessors().Get(0);
158  }
159  return block;
160}
161
162void CodeGenerator::CompileInternal(CodeAllocator* allocator, bool is_baseline) {
163  is_baseline_ = is_baseline;
164  HGraphVisitor* instruction_visitor = GetInstructionVisitor();
165  DCHECK_EQ(current_block_index_, 0u);
166  GenerateFrameEntry();
167  DCHECK_EQ(GetAssembler()->cfi().GetCurrentCFAOffset(), static_cast<int>(frame_size_));
168  for (size_t e = block_order_->Size(); current_block_index_ < e; ++current_block_index_) {
169    HBasicBlock* block = block_order_->Get(current_block_index_);
170    // Don't generate code for an empty block. Its predecessors will branch to its successor
171    // directly. Also, the label of that block will not be emitted, so this helps catch
172    // errors where we reference that label.
173    if (block->IsSingleGoto()) continue;
174    Bind(block);
175    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
176      HInstruction* current = it.Current();
177      if (is_baseline) {
178        InitLocationsBaseline(current);
179      }
180      DCHECK(CheckTypeConsistency(current));
181      current->Accept(instruction_visitor);
182    }
183  }
184
185  // Generate the slow paths.
186  for (size_t i = 0, e = slow_paths_.Size(); i < e; ++i) {
187    slow_paths_.Get(i)->EmitNativeCode(this);
188  }
189
190  // Finalize instructions in assember;
191  Finalize(allocator);
192}
193
194void CodeGenerator::CompileOptimized(CodeAllocator* allocator) {
195  // The register allocator already called `InitializeCodeGeneration`,
196  // where the frame size has been computed.
197  DCHECK(block_order_ != nullptr);
198  Initialize();
199  CompileInternal(allocator, /* is_baseline */ false);
200}
201
202void CodeGenerator::Finalize(CodeAllocator* allocator) {
203  size_t code_size = GetAssembler()->CodeSize();
204  uint8_t* buffer = allocator->Allocate(code_size);
205
206  MemoryRegion code(buffer, code_size);
207  GetAssembler()->FinalizeInstructions(code);
208}
209
210size_t CodeGenerator::FindFreeEntry(bool* array, size_t length) {
211  for (size_t i = 0; i < length; ++i) {
212    if (!array[i]) {
213      array[i] = true;
214      return i;
215    }
216  }
217  LOG(FATAL) << "Could not find a register in baseline register allocator";
218  UNREACHABLE();
219}
220
221size_t CodeGenerator::FindTwoFreeConsecutiveAlignedEntries(bool* array, size_t length) {
222  for (size_t i = 0; i < length - 1; i += 2) {
223    if (!array[i] && !array[i + 1]) {
224      array[i] = true;
225      array[i + 1] = true;
226      return i;
227    }
228  }
229  LOG(FATAL) << "Could not find a register in baseline register allocator";
230  UNREACHABLE();
231}
232
233void CodeGenerator::InitializeCodeGeneration(size_t number_of_spill_slots,
234                                             size_t maximum_number_of_live_core_registers,
235                                             size_t maximum_number_of_live_fp_registers,
236                                             size_t number_of_out_slots,
237                                             const GrowableArray<HBasicBlock*>& block_order) {
238  block_order_ = &block_order;
239  DCHECK(block_order_->Get(0) == GetGraph()->GetEntryBlock());
240  ComputeSpillMask();
241  first_register_slot_in_slow_path_ = (number_of_out_slots + number_of_spill_slots) * kVRegSize;
242
243  if (number_of_spill_slots == 0
244      && !HasAllocatedCalleeSaveRegisters()
245      && IsLeafMethod()
246      && !RequiresCurrentMethod()) {
247    DCHECK_EQ(maximum_number_of_live_core_registers, 0u);
248    DCHECK_EQ(maximum_number_of_live_fp_registers, 0u);
249    SetFrameSize(CallPushesPC() ? GetWordSize() : 0);
250  } else {
251    SetFrameSize(RoundUp(
252        number_of_spill_slots * kVRegSize
253        + number_of_out_slots * kVRegSize
254        + maximum_number_of_live_core_registers * GetWordSize()
255        + maximum_number_of_live_fp_registers * GetFloatingPointSpillSlotSize()
256        + FrameEntrySpillSize(),
257        kStackAlignment));
258  }
259}
260
261Location CodeGenerator::GetTemporaryLocation(HTemporary* temp) const {
262  uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
263  // The type of the previous instruction tells us if we need a single or double stack slot.
264  Primitive::Type type = temp->GetType();
265  int32_t temp_size = (type == Primitive::kPrimLong) || (type == Primitive::kPrimDouble) ? 2 : 1;
266  // Use the temporary region (right below the dex registers).
267  int32_t slot = GetFrameSize() - FrameEntrySpillSize()
268                                - kVRegSize  // filler
269                                - (number_of_locals * kVRegSize)
270                                - ((temp_size + temp->GetIndex()) * kVRegSize);
271  return temp_size == 2 ? Location::DoubleStackSlot(slot) : Location::StackSlot(slot);
272}
273
274int32_t CodeGenerator::GetStackSlot(HLocal* local) const {
275  uint16_t reg_number = local->GetRegNumber();
276  uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
277  if (reg_number >= number_of_locals) {
278    // Local is a parameter of the method. It is stored in the caller's frame.
279    // TODO: Share this logic with StackVisitor::GetVRegOffsetFromQuickCode.
280    return GetFrameSize() + InstructionSetPointerSize(GetInstructionSet())  // ART method
281                          + (reg_number - number_of_locals) * kVRegSize;
282  } else {
283    // Local is a temporary in this method. It is stored in this method's frame.
284    return GetFrameSize() - FrameEntrySpillSize()
285                          - kVRegSize  // filler.
286                          - (number_of_locals * kVRegSize)
287                          + (reg_number * kVRegSize);
288  }
289}
290
291void CodeGenerator::BlockIfInRegister(Location location, bool is_out) const {
292  // The DCHECKS below check that a register is not specified twice in
293  // the summary. The out location can overlap with an input, so we need
294  // to special case it.
295  if (location.IsRegister()) {
296    DCHECK(is_out || !blocked_core_registers_[location.reg()]);
297    blocked_core_registers_[location.reg()] = true;
298  } else if (location.IsFpuRegister()) {
299    DCHECK(is_out || !blocked_fpu_registers_[location.reg()]);
300    blocked_fpu_registers_[location.reg()] = true;
301  } else if (location.IsFpuRegisterPair()) {
302    DCHECK(is_out || !blocked_fpu_registers_[location.AsFpuRegisterPairLow<int>()]);
303    blocked_fpu_registers_[location.AsFpuRegisterPairLow<int>()] = true;
304    DCHECK(is_out || !blocked_fpu_registers_[location.AsFpuRegisterPairHigh<int>()]);
305    blocked_fpu_registers_[location.AsFpuRegisterPairHigh<int>()] = true;
306  } else if (location.IsRegisterPair()) {
307    DCHECK(is_out || !blocked_core_registers_[location.AsRegisterPairLow<int>()]);
308    blocked_core_registers_[location.AsRegisterPairLow<int>()] = true;
309    DCHECK(is_out || !blocked_core_registers_[location.AsRegisterPairHigh<int>()]);
310    blocked_core_registers_[location.AsRegisterPairHigh<int>()] = true;
311  }
312}
313
314void CodeGenerator::AllocateRegistersLocally(HInstruction* instruction) const {
315  LocationSummary* locations = instruction->GetLocations();
316  if (locations == nullptr) return;
317
318  for (size_t i = 0, e = GetNumberOfCoreRegisters(); i < e; ++i) {
319    blocked_core_registers_[i] = false;
320  }
321
322  for (size_t i = 0, e = GetNumberOfFloatingPointRegisters(); i < e; ++i) {
323    blocked_fpu_registers_[i] = false;
324  }
325
326  for (size_t i = 0, e = number_of_register_pairs_; i < e; ++i) {
327    blocked_register_pairs_[i] = false;
328  }
329
330  // Mark all fixed input, temp and output registers as used.
331  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
332    BlockIfInRegister(locations->InAt(i));
333  }
334
335  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
336    Location loc = locations->GetTemp(i);
337    BlockIfInRegister(loc);
338  }
339  Location result_location = locations->Out();
340  if (locations->OutputCanOverlapWithInputs()) {
341    BlockIfInRegister(result_location, /* is_out */ true);
342  }
343
344  SetupBlockedRegisters(/* is_baseline */ true);
345
346  // Allocate all unallocated input locations.
347  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
348    Location loc = locations->InAt(i);
349    HInstruction* input = instruction->InputAt(i);
350    if (loc.IsUnallocated()) {
351      if ((loc.GetPolicy() == Location::kRequiresRegister)
352          || (loc.GetPolicy() == Location::kRequiresFpuRegister)) {
353        loc = AllocateFreeRegister(input->GetType());
354      } else {
355        DCHECK_EQ(loc.GetPolicy(), Location::kAny);
356        HLoadLocal* load = input->AsLoadLocal();
357        if (load != nullptr) {
358          loc = GetStackLocation(load);
359        } else {
360          loc = AllocateFreeRegister(input->GetType());
361        }
362      }
363      locations->SetInAt(i, loc);
364    }
365  }
366
367  // Allocate all unallocated temp locations.
368  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
369    Location loc = locations->GetTemp(i);
370    if (loc.IsUnallocated()) {
371      switch (loc.GetPolicy()) {
372        case Location::kRequiresRegister:
373          // Allocate a core register (large enough to fit a 32-bit integer).
374          loc = AllocateFreeRegister(Primitive::kPrimInt);
375          break;
376
377        case Location::kRequiresFpuRegister:
378          // Allocate a core register (large enough to fit a 64-bit double).
379          loc = AllocateFreeRegister(Primitive::kPrimDouble);
380          break;
381
382        default:
383          LOG(FATAL) << "Unexpected policy for temporary location "
384                     << loc.GetPolicy();
385      }
386      locations->SetTempAt(i, loc);
387    }
388  }
389  if (result_location.IsUnallocated()) {
390    switch (result_location.GetPolicy()) {
391      case Location::kAny:
392      case Location::kRequiresRegister:
393      case Location::kRequiresFpuRegister:
394        result_location = AllocateFreeRegister(instruction->GetType());
395        break;
396      case Location::kSameAsFirstInput:
397        result_location = locations->InAt(0);
398        break;
399    }
400    locations->UpdateOut(result_location);
401  }
402}
403
404void CodeGenerator::InitLocationsBaseline(HInstruction* instruction) {
405  AllocateLocations(instruction);
406  if (instruction->GetLocations() == nullptr) {
407    if (instruction->IsTemporary()) {
408      HInstruction* previous = instruction->GetPrevious();
409      Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
410      Move(previous, temp_location, instruction);
411    }
412    return;
413  }
414  AllocateRegistersLocally(instruction);
415  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
416    Location location = instruction->GetLocations()->InAt(i);
417    HInstruction* input = instruction->InputAt(i);
418    if (location.IsValid()) {
419      // Move the input to the desired location.
420      if (input->GetNext()->IsTemporary()) {
421        // If the input was stored in a temporary, use that temporary to
422        // perform the move.
423        Move(input->GetNext(), location, instruction);
424      } else {
425        Move(input, location, instruction);
426      }
427    }
428  }
429}
430
431void CodeGenerator::AllocateLocations(HInstruction* instruction) {
432  instruction->Accept(GetLocationBuilder());
433  DCHECK(CheckTypeConsistency(instruction));
434  LocationSummary* locations = instruction->GetLocations();
435  if (!instruction->IsSuspendCheckEntry()) {
436    if (locations != nullptr && locations->CanCall()) {
437      MarkNotLeaf();
438    }
439    if (instruction->NeedsCurrentMethod()) {
440      SetRequiresCurrentMethod();
441    }
442  }
443}
444
445CodeGenerator* CodeGenerator::Create(HGraph* graph,
446                                     InstructionSet instruction_set,
447                                     const InstructionSetFeatures& isa_features,
448                                     const CompilerOptions& compiler_options) {
449  switch (instruction_set) {
450    case kArm:
451    case kThumb2: {
452      return new arm::CodeGeneratorARM(graph,
453          *isa_features.AsArmInstructionSetFeatures(),
454          compiler_options);
455    }
456    case kArm64: {
457      return new arm64::CodeGeneratorARM64(graph,
458          *isa_features.AsArm64InstructionSetFeatures(),
459          compiler_options);
460    }
461    case kMips:
462      return nullptr;
463    case kMips64: {
464      return new mips64::CodeGeneratorMIPS64(graph,
465          *isa_features.AsMips64InstructionSetFeatures(),
466          compiler_options);
467    }
468    case kX86: {
469      return new x86::CodeGeneratorX86(graph,
470           *isa_features.AsX86InstructionSetFeatures(),
471           compiler_options);
472    }
473    case kX86_64: {
474      return new x86_64::CodeGeneratorX86_64(graph,
475          *isa_features.AsX86_64InstructionSetFeatures(),
476          compiler_options);
477    }
478    default:
479      return nullptr;
480  }
481}
482
483void CodeGenerator::BuildNativeGCMap(
484    std::vector<uint8_t>* data, const DexCompilationUnit& dex_compilation_unit) const {
485  const std::vector<uint8_t>& gc_map_raw =
486      dex_compilation_unit.GetVerifiedMethod()->GetDexGcMap();
487  verifier::DexPcToReferenceMap dex_gc_map(&(gc_map_raw)[0]);
488
489  uint32_t max_native_offset = 0;
490  for (size_t i = 0; i < pc_infos_.Size(); i++) {
491    uint32_t native_offset = pc_infos_.Get(i).native_pc;
492    if (native_offset > max_native_offset) {
493      max_native_offset = native_offset;
494    }
495  }
496
497  GcMapBuilder builder(data, pc_infos_.Size(), max_native_offset, dex_gc_map.RegWidth());
498  for (size_t i = 0; i < pc_infos_.Size(); i++) {
499    struct PcInfo pc_info = pc_infos_.Get(i);
500    uint32_t native_offset = pc_info.native_pc;
501    uint32_t dex_pc = pc_info.dex_pc;
502    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
503    CHECK(references != nullptr) << "Missing ref for dex pc 0x" << std::hex << dex_pc;
504    builder.AddEntry(native_offset, references);
505  }
506}
507
508void CodeGenerator::BuildSourceMap(DefaultSrcMap* src_map) const {
509  for (size_t i = 0; i < pc_infos_.Size(); i++) {
510    struct PcInfo pc_info = pc_infos_.Get(i);
511    uint32_t pc2dex_offset = pc_info.native_pc;
512    int32_t pc2dex_dalvik_offset = pc_info.dex_pc;
513    src_map->push_back(SrcMapElem({pc2dex_offset, pc2dex_dalvik_offset}));
514  }
515}
516
517void CodeGenerator::BuildMappingTable(std::vector<uint8_t>* data) const {
518  uint32_t pc2dex_data_size = 0u;
519  uint32_t pc2dex_entries = pc_infos_.Size();
520  uint32_t pc2dex_offset = 0u;
521  int32_t pc2dex_dalvik_offset = 0;
522  uint32_t dex2pc_data_size = 0u;
523  uint32_t dex2pc_entries = 0u;
524  uint32_t dex2pc_offset = 0u;
525  int32_t dex2pc_dalvik_offset = 0;
526
527  for (size_t i = 0; i < pc2dex_entries; i++) {
528    struct PcInfo pc_info = pc_infos_.Get(i);
529    pc2dex_data_size += UnsignedLeb128Size(pc_info.native_pc - pc2dex_offset);
530    pc2dex_data_size += SignedLeb128Size(pc_info.dex_pc - pc2dex_dalvik_offset);
531    pc2dex_offset = pc_info.native_pc;
532    pc2dex_dalvik_offset = pc_info.dex_pc;
533  }
534
535  // Walk over the blocks and find which ones correspond to catch block entries.
536  for (size_t i = 0; i < graph_->GetBlocks().Size(); ++i) {
537    HBasicBlock* block = graph_->GetBlocks().Get(i);
538    if (block->IsCatchBlock()) {
539      intptr_t native_pc = GetAddressOf(block);
540      ++dex2pc_entries;
541      dex2pc_data_size += UnsignedLeb128Size(native_pc - dex2pc_offset);
542      dex2pc_data_size += SignedLeb128Size(block->GetDexPc() - dex2pc_dalvik_offset);
543      dex2pc_offset = native_pc;
544      dex2pc_dalvik_offset = block->GetDexPc();
545    }
546  }
547
548  uint32_t total_entries = pc2dex_entries + dex2pc_entries;
549  uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
550  uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
551  data->resize(data_size);
552
553  uint8_t* data_ptr = &(*data)[0];
554  uint8_t* write_pos = data_ptr;
555
556  write_pos = EncodeUnsignedLeb128(write_pos, total_entries);
557  write_pos = EncodeUnsignedLeb128(write_pos, pc2dex_entries);
558  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size);
559  uint8_t* write_pos2 = write_pos + pc2dex_data_size;
560
561  pc2dex_offset = 0u;
562  pc2dex_dalvik_offset = 0u;
563  dex2pc_offset = 0u;
564  dex2pc_dalvik_offset = 0u;
565
566  for (size_t i = 0; i < pc2dex_entries; i++) {
567    struct PcInfo pc_info = pc_infos_.Get(i);
568    DCHECK(pc2dex_offset <= pc_info.native_pc);
569    write_pos = EncodeUnsignedLeb128(write_pos, pc_info.native_pc - pc2dex_offset);
570    write_pos = EncodeSignedLeb128(write_pos, pc_info.dex_pc - pc2dex_dalvik_offset);
571    pc2dex_offset = pc_info.native_pc;
572    pc2dex_dalvik_offset = pc_info.dex_pc;
573  }
574
575  for (size_t i = 0; i < graph_->GetBlocks().Size(); ++i) {
576    HBasicBlock* block = graph_->GetBlocks().Get(i);
577    if (block->IsCatchBlock()) {
578      intptr_t native_pc = GetAddressOf(block);
579      write_pos2 = EncodeUnsignedLeb128(write_pos2, native_pc - dex2pc_offset);
580      write_pos2 = EncodeSignedLeb128(write_pos2, block->GetDexPc() - dex2pc_dalvik_offset);
581      dex2pc_offset = native_pc;
582      dex2pc_dalvik_offset = block->GetDexPc();
583    }
584  }
585
586
587  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size + pc2dex_data_size);
588  DCHECK_EQ(static_cast<size_t>(write_pos2 - data_ptr), data_size);
589
590  if (kIsDebugBuild) {
591    // Verify the encoded table holds the expected data.
592    MappingTable table(data_ptr);
593    CHECK_EQ(table.TotalSize(), total_entries);
594    CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
595    auto it = table.PcToDexBegin();
596    auto it2 = table.DexToPcBegin();
597    for (size_t i = 0; i < pc2dex_entries; i++) {
598      struct PcInfo pc_info = pc_infos_.Get(i);
599      CHECK_EQ(pc_info.native_pc, it.NativePcOffset());
600      CHECK_EQ(pc_info.dex_pc, it.DexPc());
601      ++it;
602    }
603    for (size_t i = 0; i < graph_->GetBlocks().Size(); ++i) {
604      HBasicBlock* block = graph_->GetBlocks().Get(i);
605      if (block->IsCatchBlock()) {
606        CHECK_EQ(GetAddressOf(block), it2.NativePcOffset());
607        CHECK_EQ(block->GetDexPc(), it2.DexPc());
608        ++it2;
609      }
610    }
611    CHECK(it == table.PcToDexEnd());
612    CHECK(it2 == table.DexToPcEnd());
613  }
614}
615
616void CodeGenerator::BuildVMapTable(std::vector<uint8_t>* data) const {
617  Leb128EncodingVector vmap_encoder;
618  // We currently don't use callee-saved registers.
619  size_t size = 0 + 1 /* marker */ + 0;
620  vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
621  vmap_encoder.PushBackUnsigned(size);
622  vmap_encoder.PushBackUnsigned(VmapTable::kAdjustedFpMarker);
623
624  *data = vmap_encoder.GetData();
625}
626
627void CodeGenerator::BuildStackMaps(std::vector<uint8_t>* data) {
628  uint32_t size = stack_map_stream_.PrepareForFillIn();
629  data->resize(size);
630  MemoryRegion region(data->data(), size);
631  stack_map_stream_.FillIn(region);
632}
633
634void CodeGenerator::RecordPcInfo(HInstruction* instruction,
635                                 uint32_t dex_pc,
636                                 SlowPathCode* slow_path) {
637  if (instruction != nullptr) {
638    // The code generated for some type conversions and comparisons
639    // may call the runtime, thus normally requiring a subsequent
640    // call to this method. However, the method verifier does not
641    // produce PC information for certain instructions, which are
642    // considered "atomic" (they cannot join a GC).
643    // Therefore we do not currently record PC information for such
644    // instructions.  As this may change later, we added this special
645    // case so that code generators may nevertheless call
646    // CodeGenerator::RecordPcInfo without triggering an error in
647    // CodeGenerator::BuildNativeGCMap ("Missing ref for dex pc 0x")
648    // thereafter.
649    if (instruction->IsTypeConversion() || instruction->IsCompare()) {
650      return;
651    }
652    if (instruction->IsRem()) {
653      Primitive::Type type = instruction->AsRem()->GetResultType();
654      if ((type == Primitive::kPrimFloat) || (type == Primitive::kPrimDouble)) {
655        return;
656      }
657    }
658  }
659
660  // Collect PC infos for the mapping table.
661  struct PcInfo pc_info;
662  pc_info.dex_pc = dex_pc;
663  pc_info.native_pc = GetAssembler()->CodeSize();
664  pc_infos_.Add(pc_info);
665
666  uint32_t inlining_depth = 0;
667
668  if (instruction == nullptr) {
669    // For stack overflow checks.
670    stack_map_stream_.BeginStackMapEntry(dex_pc, pc_info.native_pc, 0, 0, 0, inlining_depth);
671    stack_map_stream_.EndStackMapEntry();
672    return;
673  }
674  LocationSummary* locations = instruction->GetLocations();
675  HEnvironment* environment = instruction->GetEnvironment();
676  size_t environment_size = instruction->EnvironmentSize();
677
678  uint32_t register_mask = locations->GetRegisterMask();
679  if (locations->OnlyCallsOnSlowPath()) {
680    // In case of slow path, we currently set the location of caller-save registers
681    // to register (instead of their stack location when pushed before the slow-path
682    // call). Therefore register_mask contains both callee-save and caller-save
683    // registers that hold objects. We must remove the caller-save from the mask, since
684    // they will be overwritten by the callee.
685    register_mask &= core_callee_save_mask_;
686  }
687  // The register mask must be a subset of callee-save registers.
688  DCHECK_EQ(register_mask & core_callee_save_mask_, register_mask);
689  stack_map_stream_.BeginStackMapEntry(dex_pc,
690                                       pc_info.native_pc,
691                                       register_mask,
692                                       locations->GetStackMask(),
693                                       environment_size,
694                                       inlining_depth);
695  if (environment != nullptr) {
696    // TODO: Handle parent environment.
697    DCHECK(environment->GetParent() == nullptr);
698    DCHECK_EQ(environment->GetDexPc(), dex_pc);
699  }
700
701  // Walk over the environment, and record the location of dex registers.
702  for (size_t i = 0; i < environment_size; ++i) {
703    HInstruction* current = environment->GetInstructionAt(i);
704    if (current == nullptr) {
705      stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kNone, 0);
706      continue;
707    }
708
709    Location location = environment->GetLocationAt(i);
710    switch (location.GetKind()) {
711      case Location::kConstant: {
712        DCHECK_EQ(current, location.GetConstant());
713        if (current->IsLongConstant()) {
714          int64_t value = current->AsLongConstant()->GetValue();
715          stack_map_stream_.AddDexRegisterEntry(
716              i, DexRegisterLocation::Kind::kConstant, Low32Bits(value));
717          stack_map_stream_.AddDexRegisterEntry(
718              ++i, DexRegisterLocation::Kind::kConstant, High32Bits(value));
719          DCHECK_LT(i, environment_size);
720        } else if (current->IsDoubleConstant()) {
721          int64_t value = bit_cast<int64_t, double>(current->AsDoubleConstant()->GetValue());
722          stack_map_stream_.AddDexRegisterEntry(
723              i, DexRegisterLocation::Kind::kConstant, Low32Bits(value));
724          stack_map_stream_.AddDexRegisterEntry(
725              ++i, DexRegisterLocation::Kind::kConstant, High32Bits(value));
726          DCHECK_LT(i, environment_size);
727        } else if (current->IsIntConstant()) {
728          int32_t value = current->AsIntConstant()->GetValue();
729          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kConstant, value);
730        } else if (current->IsNullConstant()) {
731          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kConstant, 0);
732        } else {
733          DCHECK(current->IsFloatConstant()) << current->DebugName();
734          int32_t value = bit_cast<int32_t, float>(current->AsFloatConstant()->GetValue());
735          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kConstant, value);
736        }
737        break;
738      }
739
740      case Location::kStackSlot: {
741        stack_map_stream_.AddDexRegisterEntry(
742            i, DexRegisterLocation::Kind::kInStack, location.GetStackIndex());
743        break;
744      }
745
746      case Location::kDoubleStackSlot: {
747        stack_map_stream_.AddDexRegisterEntry(
748            i, DexRegisterLocation::Kind::kInStack, location.GetStackIndex());
749        stack_map_stream_.AddDexRegisterEntry(
750            ++i, DexRegisterLocation::Kind::kInStack, location.GetHighStackIndex(kVRegSize));
751        DCHECK_LT(i, environment_size);
752        break;
753      }
754
755      case Location::kRegister : {
756        int id = location.reg();
757        if (slow_path != nullptr && slow_path->IsCoreRegisterSaved(id)) {
758          uint32_t offset = slow_path->GetStackOffsetOfCoreRegister(id);
759          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInStack, offset);
760          if (current->GetType() == Primitive::kPrimLong) {
761            stack_map_stream_.AddDexRegisterEntry(
762                ++i, DexRegisterLocation::Kind::kInStack, offset + kVRegSize);
763            DCHECK_LT(i, environment_size);
764          }
765        } else {
766          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInRegister, id);
767          if (current->GetType() == Primitive::kPrimLong) {
768            stack_map_stream_.AddDexRegisterEntry(++i, DexRegisterLocation::Kind::kInRegister, id);
769            DCHECK_LT(i, environment_size);
770          }
771        }
772        break;
773      }
774
775      case Location::kFpuRegister : {
776        int id = location.reg();
777        if (slow_path != nullptr && slow_path->IsFpuRegisterSaved(id)) {
778          uint32_t offset = slow_path->GetStackOffsetOfFpuRegister(id);
779          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInStack, offset);
780          if (current->GetType() == Primitive::kPrimDouble) {
781            stack_map_stream_.AddDexRegisterEntry(
782                ++i, DexRegisterLocation::Kind::kInStack, offset + kVRegSize);
783            DCHECK_LT(i, environment_size);
784          }
785        } else {
786          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInFpuRegister, id);
787          if (current->GetType() == Primitive::kPrimDouble) {
788            stack_map_stream_.AddDexRegisterEntry(
789                ++i, DexRegisterLocation::Kind::kInFpuRegister, id);
790            DCHECK_LT(i, environment_size);
791          }
792        }
793        break;
794      }
795
796      case Location::kFpuRegisterPair : {
797        int low = location.low();
798        int high = location.high();
799        if (slow_path != nullptr && slow_path->IsFpuRegisterSaved(low)) {
800          uint32_t offset = slow_path->GetStackOffsetOfFpuRegister(low);
801          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInStack, offset);
802        } else {
803          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInFpuRegister, low);
804        }
805        if (slow_path != nullptr && slow_path->IsFpuRegisterSaved(high)) {
806          uint32_t offset = slow_path->GetStackOffsetOfFpuRegister(high);
807          stack_map_stream_.AddDexRegisterEntry(++i, DexRegisterLocation::Kind::kInStack, offset);
808        } else {
809          stack_map_stream_.AddDexRegisterEntry(
810              ++i, DexRegisterLocation::Kind::kInFpuRegister, high);
811        }
812        DCHECK_LT(i, environment_size);
813        break;
814      }
815
816      case Location::kRegisterPair : {
817        int low = location.low();
818        int high = location.high();
819        if (slow_path != nullptr && slow_path->IsCoreRegisterSaved(low)) {
820          uint32_t offset = slow_path->GetStackOffsetOfCoreRegister(low);
821          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInStack, offset);
822        } else {
823          stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kInRegister, low);
824        }
825        if (slow_path != nullptr && slow_path->IsCoreRegisterSaved(high)) {
826          uint32_t offset = slow_path->GetStackOffsetOfCoreRegister(high);
827          stack_map_stream_.AddDexRegisterEntry(++i, DexRegisterLocation::Kind::kInStack, offset);
828        } else {
829          stack_map_stream_.AddDexRegisterEntry(
830              ++i, DexRegisterLocation::Kind::kInRegister, high);
831        }
832        DCHECK_LT(i, environment_size);
833        break;
834      }
835
836      case Location::kInvalid: {
837        stack_map_stream_.AddDexRegisterEntry(i, DexRegisterLocation::Kind::kNone, 0);
838        break;
839      }
840
841      default:
842        LOG(FATAL) << "Unexpected kind " << location.GetKind();
843    }
844  }
845  stack_map_stream_.EndStackMapEntry();
846}
847
848bool CodeGenerator::CanMoveNullCheckToUser(HNullCheck* null_check) {
849  HInstruction* first_next_not_move = null_check->GetNextDisregardingMoves();
850
851  return (first_next_not_move != nullptr)
852      && first_next_not_move->CanDoImplicitNullCheckOn(null_check->InputAt(0));
853}
854
855void CodeGenerator::MaybeRecordImplicitNullCheck(HInstruction* instr) {
856  // If we are from a static path don't record the pc as we can't throw NPE.
857  // NB: having the checks here makes the code much less verbose in the arch
858  // specific code generators.
859  if (instr->IsStaticFieldSet() || instr->IsStaticFieldGet()) {
860    return;
861  }
862
863  if (!compiler_options_.GetImplicitNullChecks()) {
864    return;
865  }
866
867  if (!instr->CanDoImplicitNullCheckOn(instr->InputAt(0))) {
868    return;
869  }
870
871  // Find the first previous instruction which is not a move.
872  HInstruction* first_prev_not_move = instr->GetPreviousDisregardingMoves();
873
874  // If the instruction is a null check it means that `instr` is the first user
875  // and needs to record the pc.
876  if (first_prev_not_move != nullptr && first_prev_not_move->IsNullCheck()) {
877    HNullCheck* null_check = first_prev_not_move->AsNullCheck();
878    // TODO: The parallel moves modify the environment. Their changes need to be reverted
879    // otherwise the stack maps at the throw point will not be correct.
880    RecordPcInfo(null_check, null_check->GetDexPc());
881  }
882}
883
884void CodeGenerator::ClearSpillSlotsFromLoopPhisInStackMap(HSuspendCheck* suspend_check) const {
885  LocationSummary* locations = suspend_check->GetLocations();
886  HBasicBlock* block = suspend_check->GetBlock();
887  DCHECK(block->GetLoopInformation()->GetSuspendCheck() == suspend_check);
888  DCHECK(block->IsLoopHeader());
889
890  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
891    HInstruction* current = it.Current();
892    LiveInterval* interval = current->GetLiveInterval();
893    // We only need to clear bits of loop phis containing objects and allocated in register.
894    // Loop phis allocated on stack already have the object in the stack.
895    if (current->GetType() == Primitive::kPrimNot
896        && interval->HasRegister()
897        && interval->HasSpillSlot()) {
898      locations->ClearStackBit(interval->GetSpillSlot() / kVRegSize);
899    }
900  }
901}
902
903void CodeGenerator::EmitParallelMoves(Location from1,
904                                      Location to1,
905                                      Primitive::Type type1,
906                                      Location from2,
907                                      Location to2,
908                                      Primitive::Type type2) {
909  HParallelMove parallel_move(GetGraph()->GetArena());
910  parallel_move.AddMove(from1, to1, type1, nullptr);
911  parallel_move.AddMove(from2, to2, type2, nullptr);
912  GetMoveResolver()->EmitNativeCode(&parallel_move);
913}
914
915void SlowPathCode::RecordPcInfo(CodeGenerator* codegen, HInstruction* instruction, uint32_t dex_pc) {
916  codegen->RecordPcInfo(instruction, dex_pc, this);
917}
918
919void SlowPathCode::SaveLiveRegisters(CodeGenerator* codegen, LocationSummary* locations) {
920  RegisterSet* register_set = locations->GetLiveRegisters();
921  size_t stack_offset = codegen->GetFirstRegisterSlotInSlowPath();
922  for (size_t i = 0, e = codegen->GetNumberOfCoreRegisters(); i < e; ++i) {
923    if (!codegen->IsCoreCalleeSaveRegister(i)) {
924      if (register_set->ContainsCoreRegister(i)) {
925        // If the register holds an object, update the stack mask.
926        if (locations->RegisterContainsObject(i)) {
927          locations->SetStackBit(stack_offset / kVRegSize);
928        }
929        DCHECK_LT(stack_offset, codegen->GetFrameSize() - codegen->FrameEntrySpillSize());
930        DCHECK_LT(i, kMaximumNumberOfExpectedRegisters);
931        saved_core_stack_offsets_[i] = stack_offset;
932        stack_offset += codegen->SaveCoreRegister(stack_offset, i);
933      }
934    }
935  }
936
937  for (size_t i = 0, e = codegen->GetNumberOfFloatingPointRegisters(); i < e; ++i) {
938    if (!codegen->IsFloatingPointCalleeSaveRegister(i)) {
939      if (register_set->ContainsFloatingPointRegister(i)) {
940        DCHECK_LT(stack_offset, codegen->GetFrameSize() - codegen->FrameEntrySpillSize());
941        DCHECK_LT(i, kMaximumNumberOfExpectedRegisters);
942        saved_fpu_stack_offsets_[i] = stack_offset;
943        stack_offset += codegen->SaveFloatingPointRegister(stack_offset, i);
944      }
945    }
946  }
947}
948
949void SlowPathCode::RestoreLiveRegisters(CodeGenerator* codegen, LocationSummary* locations) {
950  RegisterSet* register_set = locations->GetLiveRegisters();
951  size_t stack_offset = codegen->GetFirstRegisterSlotInSlowPath();
952  for (size_t i = 0, e = codegen->GetNumberOfCoreRegisters(); i < e; ++i) {
953    if (!codegen->IsCoreCalleeSaveRegister(i)) {
954      if (register_set->ContainsCoreRegister(i)) {
955        DCHECK_LT(stack_offset, codegen->GetFrameSize() - codegen->FrameEntrySpillSize());
956        stack_offset += codegen->RestoreCoreRegister(stack_offset, i);
957      }
958    }
959  }
960
961  for (size_t i = 0, e = codegen->GetNumberOfFloatingPointRegisters(); i < e; ++i) {
962    if (!codegen->IsFloatingPointCalleeSaveRegister(i)) {
963      if (register_set->ContainsFloatingPointRegister(i)) {
964        DCHECK_LT(stack_offset, codegen->GetFrameSize() - codegen->FrameEntrySpillSize());
965        stack_offset += codegen->RestoreFloatingPointRegister(stack_offset, i);
966      }
967    }
968  }
969}
970
971}  // namespace art
972