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 
38 namespace art {
39 
40 // Return whether a location is consistent with a type.
CheckType(Primitive::Type type,Location location)41 static 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.
CheckTypeConsistency(HInstruction * instruction)77 static 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 
GetCacheOffset(uint32_t index)114 size_t CodeGenerator::GetCacheOffset(uint32_t index) {
115   return mirror::ObjectArray<mirror::Object>::OffsetOfElement(index).SizeValue();
116 }
117 
GetCachePointerOffset(uint32_t index)118 size_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 
CompileBaseline(CodeAllocator * allocator,bool is_leaf)123 void 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 
GoesToNextBlock(HBasicBlock * current,HBasicBlock * next) const140 bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
141   DCHECK_EQ(block_order_->Get(current_block_index_), current);
142   return GetNextBlockToEmit() == FirstNonEmptyBlock(next);
143 }
144 
GetNextBlockToEmit() const145 HBasicBlock* 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 
FirstNonEmptyBlock(HBasicBlock * block) const155 HBasicBlock* CodeGenerator::FirstNonEmptyBlock(HBasicBlock* block) const {
156   while (block->IsSingleGoto()) {
157     block = block->GetSuccessors().Get(0);
158   }
159   return block;
160 }
161 
CompileInternal(CodeAllocator * allocator,bool is_baseline)162 void 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 
CompileOptimized(CodeAllocator * allocator)194 void 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 
Finalize(CodeAllocator * allocator)202 void 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 
FindFreeEntry(bool * array,size_t length)210 size_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 
FindTwoFreeConsecutiveAlignedEntries(bool * array,size_t length)221 size_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 
InitializeCodeGeneration(size_t number_of_spill_slots,size_t maximum_number_of_live_core_registers,size_t maximum_number_of_live_fp_registers,size_t number_of_out_slots,const GrowableArray<HBasicBlock * > & block_order)233 void 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 
GetTemporaryLocation(HTemporary * temp) const261 Location 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 
GetStackSlot(HLocal * local) const274 int32_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 
BlockIfInRegister(Location location,bool is_out) const291 void 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 
AllocateRegistersLocally(HInstruction * instruction) const314 void 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 
InitLocationsBaseline(HInstruction * instruction)404 void 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 
AllocateLocations(HInstruction * instruction)431 void 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 
Create(HGraph * graph,InstructionSet instruction_set,const InstructionSetFeatures & isa_features,const CompilerOptions & compiler_options)445 CodeGenerator* 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 
BuildNativeGCMap(std::vector<uint8_t> * data,const DexCompilationUnit & dex_compilation_unit) const483 void 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 
BuildSourceMap(DefaultSrcMap * src_map) const508 void 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 
BuildMappingTable(std::vector<uint8_t> * data) const517 void 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 
BuildVMapTable(std::vector<uint8_t> * data) const616 void 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 
BuildStackMaps(std::vector<uint8_t> * data)627 void 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 
RecordPcInfo(HInstruction * instruction,uint32_t dex_pc,SlowPathCode * slow_path)634 void 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 
CanMoveNullCheckToUser(HNullCheck * null_check)848 bool 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 
MaybeRecordImplicitNullCheck(HInstruction * instr)855 void 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 
ClearSpillSlotsFromLoopPhisInStackMap(HSuspendCheck * suspend_check) const884 void 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 
EmitParallelMoves(Location from1,Location to1,Primitive::Type type1,Location from2,Location to2,Primitive::Type type2)903 void 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 
RecordPcInfo(CodeGenerator * codegen,HInstruction * instruction,uint32_t dex_pc)915 void SlowPathCode::RecordPcInfo(CodeGenerator* codegen, HInstruction* instruction, uint32_t dex_pc) {
916   codegen->RecordPcInfo(instruction, dex_pc, this);
917 }
918 
SaveLiveRegisters(CodeGenerator * codegen,LocationSummary * locations)919 void 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 
RestoreLiveRegisters(CodeGenerator * codegen,LocationSummary * locations)949 void 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