code_generator.cc revision e3ea83811d47152c00abea24a9b420651a33b496 
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 "utils/assembler.h"
29#include "verifier/dex_gc_map.h"
30#include "vmap_table.h"
31
32namespace art {
33
34void CodeGenerator::CompileBaseline(CodeAllocator* allocator, bool is_leaf) {
35  const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
36  DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
37  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
38  block_labels_.SetSize(blocks.Size());
39
40  DCHECK_EQ(frame_size_, kUninitializedFrameSize);
41  if (!is_leaf) {
42    MarkNotLeaf();
43  }
44  ComputeFrameSize(GetGraph()->GetMaximumNumberOfOutVRegs()
45                   + GetGraph()->GetNumberOfLocalVRegs()
46                   + GetGraph()->GetNumberOfTemporaries()
47                   + 1 /* filler */);
48  GenerateFrameEntry();
49
50  for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
51    HBasicBlock* block = blocks.Get(i);
52    Bind(GetLabelOf(block));
53    HGraphVisitor* location_builder = GetLocationBuilder();
54    HGraphVisitor* instruction_visitor = GetInstructionVisitor();
55    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
56      HInstruction* current = it.Current();
57      current->Accept(location_builder);
58      InitLocations(current);
59      current->Accept(instruction_visitor);
60    }
61  }
62  GenerateSlowPaths();
63
64  size_t code_size = GetAssembler()->CodeSize();
65  uint8_t* buffer = allocator->Allocate(code_size);
66  MemoryRegion code(buffer, code_size);
67  GetAssembler()->FinalizeInstructions(code);
68}
69
70void CodeGenerator::CompileOptimized(CodeAllocator* allocator) {
71  // The frame size has already been computed during register allocation.
72  DCHECK_NE(frame_size_, kUninitializedFrameSize);
73  const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
74  DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
75  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
76  block_labels_.SetSize(blocks.Size());
77
78  GenerateFrameEntry();
79  for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
80    HBasicBlock* block = blocks.Get(i);
81    Bind(GetLabelOf(block));
82    HGraphVisitor* instruction_visitor = GetInstructionVisitor();
83    for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
84      HInstruction* current = it.Current();
85      current->Accept(instruction_visitor);
86    }
87  }
88  GenerateSlowPaths();
89
90  size_t code_size = GetAssembler()->CodeSize();
91  uint8_t* buffer = allocator->Allocate(code_size);
92  MemoryRegion code(buffer, code_size);
93  GetAssembler()->FinalizeInstructions(code);
94}
95
96void CodeGenerator::GenerateSlowPaths() {
97  for (size_t i = 0, e = slow_paths_.Size(); i < e; ++i) {
98    slow_paths_.Get(i)->EmitNativeCode(this);
99  }
100}
101
102size_t CodeGenerator::AllocateFreeRegisterInternal(
103    bool* blocked_registers, size_t number_of_registers) const {
104  for (size_t regno = 0; regno < number_of_registers; regno++) {
105    if (!blocked_registers[regno]) {
106      blocked_registers[regno] = true;
107      return regno;
108    }
109  }
110  return -1;
111}
112
113void CodeGenerator::ComputeFrameSize(size_t number_of_spill_slots) {
114  SetFrameSize(RoundUp(
115      number_of_spill_slots * kVRegSize
116      + kVRegSize  // Art method
117      + FrameEntrySpillSize(),
118      kStackAlignment));
119}
120
121Location CodeGenerator::GetTemporaryLocation(HTemporary* temp) const {
122  uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
123  // Use the temporary region (right below the dex registers).
124  int32_t slot = GetFrameSize() - FrameEntrySpillSize()
125                                - kVRegSize  // filler
126                                - (number_of_locals * kVRegSize)
127                                - ((1 + temp->GetIndex()) * kVRegSize);
128  return Location::StackSlot(slot);
129}
130
131int32_t CodeGenerator::GetStackSlot(HLocal* local) const {
132  uint16_t reg_number = local->GetRegNumber();
133  uint16_t number_of_locals = GetGraph()->GetNumberOfLocalVRegs();
134  if (reg_number >= number_of_locals) {
135    // Local is a parameter of the method. It is stored in the caller's frame.
136    return GetFrameSize() + kVRegSize  // ART method
137                          + (reg_number - number_of_locals) * kVRegSize;
138  } else {
139    // Local is a temporary in this method. It is stored in this method's frame.
140    return GetFrameSize() - FrameEntrySpillSize()
141                          - kVRegSize  // filler.
142                          - (number_of_locals * kVRegSize)
143                          + (reg_number * kVRegSize);
144  }
145}
146
147void CodeGenerator::AllocateRegistersLocally(HInstruction* instruction) const {
148  LocationSummary* locations = instruction->GetLocations();
149  if (locations == nullptr) return;
150
151  for (size_t i = 0, e = GetNumberOfRegisters(); i < e; ++i) {
152    blocked_registers_[i] = false;
153  }
154
155  // Mark all fixed input, temp and output registers as used.
156  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
157    Location loc = locations->InAt(i);
158    if (loc.IsRegister()) {
159      // Check that a register is not specified twice in the summary.
160      DCHECK(!blocked_registers_[loc.GetEncoding()]);
161      blocked_registers_[loc.GetEncoding()] = true;
162    }
163  }
164
165  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
166    Location loc = locations->GetTemp(i);
167    if (loc.IsRegister()) {
168      // Check that a register is not specified twice in the summary.
169      DCHECK(!blocked_registers_[loc.GetEncoding()]);
170      blocked_registers_[loc.GetEncoding()] = true;
171    }
172  }
173
174  SetupBlockedRegisters(blocked_registers_);
175
176  // Allocate all unallocated input locations.
177  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
178    Location loc = locations->InAt(i);
179    HInstruction* input = instruction->InputAt(i);
180    if (loc.IsUnallocated()) {
181      if (loc.GetPolicy() == Location::kRequiresRegister) {
182        loc = Location::RegisterLocation(
183            AllocateFreeRegister(input->GetType(), blocked_registers_));
184      } else {
185        DCHECK_EQ(loc.GetPolicy(), Location::kAny);
186        HLoadLocal* load = input->AsLoadLocal();
187        if (load != nullptr) {
188          loc = GetStackLocation(load);
189        } else {
190          loc = Location::RegisterLocation(
191              AllocateFreeRegister(input->GetType(), blocked_registers_));
192        }
193      }
194      locations->SetInAt(i, loc);
195    }
196  }
197
198  // Allocate all unallocated temp locations.
199  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
200    Location loc = locations->GetTemp(i);
201    if (loc.IsUnallocated()) {
202      DCHECK_EQ(loc.GetPolicy(), Location::kRequiresRegister);
203      // TODO: Adjust handling of temps. We currently consider temps to use
204      // core registers. They may also use floating point registers at some point.
205      loc = Location::RegisterLocation(static_cast<ManagedRegister>(
206          AllocateFreeRegister(Primitive::kPrimInt, blocked_registers_)));
207      locations->SetTempAt(i, loc);
208    }
209  }
210  Location result_location = locations->Out();
211  if (result_location.IsUnallocated()) {
212    switch (result_location.GetPolicy()) {
213      case Location::kAny:
214      case Location::kRequiresRegister:
215        result_location = Location::RegisterLocation(
216            AllocateFreeRegister(instruction->GetType(), blocked_registers_));
217        break;
218      case Location::kSameAsFirstInput:
219        result_location = locations->InAt(0);
220        break;
221    }
222    locations->SetOut(result_location);
223  }
224}
225
226void CodeGenerator::InitLocations(HInstruction* instruction) {
227  if (instruction->GetLocations() == nullptr) {
228    if (instruction->IsTemporary()) {
229      HInstruction* previous = instruction->GetPrevious();
230      Location temp_location = GetTemporaryLocation(instruction->AsTemporary());
231      Move(previous, temp_location, instruction);
232      previous->GetLocations()->SetOut(temp_location);
233    }
234    return;
235  }
236  AllocateRegistersLocally(instruction);
237  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
238    Location location = instruction->GetLocations()->InAt(i);
239    if (location.IsValid()) {
240      // Move the input to the desired location.
241      Move(instruction->InputAt(i), location, instruction);
242    }
243  }
244}
245
246bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
247  // We currently iterate over the block in insertion order.
248  return current->GetBlockId() + 1 == next->GetBlockId();
249}
250
251Label* CodeGenerator::GetLabelOf(HBasicBlock* block) const {
252  return block_labels_.GetRawStorage() + block->GetBlockId();
253}
254
255CodeGenerator* CodeGenerator::Create(ArenaAllocator* allocator,
256                                     HGraph* graph,
257                                     InstructionSet instruction_set) {
258  switch (instruction_set) {
259    case kArm:
260    case kThumb2: {
261      return new (allocator) arm::CodeGeneratorARM(graph);
262    }
263    case kMips:
264      return nullptr;
265    case kX86: {
266      return new (allocator) x86::CodeGeneratorX86(graph);
267    }
268    case kX86_64: {
269      return new (allocator) x86_64::CodeGeneratorX86_64(graph);
270    }
271    default:
272      return nullptr;
273  }
274}
275
276void CodeGenerator::BuildNativeGCMap(
277    std::vector<uint8_t>* data, const DexCompilationUnit& dex_compilation_unit) const {
278  const std::vector<uint8_t>& gc_map_raw =
279      dex_compilation_unit.GetVerifiedMethod()->GetDexGcMap();
280  verifier::DexPcToReferenceMap dex_gc_map(&(gc_map_raw)[0]);
281
282  uint32_t max_native_offset = 0;
283  for (size_t i = 0; i < pc_infos_.Size(); i++) {
284    uint32_t native_offset = pc_infos_.Get(i).native_pc;
285    if (native_offset > max_native_offset) {
286      max_native_offset = native_offset;
287    }
288  }
289
290  GcMapBuilder builder(data, pc_infos_.Size(), max_native_offset, dex_gc_map.RegWidth());
291  for (size_t i = 0; i < pc_infos_.Size(); i++) {
292    struct PcInfo pc_info = pc_infos_.Get(i);
293    uint32_t native_offset = pc_info.native_pc;
294    uint32_t dex_pc = pc_info.dex_pc;
295    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
296    CHECK(references != NULL) << "Missing ref for dex pc 0x" << std::hex << dex_pc;
297    builder.AddEntry(native_offset, references);
298  }
299}
300
301void CodeGenerator::BuildMappingTable(std::vector<uint8_t>* data, SrcMap* src_map) const {
302  uint32_t pc2dex_data_size = 0u;
303  uint32_t pc2dex_entries = pc_infos_.Size();
304  uint32_t pc2dex_offset = 0u;
305  int32_t pc2dex_dalvik_offset = 0;
306  uint32_t dex2pc_data_size = 0u;
307  uint32_t dex2pc_entries = 0u;
308
309  if (src_map != nullptr) {
310    src_map->reserve(pc2dex_entries);
311  }
312
313  // We currently only have pc2dex entries.
314  for (size_t i = 0; i < pc2dex_entries; i++) {
315    struct PcInfo pc_info = pc_infos_.Get(i);
316    pc2dex_data_size += UnsignedLeb128Size(pc_info.native_pc - pc2dex_offset);
317    pc2dex_data_size += SignedLeb128Size(pc_info.dex_pc - pc2dex_dalvik_offset);
318    pc2dex_offset = pc_info.native_pc;
319    pc2dex_dalvik_offset = pc_info.dex_pc;
320    if (src_map != nullptr) {
321      src_map->push_back(SrcMapElem({pc2dex_offset, pc2dex_dalvik_offset}));
322    }
323  }
324
325  uint32_t total_entries = pc2dex_entries + dex2pc_entries;
326  uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
327  uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
328  data->resize(data_size);
329
330  uint8_t* data_ptr = &(*data)[0];
331  uint8_t* write_pos = data_ptr;
332  write_pos = EncodeUnsignedLeb128(write_pos, total_entries);
333  write_pos = EncodeUnsignedLeb128(write_pos, pc2dex_entries);
334  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size);
335  uint8_t* write_pos2 = write_pos + pc2dex_data_size;
336
337  pc2dex_offset = 0u;
338  pc2dex_dalvik_offset = 0u;
339  for (size_t i = 0; i < pc2dex_entries; i++) {
340    struct PcInfo pc_info = pc_infos_.Get(i);
341    DCHECK(pc2dex_offset <= pc_info.native_pc);
342    write_pos = EncodeUnsignedLeb128(write_pos, pc_info.native_pc - pc2dex_offset);
343    write_pos = EncodeSignedLeb128(write_pos, pc_info.dex_pc - pc2dex_dalvik_offset);
344    pc2dex_offset = pc_info.native_pc;
345    pc2dex_dalvik_offset = pc_info.dex_pc;
346  }
347  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size + pc2dex_data_size);
348  DCHECK_EQ(static_cast<size_t>(write_pos2 - data_ptr), data_size);
349
350  if (kIsDebugBuild) {
351    // Verify the encoded table holds the expected data.
352    MappingTable table(data_ptr);
353    CHECK_EQ(table.TotalSize(), total_entries);
354    CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
355    auto it = table.PcToDexBegin();
356    auto it2 = table.DexToPcBegin();
357    for (size_t i = 0; i < pc2dex_entries; i++) {
358      struct PcInfo pc_info = pc_infos_.Get(i);
359      CHECK_EQ(pc_info.native_pc, it.NativePcOffset());
360      CHECK_EQ(pc_info.dex_pc, it.DexPc());
361      ++it;
362    }
363    CHECK(it == table.PcToDexEnd());
364    CHECK(it2 == table.DexToPcEnd());
365  }
366}
367
368void CodeGenerator::BuildVMapTable(std::vector<uint8_t>* data) const {
369  Leb128EncodingVector vmap_encoder;
370  // We currently don't use callee-saved registers.
371  size_t size = 0 + 1 /* marker */ + 0;
372  vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
373  vmap_encoder.PushBackUnsigned(size);
374  vmap_encoder.PushBackUnsigned(VmapTable::kAdjustedFpMarker);
375
376  *data = vmap_encoder.GetData();
377}
378
379}  // namespace art
380