code_generator.cc revision 92a73aef279be78e3c2b04db1713076183933436 
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_x86.h"
21#include "code_generator_x86_64.h"
22#include "compiled_method.h"
23#include "dex/verified_method.h"
24#include "driver/dex_compilation_unit.h"
25#include "gc_map_builder.h"
26#include "leb128.h"
27#include "mapping_table.h"
28#include "ssa_liveness_analysis.h"
29#include "utils/assembler.h"
30#include "verifier/dex_gc_map.h"
31#include "vmap_table.h"
32
33namespace art {
34
35void CodeGenerator::CompileBaseline(CodeAllocator* allocator, bool is_leaf) {
36  const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
37  DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
38  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
39  Initialize();
40
41  DCHECK_EQ(frame_size_, kUninitializedFrameSize);
42  if (!is_leaf) {
43    MarkNotLeaf();
44  }
45  ComputeFrameSize(GetGraph()->GetNumberOfLocalVRegs()
46                     + GetGraph()->GetNumberOfTemporaries()
47                     + 1 /* filler */,
48                   0, /* the baseline compiler does not have live registers at slow path */
49                   GetGraph()->GetMaximumNumberOfOutVRegs()
50                     + 1 /* current method */);
51  GenerateFrameEntry();
52
53  HGraphVisitor* location_builder = GetLocationBuilder();
54  HGraphVisitor* instruction_visitor = GetInstructionVisitor();
55  for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
56    HBasicBlock* block = blocks.Get(i);
57    Bind(block);
58    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
59      HInstruction* current = it.Current();
60      current->Accept(location_builder);
61      InitLocations(current);
62      current->Accept(instruction_visitor);
63    }
64  }
65  GenerateSlowPaths();
66
67  size_t code_size = GetAssembler()->CodeSize();
68  uint8_t* buffer = allocator->Allocate(code_size);
69  MemoryRegion code(buffer, code_size);
70  GetAssembler()->FinalizeInstructions(code);
71}
72
73void CodeGenerator::CompileOptimized(CodeAllocator* allocator) {
74  // The frame size has already been computed during register allocation.
75  DCHECK_NE(frame_size_, kUninitializedFrameSize);
76  const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
77  DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
78  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
79  Initialize();
80
81  GenerateFrameEntry();
82  HGraphVisitor* instruction_visitor = GetInstructionVisitor();
83  for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
84    HBasicBlock* block = blocks.Get(i);
85    Bind(block);
86    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
87      HInstruction* current = it.Current();
88      current->Accept(instruction_visitor);
89    }
90  }
91  GenerateSlowPaths();
92
93  size_t code_size = GetAssembler()->CodeSize();
94  uint8_t* buffer = allocator->Allocate(code_size);
95  MemoryRegion code(buffer, code_size);
96  GetAssembler()->FinalizeInstructions(code);
97}
98
99void CodeGenerator::GenerateSlowPaths() {
100  for (size_t i = 0, e = slow_paths_.Size(); i < e; ++i) {
101    slow_paths_.Get(i)->EmitNativeCode(this);
102  }
103}
104
105size_t CodeGenerator::FindFreeEntry(bool* array, size_t length) {
106  for (size_t i = 0; i < length; ++i) {
107    if (!array[i]) {
108      array[i] = true;
109      return i;
110    }
111  }
112  LOG(FATAL) << "Could not find a register in baseline register allocator";
113  return -1;
114}
115
116void CodeGenerator::ComputeFrameSize(size_t number_of_spill_slots,
117                                     size_t maximum_number_of_live_registers,
118                                     size_t number_of_out_slots) {
119  first_register_slot_in_slow_path_ = (number_of_out_slots + number_of_spill_slots) * kVRegSize;
120
121  SetFrameSize(RoundUp(
122      number_of_spill_slots * kVRegSize
123      + number_of_out_slots * kVRegSize
124      + maximum_number_of_live_registers * GetWordSize()
125      + FrameEntrySpillSize(),
126      kStackAlignment));
127}
128
129Location CodeGenerator::GetTemporaryLocation(HTemporary* temp) const {
130  uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
131  // Use the temporary region (right below the dex registers).
132  int32_t slot = GetFrameSize() - FrameEntrySpillSize()
133                                - kVRegSize  // filler
134                                - (number_of_locals * kVRegSize)
135                                - ((1 + temp->GetIndex()) * kVRegSize);
136  return Location::StackSlot(slot);
137}
138
139int32_t CodeGenerator::GetStackSlot(HLocal* local) const {
140  uint16_t reg_number = local->GetRegNumber();
141  uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
142  if (reg_number >= number_of_locals) {
143    // Local is a parameter of the method. It is stored in the caller's frame.
144    return GetFrameSize() + kVRegSize  // ART method
145                          + (reg_number - number_of_locals) * kVRegSize;
146  } else {
147    // Local is a temporary in this method. It is stored in this method's frame.
148    return GetFrameSize() - FrameEntrySpillSize()
149                          - kVRegSize  // filler.
150                          - (number_of_locals * kVRegSize)
151                          + (reg_number * kVRegSize);
152  }
153}
154
155void CodeGenerator::AllocateRegistersLocally(HInstruction* instruction) const {
156  LocationSummary* locations = instruction->GetLocations();
157  if (locations == nullptr) return;
158
159  for (size_t i = 0, e = GetNumberOfCoreRegisters(); i < e; ++i) {
160    blocked_core_registers_[i] = false;
161  }
162
163  for (size_t i = 0, e = GetNumberOfFloatingPointRegisters(); i < e; ++i) {
164    blocked_fpu_registers_[i] = false;
165  }
166
167  for (size_t i = 0, e = number_of_register_pairs_; i < e; ++i) {
168    blocked_register_pairs_[i] = false;
169  }
170
171  // Mark all fixed input, temp and output registers as used.
172  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
173    Location loc = locations->InAt(i);
174    // The DCHECKS below check that a register is not specified twice in
175    // the summary.
176    if (loc.IsRegister()) {
177      DCHECK(!blocked_core_registers_[loc.reg()]);
178      blocked_core_registers_[loc.reg()] = true;
179    } else if (loc.IsFpuRegister()) {
180      DCHECK(!blocked_fpu_registers_[loc.reg()]);
181      blocked_fpu_registers_[loc.reg()] = true;
182    } else if (loc.IsRegisterPair()) {
183      DCHECK(!blocked_core_registers_[loc.AsRegisterPairLow<int>()]);
184      blocked_core_registers_[loc.AsRegisterPairLow<int>()] = true;
185      DCHECK(!blocked_core_registers_[loc.AsRegisterPairHigh<int>()]);
186      blocked_core_registers_[loc.AsRegisterPairHigh<int>()] = true;
187    }
188  }
189
190  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
191    Location loc = locations->GetTemp(i);
192    if (loc.IsRegister()) {
193      // Check that a register is not specified twice in the summary.
194      DCHECK(!blocked_core_registers_[loc.reg()]);
195      blocked_core_registers_[loc.reg()] = true;
196    } else {
197      DCHECK_EQ(loc.GetPolicy(), Location::kRequiresRegister);
198    }
199  }
200
201  SetupBlockedRegisters();
202
203  // Allocate all unallocated input locations.
204  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
205    Location loc = locations->InAt(i);
206    HInstruction* input = instruction->InputAt(i);
207    if (loc.IsUnallocated()) {
208      if ((loc.GetPolicy() == Location::kRequiresRegister)
209          || (loc.GetPolicy() == Location::kRequiresFpuRegister)) {
210        loc = AllocateFreeRegister(input->GetType());
211      } else {
212        DCHECK_EQ(loc.GetPolicy(), Location::kAny);
213        HLoadLocal* load = input->AsLoadLocal();
214        if (load != nullptr) {
215          loc = GetStackLocation(load);
216        } else {
217          loc = AllocateFreeRegister(input->GetType());
218        }
219      }
220      locations->SetInAt(i, loc);
221    }
222  }
223
224  // Allocate all unallocated temp locations.
225  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
226    Location loc = locations->GetTemp(i);
227    if (loc.IsUnallocated()) {
228      DCHECK_EQ(loc.GetPolicy(), Location::kRequiresRegister);
229      // TODO: Adjust handling of temps. We currently consider temps to use
230      // core registers. They may also use floating point registers at some point.
231      loc = AllocateFreeRegister(Primitive::kPrimInt);
232      locations->SetTempAt(i, loc);
233    }
234  }
235  Location result_location = locations->Out();
236  if (result_location.IsUnallocated()) {
237    switch (result_location.GetPolicy()) {
238      case Location::kAny:
239      case Location::kRequiresRegister:
240      case Location::kRequiresFpuRegister:
241        result_location = AllocateFreeRegister(instruction->GetType());
242        break;
243      case Location::kSameAsFirstInput:
244        result_location = locations->InAt(0);
245        break;
246    }
247    locations->SetOut(result_location);
248  }
249}
250
251void CodeGenerator::InitLocations(HInstruction* instruction) {
252  if (instruction->GetLocations() == nullptr) {
253    if (instruction->IsTemporary()) {
254      HInstruction* previous = instruction->GetPrevious();
255      Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
256      Move(previous, temp_location, instruction);
257      previous->GetLocations()->SetOut(temp_location);
258    }
259    return;
260  }
261  AllocateRegistersLocally(instruction);
262  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
263    Location location = instruction->GetLocations()->InAt(i);
264    if (location.IsValid()) {
265      // Move the input to the desired location.
266      Move(instruction->InputAt(i), location, instruction);
267    }
268  }
269}
270
271bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
272  // We currently iterate over the block in insertion order.
273  return current->GetBlockId() + 1 == next->GetBlockId();
274}
275
276CodeGenerator* CodeGenerator::Create(ArenaAllocator* allocator,
277                                     HGraph* graph,
278                                     InstructionSet instruction_set) {
279  switch (instruction_set) {
280    case kArm:
281    case kThumb2: {
282      return new (allocator) arm::CodeGeneratorARM(graph);
283    }
284    case kMips:
285      return nullptr;
286    case kX86: {
287      return new (allocator) x86::CodeGeneratorX86(graph);
288    }
289    case kX86_64: {
290      return new (allocator) x86_64::CodeGeneratorX86_64(graph);
291    }
292    default:
293      return nullptr;
294  }
295}
296
297void CodeGenerator::BuildNativeGCMap(
298    std::vector<uint8_t>* data, const DexCompilationUnit& dex_compilation_unit) const {
299  const std::vector<uint8_t>& gc_map_raw =
300      dex_compilation_unit.GetVerifiedMethod()->GetDexGcMap();
301  verifier::DexPcToReferenceMap dex_gc_map(&(gc_map_raw)[0]);
302
303  uint32_t max_native_offset = 0;
304  for (size_t i = 0; i < pc_infos_.Size(); i++) {
305    uint32_t native_offset = pc_infos_.Get(i).native_pc;
306    if (native_offset > max_native_offset) {
307      max_native_offset = native_offset;
308    }
309  }
310
311  GcMapBuilder builder(data, pc_infos_.Size(), max_native_offset, dex_gc_map.RegWidth());
312  for (size_t i = 0; i < pc_infos_.Size(); i++) {
313    struct PcInfo pc_info = pc_infos_.Get(i);
314    uint32_t native_offset = pc_info.native_pc;
315    uint32_t dex_pc = pc_info.dex_pc;
316    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
317    CHECK(references != NULL) << "Missing ref for dex pc 0x" << std::hex << dex_pc;
318    builder.AddEntry(native_offset, references);
319  }
320}
321
322void CodeGenerator::BuildMappingTable(std::vector<uint8_t>* data, SrcMap* src_map) const {
323  uint32_t pc2dex_data_size = 0u;
324  uint32_t pc2dex_entries = pc_infos_.Size();
325  uint32_t pc2dex_offset = 0u;
326  int32_t pc2dex_dalvik_offset = 0;
327  uint32_t dex2pc_data_size = 0u;
328  uint32_t dex2pc_entries = 0u;
329
330  if (src_map != nullptr) {
331    src_map->reserve(pc2dex_entries);
332  }
333
334  // We currently only have pc2dex entries.
335  for (size_t i = 0; i < pc2dex_entries; i++) {
336    struct PcInfo pc_info = pc_infos_.Get(i);
337    pc2dex_data_size += UnsignedLeb128Size(pc_info.native_pc - pc2dex_offset);
338    pc2dex_data_size += SignedLeb128Size(pc_info.dex_pc - pc2dex_dalvik_offset);
339    pc2dex_offset = pc_info.native_pc;
340    pc2dex_dalvik_offset = pc_info.dex_pc;
341    if (src_map != nullptr) {
342      src_map->push_back(SrcMapElem({pc2dex_offset, pc2dex_dalvik_offset}));
343    }
344  }
345
346  uint32_t total_entries = pc2dex_entries + dex2pc_entries;
347  uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
348  uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
349  data->resize(data_size);
350
351  uint8_t* data_ptr = &(*data)[0];
352  uint8_t* write_pos = data_ptr;
353  write_pos = EncodeUnsignedLeb128(write_pos, total_entries);
354  write_pos = EncodeUnsignedLeb128(write_pos, pc2dex_entries);
355  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size);
356  uint8_t* write_pos2 = write_pos + pc2dex_data_size;
357
358  pc2dex_offset = 0u;
359  pc2dex_dalvik_offset = 0u;
360  for (size_t i = 0; i < pc2dex_entries; i++) {
361    struct PcInfo pc_info = pc_infos_.Get(i);
362    DCHECK(pc2dex_offset <= pc_info.native_pc);
363    write_pos = EncodeUnsignedLeb128(write_pos, pc_info.native_pc - pc2dex_offset);
364    write_pos = EncodeSignedLeb128(write_pos, pc_info.dex_pc - pc2dex_dalvik_offset);
365    pc2dex_offset = pc_info.native_pc;
366    pc2dex_dalvik_offset = pc_info.dex_pc;
367  }
368  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size + pc2dex_data_size);
369  DCHECK_EQ(static_cast<size_t>(write_pos2 - data_ptr), data_size);
370
371  if (kIsDebugBuild) {
372    // Verify the encoded table holds the expected data.
373    MappingTable table(data_ptr);
374    CHECK_EQ(table.TotalSize(), total_entries);
375    CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
376    auto it = table.PcToDexBegin();
377    auto it2 = table.DexToPcBegin();
378    for (size_t i = 0; i < pc2dex_entries; i++) {
379      struct PcInfo pc_info = pc_infos_.Get(i);
380      CHECK_EQ(pc_info.native_pc, it.NativePcOffset());
381      CHECK_EQ(pc_info.dex_pc, it.DexPc());
382      ++it;
383    }
384    CHECK(it == table.PcToDexEnd());
385    CHECK(it2 == table.DexToPcEnd());
386  }
387}
388
389void CodeGenerator::BuildVMapTable(std::vector<uint8_t>* data) const {
390  Leb128EncodingVector vmap_encoder;
391  // We currently don't use callee-saved registers.
392  size_t size = 0 + 1 /* marker */ + 0;
393  vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
394  vmap_encoder.PushBackUnsigned(size);
395  vmap_encoder.PushBackUnsigned(VmapTable::kAdjustedFpMarker);
396
397  *data = vmap_encoder.GetData();
398}
399
400void CodeGenerator::BuildStackMaps(std::vector<uint8_t>* data) {
401  uint32_t size = stack_map_stream_.ComputeNeededSize();
402  data->resize(size);
403  MemoryRegion region(data->data(), size);
404  stack_map_stream_.FillIn(region);
405}
406
407void CodeGenerator::RecordPcInfo(HInstruction* instruction, uint32_t dex_pc) {
408  // Collect PC infos for the mapping table.
409  struct PcInfo pc_info;
410  pc_info.dex_pc = dex_pc;
411  pc_info.native_pc = GetAssembler()->CodeSize();
412  pc_infos_.Add(pc_info);
413
414  // Populate stack map information.
415
416  if (instruction == nullptr) {
417    // For stack overflow checks.
418    stack_map_stream_.AddStackMapEntry(dex_pc, pc_info.native_pc, 0, 0, 0, 0);
419    return;
420  }
421
422  LocationSummary* locations = instruction->GetLocations();
423  HEnvironment* environment = instruction->GetEnvironment();
424
425  size_t environment_size = instruction->EnvironmentSize();
426
427  size_t register_mask = 0;
428  size_t inlining_depth = 0;
429  stack_map_stream_.AddStackMapEntry(
430      dex_pc, pc_info.native_pc, register_mask,
431      locations->GetStackMask(), environment_size, inlining_depth);
432
433  // Walk over the environment, and record the location of dex registers.
434  for (size_t i = 0; i < environment_size; ++i) {
435    HInstruction* current = environment->GetInstructionAt(i);
436    if (current == nullptr) {
437      stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kNone, 0);
438      continue;
439    }
440
441    Location location = locations->GetEnvironmentAt(i);
442    switch (location.GetKind()) {
443      case Location::kConstant: {
444        DCHECK(current == location.GetConstant());
445        if (current->IsLongConstant()) {
446          int64_t value = current->AsLongConstant()->GetValue();
447          stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kConstant, Low32Bits(value));
448          stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kConstant, High32Bits(value));
449          ++i;
450          DCHECK_LT(i, environment_size);
451        } else {
452          DCHECK(current->IsIntConstant());
453          int32_t value = current->AsIntConstant()->GetValue();
454          stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kConstant, value);
455        }
456        break;
457      }
458
459      case Location::kStackSlot: {
460        stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kInStack, location.GetStackIndex());
461        break;
462      }
463
464      case Location::kDoubleStackSlot: {
465        stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kInStack, location.GetStackIndex());
466        stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kInStack,
467                                              location.GetHighStackIndex(kVRegSize));
468        ++i;
469        DCHECK_LT(i, environment_size);
470        break;
471      }
472
473      case Location::kRegister : {
474        int id = location.reg();
475        stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kInRegister, id);
476        if (current->GetType() == Primitive::kPrimDouble
477            || current->GetType() == Primitive::kPrimLong) {
478          stack_map_stream_.AddDexRegisterEntry(DexRegisterMap::kInRegister, id);
479          ++i;
480          DCHECK_LT(i, environment_size);
481        }
482        break;
483      }
484
485      default:
486        LOG(FATAL) << "Unexpected kind " << location.GetKind();
487    }
488  }
489}
490
491size_t CodeGenerator::GetStackOffsetOfSavedRegister(size_t index) {
492  return first_register_slot_in_slow_path_ + index * GetWordSize();
493}
494
495void CodeGenerator::SaveLiveRegisters(LocationSummary* locations) {
496  RegisterSet* register_set = locations->GetLiveRegisters();
497  uint32_t count = 0;
498  for (size_t i = 0, e = GetNumberOfCoreRegisters(); i < e; ++i) {
499    if (register_set->ContainsCoreRegister(i)) {
500      size_t stack_offset = GetStackOffsetOfSavedRegister(count);
501      ++count;
502      SaveCoreRegister(Location::StackSlot(stack_offset), i);
503      // If the register holds an object, update the stack mask.
504      if (locations->RegisterContainsObject(i)) {
505        locations->SetStackBit(stack_offset / kVRegSize);
506      }
507    }
508  }
509
510  for (size_t i = 0, e = GetNumberOfFloatingPointRegisters(); i < e; ++i) {
511    if (register_set->ContainsFloatingPointRegister(i)) {
512      LOG(FATAL) << "Unimplemented";
513    }
514  }
515}
516
517void CodeGenerator::RestoreLiveRegisters(LocationSummary* locations) {
518  RegisterSet* register_set = locations->GetLiveRegisters();
519  uint32_t count = 0;
520  for (size_t i = 0, e = GetNumberOfCoreRegisters(); i < e; ++i) {
521    if (register_set->ContainsCoreRegister(i)) {
522      size_t stack_offset = GetStackOffsetOfSavedRegister(count);
523      ++count;
524      RestoreCoreRegister(Location::StackSlot(stack_offset), i);
525    }
526  }
527
528  for (size_t i = 0, e = GetNumberOfFloatingPointRegisters(); i < e; ++i) {
529    if (register_set->ContainsFloatingPointRegister(i)) {
530      LOG(FATAL) << "Unimplemented";
531    }
532  }
533}
534
535void CodeGenerator::ClearSpillSlotsFromLoopPhisInStackMap(HSuspendCheck* suspend_check) const {
536  LocationSummary* locations = suspend_check->GetLocations();
537  HBasicBlock* block = suspend_check->GetBlock();
538  DCHECK(block->GetLoopInformation()->GetSuspendCheck() == suspend_check);
539  DCHECK(block->IsLoopHeader());
540
541  for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
542    HInstruction* current = it.Current();
543    LiveInterval* interval = current->GetLiveInterval();
544    // We only need to clear bits of loop phis containing objects and allocated in register.
545    // Loop phis allocated on stack already have the object in the stack.
546    if (current->GetType() == Primitive::kPrimNot
547        && interval->HasRegister()
548        && interval->HasSpillSlot()) {
549      locations->ClearStackBit(interval->GetSpillSlot() / kVRegSize);
550    }
551  }
552}
553
554}  // namespace art
555