code_generator.cc revision 804d09372cc3d80d537da1489da4a45e0e19aa5d 
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 "dex/verified_method.h"
22#include "driver/dex_compilation_unit.h"
23#include "gc_map_builder.h"
24#include "leb128.h"
25#include "mapping_table.h"
26#include "utils/assembler.h"
27#include "verifier/dex_gc_map.h"
28#include "vmap_table.h"
29
30namespace art {
31
32void CodeGenerator::Compile(CodeAllocator* allocator) {
33  const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks();
34  DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock());
35  DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1)));
36  GenerateFrameEntry();
37  for (size_t i = 0, e = blocks.Size(); i < e; ++i) {
38    CompileBlock(blocks.Get(i));
39  }
40  size_t code_size = GetAssembler()->CodeSize();
41  uint8_t* buffer = allocator->Allocate(code_size);
42  MemoryRegion code(buffer, code_size);
43  GetAssembler()->FinalizeInstructions(code);
44}
45
46void CodeGenerator::CompileBlock(HBasicBlock* block) {
47  Bind(GetLabelOf(block));
48  HGraphVisitor* location_builder = GetLocationBuilder();
49  HGraphVisitor* instruction_visitor = GetInstructionVisitor();
50  for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) {
51    HInstruction* current = it.Current();
52    current->Accept(location_builder);
53    InitLocations(current);
54    current->Accept(instruction_visitor);
55  }
56}
57
58size_t CodeGenerator::AllocateFreeRegisterInternal(
59    bool* blocked_registers, size_t number_of_registers) const {
60  for (size_t regno = 0; regno < number_of_registers; regno++) {
61    if (!blocked_registers[regno]) {
62      blocked_registers[regno] = true;
63      return regno;
64    }
65  }
66  LOG(FATAL) << "Unreachable";
67  return -1;
68}
69
70
71void CodeGenerator::AllocateRegistersLocally(HInstruction* instruction) const {
72  LocationSummary* locations = instruction->GetLocations();
73  if (locations == nullptr) return;
74
75  for (size_t i = 0, e = GetNumberOfRegisters(); i < e; ++i) {
76    blocked_registers_[i] = false;
77  }
78
79  // Mark all fixed input, temp and output registers as used.
80  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
81    Location loc = locations->InAt(i);
82    if (loc.IsRegister()) {
83      // Check that a register is not specified twice in the summary.
84      DCHECK(!blocked_registers_[loc.GetEncoding()]);
85      blocked_registers_[loc.GetEncoding()] = true;
86    }
87  }
88
89  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
90    Location loc = locations->GetTemp(i);
91    if (loc.IsRegister()) {
92      // Check that a register is not specified twice in the summary.
93      DCHECK(!blocked_registers_[loc.GetEncoding()]);
94      blocked_registers_[loc.GetEncoding()] = true;
95    }
96  }
97
98  SetupBlockedRegisters(blocked_registers_);
99
100  // Allocate all unallocated input locations.
101  for (size_t i = 0, e = locations->GetInputCount(); i < e; ++i) {
102    Location loc = locations->InAt(i);
103    HInstruction* input = instruction->InputAt(i);
104    if (loc.IsUnallocated()) {
105      if (loc.GetPolicy() == Location::kRequiresRegister) {
106        loc = Location::RegisterLocation(
107            AllocateFreeRegister(input->GetType(), blocked_registers_));
108      } else {
109        DCHECK_EQ(loc.GetPolicy(), Location::kAny);
110        HLoadLocal* load = input->AsLoadLocal();
111        if (load != nullptr) {
112          loc = GetStackLocation(load);
113        } else {
114          loc = Location::RegisterLocation(
115              AllocateFreeRegister(input->GetType(), blocked_registers_));
116        }
117      }
118      locations->SetInAt(i, loc);
119    }
120  }
121
122  // Allocate all unallocated temp locations.
123  for (size_t i = 0, e = locations->GetTempCount(); i < e; ++i) {
124    Location loc = locations->GetTemp(i);
125    if (loc.IsUnallocated()) {
126      DCHECK_EQ(loc.GetPolicy(), Location::kRequiresRegister);
127      // TODO: Adjust handling of temps. We currently consider temps to use
128      // core registers. They may also use floating point registers at some point.
129      loc = Location::RegisterLocation(static_cast<ManagedRegister>(
130          AllocateFreeRegister(Primitive::kPrimInt, blocked_registers_)));
131      locations->SetTempAt(i, loc);
132    }
133  }
134
135  // Make all registers available for the return value.
136  for (size_t i = 0, e = GetNumberOfRegisters(); i < e; ++i) {
137    blocked_registers_[i] = false;
138  }
139  SetupBlockedRegisters(blocked_registers_);
140
141  Location result_location = locations->Out();
142  if (result_location.IsUnallocated()) {
143    switch (result_location.GetPolicy()) {
144      case Location::kAny:
145      case Location::kRequiresRegister:
146        result_location = Location::RegisterLocation(
147            AllocateFreeRegister(instruction->GetType(), blocked_registers_));
148        break;
149      case Location::kSameAsFirstInput:
150        result_location = locations->InAt(0);
151        break;
152    }
153    locations->SetOut(result_location);
154  }
155}
156
157void CodeGenerator::InitLocations(HInstruction* instruction) {
158  if (instruction->GetLocations() == nullptr) {
159    return;
160  }
161  AllocateRegistersLocally(instruction);
162  for (size_t i = 0, e = instruction->InputCount(); i < e; ++i) {
163    Location location = instruction->GetLocations()->InAt(i);
164    if (location.IsValid()) {
165      // Move the input to the desired location.
166      Move(instruction->InputAt(i), location, instruction);
167    }
168  }
169}
170
171bool CodeGenerator::GoesToNextBlock(HBasicBlock* current, HBasicBlock* next) const {
172  // We currently iterate over the block in insertion order.
173  return current->GetBlockId() + 1 == next->GetBlockId();
174}
175
176Label* CodeGenerator::GetLabelOf(HBasicBlock* block) const {
177  return block_labels_.GetRawStorage() + block->GetBlockId();
178}
179
180CodeGenerator* CodeGenerator::Create(ArenaAllocator* allocator,
181                                     HGraph* graph,
182                                     InstructionSet instruction_set) {
183  switch (instruction_set) {
184    case kArm:
185    case kThumb2: {
186      return new (allocator) arm::CodeGeneratorARM(graph);
187    }
188    case kMips:
189      return nullptr;
190    case kX86: {
191      return new (allocator) x86::CodeGeneratorX86(graph);
192    }
193    case kX86_64: {
194      return new (allocator) x86::CodeGeneratorX86(graph);
195    }
196    default:
197      return nullptr;
198  }
199}
200
201void CodeGenerator::BuildNativeGCMap(
202    std::vector<uint8_t>* data, const DexCompilationUnit& dex_compilation_unit) const {
203  const std::vector<uint8_t>& gc_map_raw =
204      dex_compilation_unit.GetVerifiedMethod()->GetDexGcMap();
205  verifier::DexPcToReferenceMap dex_gc_map(&(gc_map_raw)[0]);
206
207  uint32_t max_native_offset = 0;
208  for (size_t i = 0; i < pc_infos_.Size(); i++) {
209    uint32_t native_offset = pc_infos_.Get(i).native_pc;
210    if (native_offset > max_native_offset) {
211      max_native_offset = native_offset;
212    }
213  }
214
215  GcMapBuilder builder(data, pc_infos_.Size(), max_native_offset, dex_gc_map.RegWidth());
216  for (size_t i = 0; i < pc_infos_.Size(); i++) {
217    struct PcInfo pc_info = pc_infos_.Get(i);
218    uint32_t native_offset = pc_info.native_pc;
219    uint32_t dex_pc = pc_info.dex_pc;
220    const uint8_t* references = dex_gc_map.FindBitMap(dex_pc, false);
221    CHECK(references != NULL) << "Missing ref for dex pc 0x" << std::hex << dex_pc;
222    builder.AddEntry(native_offset, references);
223  }
224}
225
226void CodeGenerator::BuildMappingTable(std::vector<uint8_t>* data) const {
227  uint32_t pc2dex_data_size = 0u;
228  uint32_t pc2dex_entries = pc_infos_.Size();
229  uint32_t pc2dex_offset = 0u;
230  int32_t pc2dex_dalvik_offset = 0;
231  uint32_t dex2pc_data_size = 0u;
232  uint32_t dex2pc_entries = 0u;
233
234  // We currently only have pc2dex entries.
235  for (size_t i = 0; i < pc2dex_entries; i++) {
236    struct PcInfo pc_info = pc_infos_.Get(i);
237    pc2dex_data_size += UnsignedLeb128Size(pc_info.native_pc - pc2dex_offset);
238    pc2dex_data_size += SignedLeb128Size(pc_info.dex_pc - pc2dex_dalvik_offset);
239    pc2dex_offset = pc_info.native_pc;
240    pc2dex_dalvik_offset = pc_info.dex_pc;
241  }
242
243  uint32_t total_entries = pc2dex_entries + dex2pc_entries;
244  uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
245  uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
246  data->resize(data_size);
247
248  uint8_t* data_ptr = &(*data)[0];
249  uint8_t* write_pos = data_ptr;
250  write_pos = EncodeUnsignedLeb128(write_pos, total_entries);
251  write_pos = EncodeUnsignedLeb128(write_pos, pc2dex_entries);
252  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size);
253  uint8_t* write_pos2 = write_pos + pc2dex_data_size;
254
255  pc2dex_offset = 0u;
256  pc2dex_dalvik_offset = 0u;
257  for (size_t i = 0; i < pc2dex_entries; i++) {
258    struct PcInfo pc_info = pc_infos_.Get(i);
259    DCHECK(pc2dex_offset <= pc_info.native_pc);
260    write_pos = EncodeUnsignedLeb128(write_pos, pc_info.native_pc - pc2dex_offset);
261    write_pos = EncodeSignedLeb128(write_pos, pc_info.dex_pc - pc2dex_dalvik_offset);
262    pc2dex_offset = pc_info.native_pc;
263    pc2dex_dalvik_offset = pc_info.dex_pc;
264  }
265  DCHECK_EQ(static_cast<size_t>(write_pos - data_ptr), hdr_data_size + pc2dex_data_size);
266  DCHECK_EQ(static_cast<size_t>(write_pos2 - data_ptr), data_size);
267
268  if (kIsDebugBuild) {
269    // Verify the encoded table holds the expected data.
270    MappingTable table(data_ptr);
271    CHECK_EQ(table.TotalSize(), total_entries);
272    CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
273    auto it = table.PcToDexBegin();
274    auto it2 = table.DexToPcBegin();
275    for (size_t i = 0; i < pc2dex_entries; i++) {
276      struct PcInfo pc_info = pc_infos_.Get(i);
277      CHECK_EQ(pc_info.native_pc, it.NativePcOffset());
278      CHECK_EQ(pc_info.dex_pc, it.DexPc());
279      ++it;
280    }
281    CHECK(it == table.PcToDexEnd());
282    CHECK(it2 == table.DexToPcEnd());
283  }
284}
285
286void CodeGenerator::BuildVMapTable(std::vector<uint8_t>* data) const {
287  Leb128EncodingVector vmap_encoder;
288  // We currently don't use callee-saved registers.
289  size_t size = 0 + 1 /* marker */ + 0;
290  vmap_encoder.Reserve(size + 1u);  // All values are likely to be one byte in ULEB128 (<128).
291  vmap_encoder.PushBackUnsigned(size);
292  vmap_encoder.PushBackUnsigned(VmapTable::kAdjustedFpMarker);
293
294  *data = vmap_encoder.GetData();
295}
296
297}  // namespace art
298