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